LeetCode 161-165

162. 寻找峰值

线性O(n)的方法很容易想到，直接从左往右遍历，只要某个点的值大于它右边的值，那么它就是峰值。
题目要求Ologn，需要使用二分。在中点mid处比较它和mid+1处的大小，如果mid更大，那么峰值一定在mid左边（包含mid），此时令hi = mid。如果mid+1更大，那么峰值一定在mid右边（不包含mid），此时令lo = mid+1。
直到lo = hi时，这个点就是峰值。

class Solution {
    public int findPeakElement(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[mid + 1]) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

164. 最大间距

O(nlogn)的方法:

class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int res = 0;
        for (int i = 1; i < nums.length; i++) {
            res = Math.max(res, Math.abs(nums[i] - nums[i - 1]));
        }
        return res;
    }
}

O(n)的方法，桶排序：

165. 比较版本号

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\."), v2 = version2.split("\\.");
        int minLen = Math.min(v1.length, v2.length);
        for (int i = 0; i < minLen; i++) {
            if (Integer.parseInt(v1[i]) > Integer.parseInt(v2[i])) {
                return 1;
            } else if (Integer.parseInt(v1[i]) == Integer.parseInt(v2[i])) {

            } else {
                return -1;
            }
        }
        if (v1.length > minLen) {
            for (int i = minLen; i < v1.length; i++) {
                if (Integer.parseInt(v1[i]) != 0) {
                    return 1;
                }
            }
            return 0;
        } else if (v2.length > minLen) {
            for (int i = minLen; i < v2.length; i++) {
                if (Integer.parseInt(v2[i]) != 0) {
                    return -1;
                }
            }
            return 0;
        }
        return 0;
    }
}

优化，写的更简单:

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\."), v2 = version2.split("\\.");
        int len1 = v1.length, len2 = v2.length, maxLen = Math.max(len1, len2);
        int num1, num2;
        for (int i = 0; i < maxLen; i++) {
            num1 = i < len1 ? Integer.parseInt(v1[i]) : 0;
            num2 = i < len2 ? Integer.parseInt(v2[i]) : 0;
            if (num1 != num2) {
                return num1 > num2 ? 1 : -1;
            }
        }
        return 0;
    }
}