LC 704. 二分查找

class Solution {
    public int search(int[] nums, int target) {
        {
            /*
            二分查找的时间复杂度：O(logn)
             */
        }
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] != target) {
            return -1;
        } else {
            return l;
        }
    }
}

class Solution {
    public int search(int[] nums, int target) {
        {
            /*
            二分查找的时间复杂度：O(logn)
             */
        }
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            // 找到结果就直接返回
            // 对第一种方法的优化
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] != target) {
            return -1;
        } else {
            return l;
        }
    }
}

LC 714. 买卖股票的最佳时机含手续费

股票问题系列通解

LC 763. 划分字母区间

思路：维护一个区间的左边界和右边界，在这个区间内遍历查看字符出现的最远位置，并更新右边界为新的最远位置。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] nums = new int[26];
        List<Integer> list = new ArrayList<>();
        Arrays.fill(nums, -1);
        // 记录字符出现的最远位置
        for (int i = 0; i < s.length(); i++) {
            nums[s.charAt(i) - 'a'] = i;
        }
        int left = 0;
        while (left < s.length()) {
            int right = nums[s.charAt(left) - 'a'];
            for (int i = left + 1; i < right; i++) {
                if (nums[s.charAt(i) - 'a'] > right) {
                    right = nums[s.charAt(i) - 'a'];
                }
            }
            list.add(right - left + 1);
            left = right + 1;
        }
        return list;
    }
}