刷题笔记

滑动窗口

滑动窗口可以解决子结构中求最值问题，例如：

解决滑动窗口问题包含几个步骤：

  1. 确定窗口大小
  2. 移动右指针使得窗口最大，更新结果
  3. 移动左指针缩小窗口，使得窗口保持最大，更新结果

要理解滑动窗口不难，难点在于如何正确的把所有细节都写出来，以 无重复字符的最长子串为例：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

这类问题是找求最大的窗口大小，难度不高，不过要注意是不含重复字符的，因此我们可以一个HashSet来实时存储当前窗口中的无重复字符。

何时移动右指针增大窗口？当HashSet中不存在当前字符时，增大窗口。

何时移动左指针缩小窗口？当HashSet中存在当前字符时，缩小窗口。

每一次遍历，我们都需要更新最大窗口的值，遍历完之后得到的最大窗口值即为结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        Set<Character> set = new HashSet<>();

        int left = 0, right = 0, maxLen = 0;

        while (right < s.length()) {
            char c = s.charAt(right);

            if (!set.contains(c)) {
                set.add(c);
                right++;
            } else {
                // 将left指针指向的字符移出Set中
                set.remove(s.charAt(left));
                left++;
            }

            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
}

二分查找

一般看到有序就要考虑二分，通常不会直接让你写二分查找，大部分都是变形题。

正常的二分查找

二分查找的原理很简单，但细节很多，这里有几个需要注意的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; // 注意
    while (left <= right) { // 注意
        int mid = left + (right - left) / 2;  // 注意

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

如果把右边界定为数组长度 - 1，那么循环的进入条件就是 left <= right。

对于mid的算法，使用left + (right - left) / 2的方式可以防止left + right可能溢出的问题，当然如果题目给出的数据范围是不可能溢出的话正常写就行 。

求左右边界

一般来说算法中不会直接让我们直接套二分查找，而是要求我们利用二分查找来寻找重复数据的左右边界。

对于左边界，只需要对上面的代码一些小改动即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int binarySearchLeftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            right = mid - 1;  // 注意
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (left == nums.length || nums[left] != target) return -1; // 注意
    return left;  // 注意
}

为了寻找左边界，当我们发现mid对应的数等于target时，我们不能直接返回，而是缩小搜索区域为mid左边，即right = mid - 1。

这里有几点需要特别注意：

  1. 第一点，搜索结束时，应该返回left而不是right。

    为什么返回left，只需要考虑最后一次循环即可快速理解。最后一次循环时，left、mid、right三者相等，此时将会进入第一个if分支中，right = mid - 1，使得right会小于我们所求的边界，因此left才是最终答案。

  2. 第二点，如果搜索不到对应的target时，需要考虑越界问题。

    如果target不在待搜索数组中，有三种情况：

    • target小于数组中的所有数
    • target小于数组中的部分数，大于数组中的另一部分数
    • target大于数组中的所有数

    对于第一种和第二种情况，当循环结束时，left都不会越界，因此只需要考虑nums[left]与target是否相等就知道target存不存在数组中。

    对于第三种情况，经过最后一次循环时，left将会被赋值为mid + 1，导致最终left为数组长度，此时使用nums[left]将会有越界问题，所以需要单独判断。

    最终通过left == nums.length || nums[left] != target)这个表达式我们可以判断出数组中是否是不存在target的。

对于右边界，代码与左边界是类似的，如下所示，这里不再赘述：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int binarySearchRightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            left = mid + 1;  // 注意
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (right < 0 || nums[right] != target) return -1; // 注意
    return right;  // 注意
}

回溯算法

回溯算法即带有撤销操作的DFS算法，用于处理需要求出所有可能的结果的问题。

算法基本逃不出这个框架：

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

难点在于如何去除重复项，即剪枝。

剪枝要考虑清除题目要求的不可重复项，例如组合2中要求不出现重复的数字，而子集2中要求不能出现重复的子集。

对于无法确定的要先画出决策树，再考虑应该减去同一层重复的还是同一路径重复的。

对于同一路径去重，即组合2问题，只需要对源数据进行排序后，判断前后数字是否相同即可。

对于同一层去重，即子集2问题，需要引入一个visited的boolean标志位数组，选择当前数字后，在撤销选择时将其visited[i]标记为true，表示此层使用此数字完成了一此回溯选择，同一层的重复数字遇到此标记位为true时就可以不用继续了，因为必定重复。