首页 学习记录

# 哈希

# 1 两数之和

思路：二分查找。不过要注意下标，采用下标索引转换。

后更新：简直是莫名其妙，哈希表就行了，在二分查找什么

public int[] twoSum(int[] nums, int target) {  
    int n = nums.length;  
    Integer[] indices = new Integer[n];  
    for (int i = 0; i < n; i++) {  
        indices[i] = i;  
    }  
  
    Arrays.sort(indices, Comparator.comparingInt(a -> nums[a]));  
  
    for (int i = 0; i < n; i++) {  
        int need = target - nums[indices[i]];  
        int index = binarySearch(nums, need, indices, i + 1, n - 1);  
        if (index != -1) {  
            return new int[]{indices[i], index};  
        }  
    }  
    return new int[]{};  
}  
  
public int binarySearch(int[] nums, int target, Integer[] indices, int left, int right) {  
    while (left <= right) {  
        int mid = left + (right - left) / 2;  
        int midValue = nums[indices[mid]];  
        if (midValue == target) {  
            return indices[mid];  
        } else if (midValue < target) {  
            left = mid + 1;  
        } else {  
            right = mid - 1;  
        }  
    }  
    return -1;  
}
  1. 学习 Arrays.sort(indices, Comparator.comparingInt(a -> nums[a]));
  2. 学习 indices 索引

# 49 字母异位词分组

关键点：排序，哈希表

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

# 128 最长连续数列

有几个关键点：

  1. 第二次遍历的时候是遍历哈希表。为什么呢？因为哈希表可以去重，如果数组是 10^9 个 1，那么哈希表内只有一个 1 ，大大减少时间。
  2. 为了降低时间复杂度，依据特性，需要判断 !set.contains(num - 1) ，从而把时间复杂度从 O(n2)O(n^2) 降为 O(n)O(n)
class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num: nums) {
            set.add(num);
        }
        int longestStreak = 0;
        for (int num : set) {
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }
}

# 双指针

# 283 移动零

两个方法，一个是双指针（即维护两个下标），一个是原地栈

# 双指针

使用双指针，左指针指向当前已经处理好的序列的尾部（实际上不是尾部，是尾部后的第一个不在该序列内的数字），右指针指向待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }
    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
# 原地栈
原理就是第一次遍历获得 0 的个数并删去 0，第二次把 0 加上去。但是这里精妙点就在于把获得 0 的个数与删去 0 两件事合在同一次循环里完成了。
由于 i 必定大于等于 j，利用特性可以在该次循环中就进行覆盖去除 0，不会导致非 0 值被意外覆盖的情况。这个做法个人认为是相当巧妙且比上面那个好懂的。
public void moveZeroes(int[] nums) {  
    int j = 0;  
    for (int i = 0; i < nums.length; i++) {  
        if (nums[i] != 0) {  
            nums[j] = nums[i];  
            j++;  
        }  
    }  
    while (j < nums.length) {  
        nums[j] = 0;  
        j++;  
    }  
}
# 11 盛最多水的容器
感觉之前就做过这个题。思路是双指针指向最左与最右（下标），依次移动其中较小的一个，直到二者重合。
那么为什么是移动较小的那个呢？因为我们的目的是找到最大的，但是我们不知道最大的在哪，那么我们的移动其实是有随机性的。但是我们可以证明，如果不移动较小的那方而是移动较大的那方，后面的容量是肯定比一开始的小的。这个可以画图直观感受。
所以，因为随机性的存在我们需要尝试，那就只能移动较大的那一方的。依次移动，每次记录值并且更新最大值，直到重合所有情况列举完毕。
换言之，就是一个怎么做到最大收益移动的问题。因为移动的方式只有两种，有一种可以肯定只会越来越差，那么就选取另一个了。
public int maxArea(int[] height) {  
    int max = 0;  
    int left = 0;  
    int right = height.length - 1;  
    while (left < right) {  
        int area = Math.min(height[left], height[right]) * (right - left);  
        max = Math.max(max, area);  
        if (height[left] < height[right]) {  
            left++;  
        } else {  
            right--;  
        }  
    }  
    return max;  
}
# 15 三数之和
先排序，再三层循环，保证枚举出的 a <= b <= c，优化不重复枚举，其中 c 从右向左遍历。
但是这题巧妙的点还挺多的，关键在于如何最大化利用升序数组这个性质，从而实现多指针的最少数量遍历。
这个是我大概看了题解思路后写的第一版代码，不过超时了：
public List<List<Integer>> threeSum(int[] nums) {  
    List<List<Integer>> result = new ArrayList<>();  
    Arrays.sort(nums);  
    for (int i = 0; i < nums.length - 2; i++) {  
        if (i > 0 && nums[i] == nums[i - 1]) {  
            continue;  
        }  
        int target = -nums[i];  
        for (int j = i + 1; j < nums.length - 1; j++) {  
            if (j > i + 1 && nums[j] == nums[j - 1]) {  
                continue;  
            }  
            int right = nums.length - 1;  // 注意点 1
            while (j < right) {  
                if (nums[j] + nums[right] > target) {  // 巧妙点
                    right--;  
                } else {  
                    break;  
                }  
            }  
            if (j == right || nums[j] + nums[right] != target) {  
                continue;  // 注意点 2
            }  
            List<Integer> triplet = new ArrayList<>();  
            triplet.add(nums[i]);  
            triplet.add(nums[j]);  
            triplet.add(nums[right]);  
            result.add(triplet);  
        }  
    }  
    return result;  
}
巧妙点这一行，先想，我们需要找到的是 nums[j] + nums[right] == target 的情况，而我们已经将数组事先排序，那么当 j 固定而 right 逐渐向左逼近的过程中， nums[j] + nums[right] 肯定是越来越小的，而如果某一点 right 的值已经使和小于 target 了，那么再逼近也没有意义了，所以可以退出第三层循环。
但是，在我写的代码里面，right 是每次二层循环重定义一次的，这导致耗时还是很久。下面的是优化后的：
public List<List<Integer>> threeSum(int[] nums) {  
    List<List<Integer>> result = new ArrayList<>();  
    Arrays.sort(nums);  
    for (int i = 0; i < nums.length - 2; i++) {  
        if (i > 0 && nums[i] == nums[i - 1]) {  
            continue;  
        }  
        int target = -nums[i];  
        int right = nums.length - 1; // 对应注意点 1  
        for (int j = i + 1; j < nums.length - 1; j++) {  
            if (j > i + 1 && nums[j] == nums[j - 1]) {  
                continue;  
            }  
            while (j < right) {  
                if (nums[j] + nums[right] > target) {  
                    right--;  
                } else {  
                    break;  
                }  
            }  
            if (j == right) {  
                break; // 对应注意点 2  
            }  
            if (nums[j] + nums[right] == target) {  
                List<Integer> triplet = new ArrayList<>();  
                triplet.add(nums[i]);  
                triplet.add(nums[j]);  
                triplet.add(nums[right]);  
                result.add(triplet);  
            }  
        }  
    }  
    return result;  
}
这里，我们对二层循环也进行了优化。思考一下，为什么 right 可以在第一层循环就定义？而对应的为什么当 j == right 后，我们就可以退出第二层循环了？
先解释第二个问题。还是那个道理，我们的目的是逼近 j 和 right，找到 nums[j] + nums[right] == target 的情况。我们可以看到，当 j == right 时，那必然第三层循环全部进行完毕，也就是对于固定的 j，所有的 right 全都使 nums[j] + nums[right] > target ，在这个时候，继续逼近 j 也就是增大 j 的值，那么其和必然还是大于 target 的，所以完全可以退出第二层循环了。
我们优化完这一点后已经可以通过测试，但是耗时还是很久。接下来就是第一个问题 —— 为什么 right 可以在第一层循环就定义？这个换句话说就是，为什么 right 的值在第二层循环是可以继承复用的。
我们还是从目的讲起，逼近 j 和 right，找到 nums[j] + nums[right] == target 。那么，介于上面我们知道除去到达终点外退出第二层循环的条件是 j == right ，所有的 j 和 right 全都使 nums[j] + nums[right] > target ，那么，继续进行第二层循环即代表着存在一个 right， nums[j] + nums[right] <= target （当然，等于的情况已经被加入结果中了），而 right + 1（如果存在的话），它可以使和大于 target。那么现在，我们需要逼近 j，从而试图找到能让和等于 target 的值。
我们现在举例几个下标 1 2 3 4 5 6. 假设 j == 1，right == 5， nums[1] + nums[6] > target ，而 nums[1] + nums[5] < target ，再向右逼近 right 已经没有意义，只能向左逼近 j。那么为什么 right 可以复用呢？我们假设 j 逼近到 2，right 还是重新从 6 开始计算， nums[2] + nums[6] 必然大于 nums[1] + nums[6] 也必然大于 target，所以是可以复用的。
这题可以说是优化的相当精妙了，佩服佩服。个人认为，还是得找到核心目的，从目的出发，一步步优化方法实现，利益最大化。
# 42 接雨水
官方给了三种题解：动态规划、栈与双指针，个人觉得栈那个方法有点反人类直觉了。
# 动态规划
Pasted image 20250722164055.png
看这张直观图，可以看到，低洼处可以积水，积水高度与两边最矮的高度直接相关。是不是有点像盛最多水的容器这题？
那么，我们现在只考虑一个单位长度的地方能否积水（也就是能否形成一个长条）。这个需要符合什么条件呢？答案是该点处左右两点的高度都需要大于它。
那么，在该点处的积水量（也就是长条高度），由什么决定呢？我们假设这么一个数组： [1, 2, 1, 0, 1, 1, 3, 2] ，考虑在高度为 0 处的积水量，从该点先往左看，找到其非递减的最高高度，那就是 2；再向右看，找到非递减的最高高度，那就是 3。最后，取这两者的最小值，再减去自身的高度，得到的就是在这一点的积水量了。这个可以意会一下。
理论成立，现在落实到算法上。我们可以先通过两轮遍历，获得每点左边及右边符合上面理论的值。我们会发现找这个值是很容易的。
Pasted image 20250722165554.png
找到值后直接遍历数组，先判断能否积水，再算出积水值总和即可。
public int trap(int[] height) {  
    int sum = 0;  
    int[] leftMax = new int[height.length];  
    int[] rightMax = new int[height.length];  
    leftMax[0] = height[0];  
    rightMax[height.length - 1] = height[height.length - 1];  
    for (int i = 1; i < height.length; i++) {  
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);  
    }  
    for (int i = height.length - 2; i >= 0; i--) {  
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);  
    }  
    for (int i = 0; i < height.length; i++) {  
        if (Math.min(leftMax[i], rightMax[i]) - height[i] > 0) {  
            sum += Math.min(leftMax[i], rightMax[i]) - height[i];  
        }  
    }  
    return sum;  
}
# 双指针法
和上面那个用的是同一个理论。就是可能没那么直观了。
public int trap(int[] height) {  
    int sum = 0;  
    int left = 0;  
    int right = height.length - 1;  
    int leftMax = 0;  
    int rightMax = 0;  
    while (left < right) {  
        leftMax = Math.max(leftMax, height[left]);  
        rightMax = Math.max(rightMax, height[right]);  
        if (height[left] < height[right]) {  
            sum += leftMax - height[left];  
            left++;  
        } else {  
            sum += rightMax - height[right];  
            right--;  
        }  
    }  
    return sum;  
}
# 滑动窗口
# 3 无重复字符的最长子串
整体思路是遍历所有子串，判断它是否无重复字符，更新最大值。
最暴力情况下，时间复杂度为 O(n2)O(n^2)，那么，我们重点就是要优化这个遍历过程，尽量减少遍历次数。
left 左指针，right 右指针，首先固定左指针向右遍历，当检测到某个右指针子串有重复时，立即退出内循环，更新外循环。有一个很明显的优化思路：我们一次遍历下来的结果，是否可以保留中间已经判断过无重复的部分，留给下一次遍历呢？
public int lengthOfLongestSubstring(String s) {  
    int max = 0;  
    char[] chars = s.toCharArray();  
    int right = -1;  
    HashSet<Character> set = new HashSet<>();  
    for (int left = 0; left < s.length(); left++) {  
        if (left > 0) {  
            set.remove(chars[left - 1]);  
        }  
        while (right + 1 < s.length() && !set.contains(chars[right + 1])) {  
            set.add(chars[right + 1]);  
            right++;  
        }  
        max = Math.max(max, right - left + 1);  
        if (right == s.length() - 1) {  
            break;  
        }  
    }  
    return max;  
}
本质上我们这里做的是 right 的复用，right 停在检测到的最后一个符合当前子串为无重复子串的位置上，在下一轮继续判断 set.contains(chars[right + 1]) 成立与否。
或许也可以花一点功夫，把 left 移到最合适的位置上（比如 "aebcdbacd"，aebcd 判断后遇见第一个重复的 b，right 停留在 d 上，将 left 并非向前一步移到 e 而是直接移到 c 上）。但是我觉得花的这个功夫耗的时间也不能优化多少整体。
# 438 找到字符串中的所有字母异位词
public List<Integer> findAnagrams(String s, String p) {  
    int sLength = s.length();  
    int pLength = p.length();  
    if (sLength < pLength) {  
        return new ArrayList<>();  
    }  
    List<Integer> result = new ArrayList<>();  
    int[] pCount = new int[26];  
    int[] sCount = new int[26];  
    for (int i = 0; i < pLength; i++) {  
        pCount[p.charAt(i) - 'a']++;  
        sCount[s.charAt(i) - 'a']++;  
    }  
    if (Arrays.equals(pCount, sCount)) {  
        result.add(0);  
    }  
    for (int i = 0; i < sLength - pLength; i++) {  
        sCount[s.charAt(i) - 'a']--;  
        sCount[s.charAt(i + pLength) - 'a']++;  
        if (Arrays.equals(pCount, sCount)) {  
            result.add(i + 1);  
        }  
    }  
    return result;  
}
这题比较简单，滑动窗口思想，固定长度窗口依次遍历，同时，保留能够复用的部分，每次只要去除无用部分并加上新增部分即可。
# 子串
# 560 和为 K 的子数组
前缀和思路，非常巧妙的一题！！！
本题要求的是子数组和为 K 的数目，因为是连续子数组，刚刚又做了滑动窗口那几题，很明显就会想成窗口遍历的思路了。但是这个思路再怎么优化时间复杂度也是 O(n2)O(n^2) 。那么，我们能不能换个角度呢？
形象化，我们要求 [i, j] 范围数组的和，那么，我们是不是可以转化一下： Sum[i, j] = Sum[0, j] - Sum[0, i - 1] 。 Sum[0, i] ，不就是前缀和嘛。
通过计算出所有的前缀和，我们就能得到任意 Sum[i, j] 的值。但是这还不行啊，这不还得遍历所有 i j 可能性求值判断吗。这个时候，哈希表就来了。
public int subarraySum(int[] nums, int k) {  
    int count = 0;  
    HashMap<Integer, Integer> map = new HashMap<>();  
    int sum = 0;  
    map.put(0, 1);  // 必须要加
    for (int i = 0; i < nums.length; i++) {  
        sum += nums[i];  
        if (map.containsKey(sum - k)) {  
            count += map.get(sum - k);  
        }  
        map.put(sum, map.getOrDefault(sum, 0) + 1); // 必须要放在后面  
    }  
    return count;  
}
可以看到，我们哈希表的键值反而是 sum ，后面 value 则是对应出现的次数。这是怎么一回事呢？毕竟，我们要得到的只是和为 K 的子数组的数目啊！假设，K 为 10，前缀和为 11 的数组有 2 个，前缀和为 1 的数组有 2 个，那么，我们这里可以得到几个和为 10 的数组呢？很明显，是 4 个。
所以，我们可以直接无视位置，存储其出现次数即可。依次从前往后遍历，获得当前前缀和，先不急着存进去，看对应的 sum - k 有多少个，在 count 中加上本次数就行。
为什么加完后再存呢，主要是防止 sum - k = sum 也就是 k 为 0 的情况。如果放在前面，就会出现空数组，而本题对于子数组定义是非空的，因此不符合题干。此外也要注意在循环之前我们加上了 map.put(0, 1); ，也就是前缀和为 0 的天生有一个空数组情况，这个与结果的子数组是区分开的。可以自己试一下体会一下这两个分别起了什么作用。
# 239 滑动窗口最大值
这一题咋一看感觉还挺简单的，固定窗口移动，给出每个窗口内的最大值。那么，也完全可以像前几题一样，沿用已比较值复用的思路嘛！所以按照这个思路写了个代码，第一轮（0~k）筛出最大值和第二大的值，然后移动窗口，根据最新加入的值以及离开窗口的值，依次更新这两个。然后问题就来了 —— 万一最大值和第二大的值在后面都因为离开窗口没了怎么办呢！
但是这个总体思路肯定是没错的，就是这里我们究竟要记录上个窗口的多少信息复用于下个窗口。
我们看这个数组： [1, 2, 5, 4, 3, 6, 1] ， k = 4 。现在，假设我们先对下标 0 到 3 进行第一轮获得最大值，很明显是 5，对吧？我们把它记录下来。那么，其他三个也就是 1 2 4，这三个数字要不要记录呢？我们考虑窗口移动的逻辑，最左边的数字会被移出去，那么，在这个数组里，当下标为 2 （即 5）的数字处在窗口中时，下标为 0 和 1 的数字必然不可能在后面的移动中成为最大值，所以我们可以直接排除掉它们。但是对于下标为 3 也就是 4，因为后面 5 会离开窗口，所以我们还是得记录下 4。
“当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中，这是 i 在 j 的左侧所保证的。因此，由于 nums [j] 的存在，nums [i] 一定不会是滑动窗口中的最大值了，我们可以将 nums [i] 永久地移除。”
以此类推，我们维护一个队列，存的是下标，这些下标按从小到大的顺序存储，且其在数组中对应的数字严格递减。总觉得这个想讲完全清楚有点难…… 最好还是要意会一下感受一下。个人觉得还是有些巧妙的。充分地利用了固定窗口滑动的性质，做到了存储所有必要信息用于复用。
public int[] maxSlidingWindow(int[] nums, int k) {  
    int n = nums.length;  
    Deque<Integer> deque = new LinkedList<>();  
    int[] result = new int[n - k + 1];  
    for (int i = 0; i < k; i++) {  
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {  
            deque.pollLast();  
        }  
        deque.offerLast(i);  
    }  
    result[0] = nums[deque.peekFirst()];  
    for (int i = k; i < n; i++) {  
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {  
            deque.pollLast();  
        }  
        deque.offerLast(i);  
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {  
            deque.pollFirst();  
        }  
        result[i - k + 1] = nums[deque.peekFirst()];  
    }  
    return result;  
}
“我悟了， 队尾比不过同龄人的删掉，队头超出时代区间的删掉，历史就是这么不断更迭的。”
—— 出自力扣官方题解评论
# 76 最小覆盖子串
有点难度的一题（毕竟是 Hard）。这一题还是我们滑动窗口，我们先确定大致的思路，再进行优化。
两个指针 left right，首先固定 left 为 0，向右移动 right，当 left 到 right 区段满足题目要求时，我们再固定 right，向右移动 left，尝试找出这一段的最小满足条件区段。找出来后记录长度及坐标，再固定 left，向右移动 right，重复以上过程，找下一组符合题目条件的区间，直到 right 到达最右端。
（下面代码出自灵茶山艾府）
public String minWindow(String S, String t) {  
    int[] cntS = new int[128]; //s 子串字母的出现次数  
    int[] cntT = new int[128]; //t 中字母的出现次数  
    for (char c : t.toCharArray()) {  
        cntT[c]++;  
    }  
  
    char[] s = S.toCharArray();  
    int m = s.length;  
    int ansLeft = -1;  
    int ansRight = m;  
  
    int left = 0;  
    for (int right = 0; right < m; right++) { // 移动子串右端点  
        cntS[s[right]]++; // 右端点字母移入子串  
        while (isCovered(cntS, cntT)) { // 涵盖  
            if (right - left < ansRight - ansLeft) { // 找到更短的子串  
                ansLeft = left; // 记录此时的左右端点  
                ansRight = right;  
            }  
            cntS[s[left]]--; // 左端点字母移出子串  
            left++;  
        }  
    }  
  
    return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);  
}  
  
private boolean isCovered(int[] cntS, int[] cntT) {  
    for (int i = 'A'; i <= 'Z'; i++) {  
        if (cntS[i] < cntT[i]) {  
            return false;  
        }  
    }  
    for (int i = 'a'; i <= 'z'; i++) {  
        if (cntS[i] < cntT[i]) {  
            return false;  
        }  
    }  
    return true;  
}
纯粹按照上面那个思想实现的时间复杂度是 O (∣Σ∣m+n)，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣ 为字符集合的大小，本题字符均为英文字母，所以 ∣Σ∣=52。那么，可以看到每一次判断是否包含都要遍历 26 个字符，那么能不能优化呢？
优化后的代码：
public String minWindow(String S, String t) {  
    if (S == null || t == null || S.length() < t.length()) {  
        return "";  
    }  
    int[] tCount = new int[128];  
    for (char c : t.toCharArray()) {  
        tCount[c]++;  
    }  
    int required = t.length();  
    int left = 0, right = 0, minLength = Integer.MAX_VALUE, start = 0;  
    while (right < S.length()) {  
        char cRight = S.charAt(right);  
        if (tCount[cRight] > 0) {  
            required--;  
        }  
        tCount[cRight]--;  
        right++;  
        while (required == 0) {  
            if (right - left < minLength) {  
                minLength = right - left;  
                start = left;  
            }  
            char cLeft = S.charAt(left);  
            tCount[cLeft]++;  
            if (tCount[cLeft] > 0) {  
                required++;  
            }  
            left++;  
        }  
    }  
    return minLength == Integer.MAX_VALUE ? "" : S.substring(start, start + minLength);  
}
这个主要是复用 tCount[] 以及引入了 required 这个量，从而快速判断是否存在包含关系。很好理解 required 即 t 所需的字母总数，当 required 为 0 时就可以快速判断出包含条件成立。 required 的增减需要实现判断 tCount[i] 是否大于 0，防止误增减。此外对于 tCount[i] 也有动态的增减过程。
# 普通数组
# 53 最大子数组和
比较简单的一题。有贪心与动态规划两个常见的方法，不过受到 560 和为 K 的子数组 这一题的启发，我用的是前缀和的方法，也是拿下了执行时间击败 100%。
public int maxSubArray(int[] nums) {  
    int length = nums.length;  
    int min = 0;  
    int sum = 0;  
    int max = nums[0];  
    for (int num : nums) {  
        sum += num;  
        max = Math.max(max, sum - min);  
        min = Math.min(min, sum);  
    }  
    return max;  
}
计算前缀和，先和当前维护的最小前缀和相减，判断是否最大，再判断是否更新最小前缀和。
为什么不是先判断更新最小前缀和呢？万一本题所有子数组和都小于 0，先更新的话，就会出现空数组导致和为 0 最大的错误情况了。
# 56 合并区间
很简单的一题。感觉重点就是怎么给二维数组排序。
public int[][] merge(int[][] intervals) {  
    int n = intervals.length;  
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  
    int[] array_now = intervals[0];  
    List<int[]> intervals_new = new ArrayList<>();  
    for (int i = 1; i < n; i++) {  
        if (intervals[i][0] <= array_now[1]) {  
            array_now[1] = Math.max(array_now[1], intervals[i][1]);  
        } else {  
            intervals_new.add(array_now);  
            array_now = intervals[i];  
        }  
    }  
    intervals_new.add(array_now);  
  
    return intervals_new.toArray(new int[intervals_new.size()][]);  
}
# 189 轮转数组
一开始我的思路挺简单粗暴的：本质上就是把数组后面一段拼接到前面去，直接算出切割位置切分拼接不就好了嘛。然后喜提执行用时击败 3.29%。
后来看了题解，发现一个非常巧妙的方法 —— 既然是要把后面的移到前面去，那我先把整个数组翻转，不就移动了吗？然后，再根据具体 k 值，将两段分别翻转过来，就弄好了。这样也降低了非常多的空间复杂度。
public void rotate(int[] nums, int k) {  
    k %= nums.length;  
    reverse(nums, 0, nums.length - 1);  
    reverse(nums, 0, k - 1);  
    reverse(nums, k, nums.length - 1);  
}  
  
public void reverse(int[] nums, int start, int end) {  
    while (start < end) {  
        int temp = nums[start];  
        nums[start] = nums[end];  
        nums[end] = temp;  
        start += 1;  
        end -= 1;  
    }  
}
# 238 除自身以外数组的乘积
题目明确写了不能用除法（悲）
前缀和 前缀积解法。为了最大化降低空间复杂度，我们先在 answer 数组里记录所有的前缀积。接着，再从后向前遍历 answer ，依次乘上后面的数字。
public int[] productExceptSelf(int[] nums) {  
    int n = nums.length;  
    int[] answer = new int[n];  
  
    answer[0] = 1;  // 第 0 个数字前面数字的积就视为 1
    for (int i = 1; i < n; i++) {  
        answer[i] = answer[i - 1] * nums[i - 1];  
    }  
    int R = 1;  
    for (int i = n - 1; i >= 0; i--) {  
        answer[i] *= R;  
        R *= nums[i];  
    }  
    return answer;  
}
# 41 缺失的第一个正数
非常抽象的一题。题干要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)，难度主要就出于此。
主要是利用哈希表的思想，不单独创建一个哈希表，而是将数组视为哈希表。由于特性，我们可以分析得到，最小不存在的正数范围必定为 [1, n+1] 。所以，我们先将所有小于 0 或者大于 n 的数转换成 n+1. 接着，对所有数字进行遍历，下标数对应的正负代表其是否出现过。
public int firstMissingPositive(int[] nums) {  
    int n = nums.length;  
    for (int i = 0; i < n; i++) {  
        if (nums[i] <= 0 || nums[i] > n) {  
            nums[i] = n + 1;  
        }  
    }  
    for (int i = 0; i < n; i++) {  
        int num = Math.abs(nums[i]);  
        if (num > n) {  
            continue;  
        }  
        nums[num - 1] = -Math.abs(nums[num - 1]);  
    }  
    for (int i = 0; i < n; i++) {  
        if (nums[i] > 0) {  
            return i + 1;  
        }  
    }  
    return n + 1;  
}
# 矩阵
# 73 矩阵置零
就像我以前说的，为了寻找意义而去寻找意义没有任何意义，那么我也认为为了优化而优化没有任何意义。所以这里就放最原始的两次遍历的解法。
public void setZeroes(int[][] matrix) {  
    int m = matrix.length, n = matrix[0].length;  
    boolean[] row = new boolean[m];  
    boolean[] col = new boolean[n];  
    for (int i = 0; i < m; i++) {  
        for (int j = 0; j < n; j++) {  
            if (matrix[i][j] == 0) {  
                row[i] = col[j] = true;  
            }  
        }  
    }  
    for (int i = 0; i < m; i++) {  
        for (int j = 0; j < n; j++) {  
            if (row[i] || col[j]) {  
                matrix[i][j] = 0;  
            }  
        }  
    }  
}
# 54 螺旋矩阵
总感觉我什么时候写过这一题……？算了不管了，我是比较喜欢人类一点的做法的，看了大佬的题解受益颇多。
主要就是使用方向矩阵，这个 CPL 老师也讲过。怎么记录已经走过的点呢？第一种方法就是改变原数组，走过的点置最大整数。第二种方法，找规律，比如一个 3 * 4 的矩阵，横向路径走过的路径长是 4_3_2，纵向 2_1，看得出来一个是 n 递减，一个是 m-1 递减。这样就可以清楚每次应该走多少步了。
public List<Integer> spiralOrder(int[][] matrix) {  
    int[][] dirs = <!--swig0-->;  
    int m = matrix.length, n = matrix[0].length;  
    List<Integer> ans = new ArrayList<>();  
    int i = 0, j = -1;  // 注意从 (0, -1) 开始
    int size = m * n;  
    m--;  
    for (int di = 0; ans.size() < size; di = (di + 1) % 4) {  
        if (di % 2 == 0) {  
            for (int k = 0; k < n; k++) {  
                j += dirs[di][1];  
                ans.add(matrix[i][j]);  
            }  
            n--;  
        } else {  
            for (int k = 0; k < m; k++) {  
                i += dirs[di][0];  
                ans.add(matrix[i][j]);  
            }  
            m--;  
        }  
    }  
    return ans;  
}
有一个很巧妙的点，就是 di = (di + 1) % 4 。每次加 1 在方向数组里就相当于转 90°，加到 3 了再加就变回 0。
# 48 旋转图像
核心要点：找规律
关键等式：
matrixnew[col][n−row−1]=matrix[row][col]matrix_{new}[col][n−row−1]=matrix[row][col]
四个一组旋转，对于整个矩形，只需要截取出四分之一的区域，进行四个一组的轮换即可。下面的四个坐标都是用上面那个等式推出来的。

Pasted image 20250722165554.png
public void rotate(int[][] matrix) {  
    int n = matrix.length;  
    for (int i = 0; i < n / 2; ++i) {  
        for (int j = 0; j < (n + 1) / 2; ++j) {  
            int temp = matrix[i][j];  
            matrix[i][j] = matrix[n - j - 1][i];  
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];  
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];  
            matrix[j][n - i - 1] = temp;  
        }  
    }  
}
# 240 搜索二维矩阵 II
一个特别巧妙的做法，主要还是充分利用了题面性质代码还特别简洁！
题干说：每行的元素从左到右升序排列，每列的元素从上到下升序排列。那么，我们的初始设为从矩阵右上角开始遍历。先明确性质：该处是此行的最大值，也是此列的最小值。
假设我们的目标值是 k，而矩阵右上角值为 n，当 n <k 时，代表了什么？代表这一行所有值都小于 k，那么，我们在接下来的遍历里可以将此行去除。而当 n> k 时，代表了什么？代表这一列所有值都大于 k，那么我们后面可以去除该列。
public boolean searchMatrix(int[][] matrix, int target) {  
    int m = matrix.length;  
    int n = matrix[0].length;  
    int x = 0;  
    int y = n - 1;  
    while (x < m && y >= 0) {  
        if (matrix[x][y] == target) {  
            return true;  
        }  
        if (matrix[x][y] > target) {  
            y--;  
        } else {  
            x++;  
        }  
    }  
    return false;  
}
通过更改遍历点坐标的方式简单地实现了上述去除行和列的操作。这个解法真的很清爽……
# 链表
# 106 相交链表
aywc 这不是我们数据结构考试的题目吗（）我记得我当时写的是遍历两个链表到尾结点，比较尾结点是不是相同。。不过当时题面应该只是需要给出能不能相交。
来看题，需要找出相交节点。我们设链表 A 非相交部分长度 x，链表 B 非相交部分长度 y，二者相交长度 z。一个等式： (x + z) + y = (y + z) + x 。
假设两个指针 a1a_1、b1b_1 分别从两个链表头出发，每次都前进一步，当 a1a_1 到尾部时，让它跳转到链表 B 的头部，b1b_1 同理。当二者相同时，此时即为链表相交的部分。
public class ListNode {  
    int val;  
    ListNode next;  
  
    ListNode(int x) {  
        val = x;  
        next = null;  
    }  
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {  
    ListNode a = headA;  
    ListNode b = headB;  
    while (a != b) {  
        a = a == null ? headB : a.next;  
        b = b == null ? headA : b.next;  
    }  
    return a;  
}
# 206 反转链表
以前做过。
public class ListNode {  
    int val;  
    ListNode next;  
  
    ListNode(int x) {  
        val = x;  
        next = null;  
    }  
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }  
    ListNode() {}  
}
public ListNode reverseList(ListNode head) {  
    ListNode prev = null;  
    ListNode curr = head;  
    ListNode next = null;  
    while (curr != null) {  
        next = curr.next;  
        curr.next = prev;  
        prev = curr;  
        curr = next;  
    }  
    return prev;  
}
简而言之就是记住前中后三个点，将中间点的指向改变即可。
# 234 回文链表
这个需要用到上面那个反转链表。
主要思路，就是找到链表中点，逆转后半部分，将后半部分与前半部分一一对比即可。
public ListNode reverseList(ListNode head) {  
    ListNode prev = null;  
    ListNode curr = head;  
    ListNode next = null;  
    while (curr != null) {  
        next = curr.next;  
        curr.next = prev;  
        prev = curr;  
        curr = next;  
    }  
    return prev;  
}  
  
public boolean isPalindrome(ListNode head) {  
    ListNode slow = head;  
    ListNode fast = head;  
    while (fast != null && fast.next != null) {  
        slow = slow.next;  
        fast = fast.next.next;  
    }  
    // 此时 slow 为链表中点
    ListNode secondHalf = reverseList(slow); // 逆转链表后半部分 
    while (secondHalf != null) {  // 注意循环条件 
        if (head.val != secondHalf.val) {  
            return false;  
        }  
        head = head.next;  
        secondHalf = secondHalf.next;  
    }  
    return true;  
}
# 141 环形链表
本题是判断链表是否是环形链表。介于常量内存的要求，我们有两个方法：
一个是标准做法快慢指针。A 指针每次走两步，B 指针每次走一步，若二者相遇则链表有环。
public boolean hasCycle(ListNode head) {  
    if (head == null) {  
        return false;  
    }  
    ListNode slow = head;  
    ListNode fast = head.next;  
    while (fast != null && fast.next != null) {  
        if (slow == fast) {  
            return true;  
        }  
        slow = slow.next;  
        fast = fast.next.next;  
    }  
    return false;  
}
一个是有点另类的但是很巧的，即走过一个指针就改变值，如遇到改变的那个值则有环。
public boolean hasCycle(ListNode head) {  
    if (head == null) {  
        return false;  
    }  
    while (head.next != null) {  
        if (head.val == Integer.MAX_VALUE) {  
            return true;  
        }  
        head.val = Integer.MAX_VALUE;  
        head = head.next;  
    }  
    return false;  
}
# 142 环形链表 II
上一题的升级版，要求找到入环点，并不允许改变链表内部的值（ban 掉了上面的方法二）。
还是用快慢指针，并且用到了佛洛依德判圈算法。另外这题 CPL 也出过的，不过嘛，CPL 改后的题面导致它有一个更简单的做法了……
public ListNode detectCycle(ListNode head) {  
    ListNode slow = head, fast = head;  
    while (fast != null && fast.next != null) {  
        slow = slow.next;  
        fast = fast.next.next;  
        if (fast == slow) { // 相遇  
            while (slow != head) { // 再走 a 步  
                slow = slow.next;  
                head = head.next;  
            }  
            return slow;  
        }  
    }  
    return null;  
}

Pasted image 20250814184056.png
即，根据数学运算得知，快慢指针相遇点的位置距离入环点距离即为 a，即头节点到入环点的距离。
# 2 两数相加
很惊讶于发现这一题我竟然有个去年 5.30 的提交记录，C 语言，12ms 超过了 0% 的人…… 当然，那个时候应该是备战转专业考试来找找手感的。
这一题常规做法就是模拟相加过程。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
    ListNode dummy = new ListNode(-1);  
    ListNode cur = dummy;  
    int carry = 0;  
    while (l1 != null || l2 != null) {  
        int a = l1 == null ? 0 : l1.val;  
        int b = l2 == null ? 0 : l2.val;  
        int sum = a + b + carry;  
        cur.next = new ListNode(sum % 10);  
        cur = cur.next;  
        carry = sum / 10;  
        if (l1 != null) {  
            l1 = l1.next;  
        }  
        if (l2 != null) {  
            l2 = l2.next;  
        }  
    }  
    if (carry != 0) {  
        cur.next = new ListNode(carry);  
    }  
    return dummy.next;  
}
# 19 删除链表的倒数第 N 个结点
很难得，自己立刻就想出来了执行时间最优的方案！关键点就是怎么快速确定倒数第 N 个结点是哪个，一次遍历的情况下，就得用前后指针了。
public ListNode removeNthFromEnd(ListNode head, int n) {  
    ListNode head1 = head;  
    ListNode dummy = head;  
    for (int i = 0; i < n; i++) {  
        dummy = dummy.next;  
    }  
    if (dummy == null) {  
        return head.next;  
    }  
    while (dummy.next != null) {  
        head = head.next;  
        dummy = dummy.next;  
    }  
    head.next = head.next.next;  
    return head1;  
}
# 24 两两交换链表中的节点
从这一题开始换成用 cpp 做。就是按规律交换，不过链表题真的好容易就绕晕了啊……
Pasted image 20250911220031.png
struct ListNode {  
    int val;  
    ListNode *next;  
    ListNode() : val(0), next(nullptr) {}  
    ListNode(int x) : val(x), next(nullptr) {}  
    ListNode(int x, ListNode *next) : val(x), next(next) {}  
};  
  
ListNode *swapPairs(ListNode *head) {  
    ListNode dummy(0, head);  
    ListNode *node0 = &dummy;  
    ListNode *node1 = head;  
    while (node1 && node1->next) {  
        ListNode *node2 = node1->next;  
        ListNode *node3 = node2->next;  
        node0->next = node2;  
        node2->next = node1;  
        node1->next = node3;  
        node0 = node1;  
        node1 = node3;  
    }  
    return dummy.next;  
}
# 25 K 个一组翻转链表
一道有点难度的 HRAD，主要是容易写成石山。
这题主要是得理清思路，不要把代码写的冗余。这个图解很清楚。。。不过说真的，感觉最后还是只能背代码了。
Pasted image 20250917230734.png
ListNode *reverseKGroup(ListNode *head, int k) {  
    ListNode dummy(0, head);  
    ListNode *pre = &dummy;  
    ListNode *start = head;  
    while (start) {  
        ListNode *next = start;  
        int count = 0;  
        while (next && count < k) {  
            next = next->next;  
            count++;  
        }  
        if (count < k) break;  
        ListNode *newHead = reverse(start, k);  
        pre->next = newHead;  
        start->next = next; // start is now the tail after reversal  
        pre = start;  
        start = next;  
    }  
    return dummy.next;  
}  
  
ListNode *reverse(ListNode *head, int k) {  
    ListNode *prev = nullptr;  
    ListNode *curr = head;  
    ListNode *next = nullptr;  
    while (k--) {  
        next = curr->next;  
        curr->next = prev;  
        prev = curr;  
        curr = next;  
    }  
    return prev;  
}
解释一下几个变量的含义：
start：目标翻转链表的头节点，翻转后会变成尾结点
next：目标翻转链表尾结点的后一个结点，翻转后需要将 start 和 next 相连
newHead：翻转后链表的头结点
pre：目标翻转链表头结点的前一个结点，翻转后需要将 pre 与 newHead 相连
# 138 随机链表的复制
比较有意思的一道题。首先是常规哈希表做法但是时间只击败了 21% 的人：
Node *copyRandomList(Node *head) {  
    unordered_map<Node *, Node *> cachedNode;  
    if (!head) return nullptr;  
    if (!cachedNode.count(head)) {  
        Node *node = new Node(head->val);  
        cachedNode[head] = node;  
        node->next = copyRandomList(head->next);  
        node->random = copyRandomList(head->random);  
    }  
    return cachedNode[head];  
}
接着便是神来之笔了：
Node *copyRandomList(Node *head) {  
    if (!head) return nullptr;  
    // 合并两个链表
    for (Node *cur = head; cur; cur = cur->next->next) {  
        Node *newNode = new Node(cur->val);  
        newNode->next = cur->next;  
        cur->next = newNode;  
    }  
    for (Node *cur = head; cur; cur = cur->next->next) {  
        if (cur->random) {  
            cur->next->random = cur->random->next; // 神来之笔  
        }  
    }  
    // 将两个链表拆开
    Node *newHead = head->next;  
    Node *cur = head;  
    while (cur->next) {  
        Node *temp = cur->next;  
        cur->next = temp->next;  
        cur = temp;  
    }  
    return newHead;  
}
# 148 排序链表
分治 + 递归
好久没写了，手感太生疏
简单来说，总体是个递归：排序过程是将链表一分为二，两边分别排序，然后 merge 合并。那么对于子链表排序，重复上述一分为二排序再合并，直到子链表为单节点，那么可以直接返回单节点。
ListNode *sortList(ListNode *head) {  
    if (head == nullptr || head->next == nullptr) {  
        return head;  
    }  
  
    ListNode *fast = head->next;  
    ListNode *slow = head;  
  
    while (fast != nullptr && fast->next != nullptr) {  
        fast = fast->next->next;  
        slow = slow->next;  
    }  
    ListNode *two = slow->next;  
    slow->next = nullptr;  
    return merge(sortList(head), sortList(two));  
}  
  
ListNode *merge(ListNode *a, ListNode *b) {  
    ListNode dummy(0);  
    ListNode *begin = &dummy;  
    ListNode *now = begin;  
    while (a != nullptr && b != nullptr) {  
        if (a->val <= b->val) {  
            now->next = a;  
            a = a->next;  
        } else {  
            now->next = b;  
            b = b->next;  
        }  
        now = now->next;  
    }  
    if (a != nullptr) {  
        now->next = a;  
    }  
    if (b != nullptr) {  
        now->next = b;  
    }  
    return begin->next;  
}
# 23 合并 K 个升序链表
依旧是分治的思想。解法和上一题相似，分治＋递归
ListNode *mergeKLists(vector<ListNode *> &lists)  
{  
    return mergeKLists(lists, 0, lists.size() - 1);  
}  
  
ListNode *mergeKLists(vector<ListNode *> &lists, int l, int r) {  
    if (l == r) {  
        return lists[l];  
    } else if (l > r) {  
        return nullptr;  
    }  
  
    int mid = (l + r) / 2;  
    return mergeTwo(mergeKLists(lists, l, mid), mergeKLists(lists, mid + 1, r));  
}  
  
ListNode *mergeTwo(ListNode *a, ListNode *b) {  
    ListNode dummy(0);  
    ListNode *begin = &dummy;  
    ListNode *now = begin;  
    while (a != nullptr && b != nullptr)  
    {  
        if (a->val <= b->val) {  
            now->next = a;  
            a = a->next;  
        } else {  
            now->next = b;  
            b = b->next;  
        }  
        now = now->next;  
    }  
    if (a != nullptr) {  
        now->next = a;  
    }  
    if (b != nullptr) {  
        now->next = b;  
    }  
    return begin->next;  
}
# 146 LRU 缓存
一道很 OO 的题目，感觉回到了计组。数据结构上就是哈希表 + 双向链表。
注意：cpp 中，用 unordered_map 结构而不是 map 结构，会快一点
struct LinkedNode {  
    int key, value;  
    LinkedNode *prev;  
    LinkedNode *next;  
  
    LinkedNode(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {};  
  
    LinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {};  
};  
  
class LRUCache {  
private:  
    unordered_map<int, LinkedNode *> mp;  
    LinkedNode *head;  
    LinkedNode *tail;  
    int size;  
    int capacity;  
  
public:  
    LRUCache(int capacity) : capacity(capacity), size(0) {  
        head = new LinkedNode();  
        tail = new LinkedNode();  
        head->next = tail;  
        tail->prev = head;  
    }  
  
    int get(int key) {  
        if (mp.count(key) == 0) {  
            return -1;  
        }  
        LinkedNode *a = mp[key];  
        moveToHead(a);  
        return a->value;  
    }  
  
    void put(int key, int value) {  
        if (mp.count(key) != 0) {  
            LinkedNode *a = mp[key];  
            a->value = value;  
            moveToHead(a);  
        } else {  
            LinkedNode *newNode = new LinkedNode(key, value);  
            addToHead(newNode);  
            mp[key] = newNode;  
            if (size < capacity) {  
                size++;  
            } else {  
                LinkedNode *removed = tail->prev;  
                mp.erase(removed->key);  
                deleteNode(removed);  
                delete removed;  
            }  
        }  
    }  
  
    void deleteNode(LinkedNode *a) {  
        a->prev->next = a->next;  
        a->next->prev = a->prev;  
    }  
  
    void addToHead(LinkedNode *a) {  
        a->prev = head;  
        a->next = head->next;  
        head->next->prev = a;  
        head->next = a;  
    }  
  
    void moveToHead(LinkedNode *a) {  
        deleteNode(a);  
        addToHead(a);  
    }  
};
std::map 和 std::unordered_map 是 C++ 中两种最常用的关联容器，它们的主要区别在于底层实现、性能和元素顺序。
以下是详细对比总结：
# 1. 核心区别对比表
特性std::mapstd::unordered_map
底层实现红黑树 (平衡二叉搜索树)哈希表 (Hash Table)
查找 / 插入 / 删除O(log⁡N)O(\log N) (稳定)O(1)O(1) (平均)，最坏 O(N)O(N)
元素顺序有序 (按 key 从小到大排序)无序 (看起来是随机的)
内存占用较小 (每个节点存指针和颜色位)较大 (需要维护哈希桶数组)
Key 的要求需要定义 < 运算符 (比较大小)需要定义 hash 函数和 == 运算符
# 2. 什么时候用哪个？
# ✅ std::unordered_map (首选，通常更快)
只要你不关心元素的顺序，只想快速地存取数据，就选它。
  • 场景：
    • 像 LRU 缓存这种只关心 key 是否存在、或者通过 key 取 value 的情况。
    • 统计单词出现的频率。
    • LeetCode 题目中要求时间复杂度为 O(1)O(1) 的查找。
  • 原因：它极其快，在绝大多数情况下比 map 快得多。
# ✅ std::map (特定场景使用)
当你需要利用顺序做一些操作时，必须选它。
  • 场景：
    • 按顺序遍历：比如你需要按学号从小到大输出学生信息。
    • 范围查找：比如查找 key 在 [10, 20] 之间的所有元素（利用 lower_bound 和 upper_bound ）。
    • Key 难以哈希：某些复杂对象（如 pair 或自定义结构体）作为 Key，写哈希函数很麻烦，但写 < 比较函数很简单时。
  • 原因：它自带排序功能。
# 3. 代码示例：为什么 map 会慢？
map 用的是树结构，每次插入或查找都要从树根走到叶子，层数是 log⁡N\log N。
unordered_map 直接计算哈希值定位内存地址，一步到位。
// 假设有 100 万 个数据
// std::map: 
// 查找一次大约需要计算 log2 (1000000) ≈ 20 次比较
map.find(key); 
// std::unordered_map:
// 查找一次计算 1 次哈希值，直接定位
unordered_map.find(key);
总结：在你的 LRU 题目中，因为只要快速存取（Get/Put），完全不需要排序，所以用 map 就像是用牛刀杀鸡（而且这把牛刀动作还慢），改成 unordered_map 后性能直接起飞。
# 二叉树
# 94 二叉树的中序遍历
数据结构已经忘光了。中序遍历是什么？能吃吗？
什么是二叉树的中序遍历：按照访问左子树 —— 根节点 —— 右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。
递归的做法符合人类直觉。至于使用栈的迭代方法，不喜欢，就不写了。
struct TreeNode  
{  
    int val;  
    TreeNode *left;  
    TreeNode *right;  
    TreeNode() : val(0), left(nullptr), right(nullptr) {}  
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}  
};  
  
vector<int> inorderTraversal(TreeNode *root)  
{  
    vector<int> res;  
    inOrder(root, res);  
    return res;  
}  
  
void inOrder(TreeNode *root, vector<int>& res) {  
    if (!root) {  
        return;  
    }  
    inOrder(root->left, res);  
    res.push_back(root->val);  
    inOrder(root->right, res);  
}
# 104 二叉树的最大深度
感觉像做过的，反正很顺手写出来了。写完才知道原来我写的是什么深度优先搜索。
int maxDepth(TreeNode *root)  
{  
    if (root == nullptr) {  
        return 0;  
    }  
    return 1 + max( maxDepth(root->left), maxDepth(root->right));  
}
还有个广度优先搜索的方法，但是太复杂了。
[[DFS 与 BFS]]
# 226 翻转二叉树
依旧是递归 + BFS，轻松拿下
TreeNode *invertTree(TreeNode *root)  
{  
    if (root != nullptr)  
    {  
        invertTree(root->left);  
        invertTree(root->right);  
        TreeNode *temp = root->left;  
        root->left = root->right;  
        root->right = temp;  
        return root;  
    } else {  
        return nullptr;  
    }  
}
# 101 对称二叉树
递归依然比迭代好写。。。
bool isSymmetric(TreeNode *root)  
{  
    return check(root->left, root->right);  
}  
bool check(TreeNode *left, TreeNode *right)  
{  
    if (!left && !right)  
    {  
        return true;  
    }  
    else if (!right || !left)  
    {  
        return false;  
    }  
  
    return left->val == right->val && check(left->left, right->right) && check(left->right, right->left);  
}
如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
因此，该问题可以转化为：两个树在什么情况下互为镜像？
如果同时满足下面的条件，两个树互为镜像：
  • 它们的两个根结点具有相同的值
  • 每个树的右子树都与另一个树的左子树镜像对称
    我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移，p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。
# 543 二叉树的直径
这题主要是围绕着深度和直径的关系展开。
以某个节点为根的直径，它的最大值是左子结点的深度加右子节点的深度。
但是问题在于，整个树的直径，是不一定以最上方根节点为根的。
所以我们需要遍历所有节点，依次算出值然后比较，获得最大值。
也就是说一个递归函数干两件事情：返回当前节点的深度，以及算出本节点为根的直径，进行比较。
深度的话之前写过，这个好算。
int ans;  
int depth(TreeNode *root) {  
    if (root == nullptr) {  
        return 0;  
    }  
    int leftd = depth(root->left);  
    int rightd = depth(root->right);  
  
    ans = max(ans, leftd + rightd);  
    return max(leftd, rightd) + 1;  
}  
  
  
int diameterOfBinaryTree(TreeNode *root)  
{  
    ans = 0;  
    depth(root);  
    return ans;  
}
# 102 二叉树的层序遍历
class Solution {  
public:  
    vector<vector<int>> ans;  
  
    vector<vector<int>> levelOrder(TreeNode *root) {  
        if (root == nullptr) {  
            return ans;  
        }  
  
        vector<TreeNode *> solve_now;  
        solve_now.push_back(root);  
        ans.push_back(vector<int>(1, root->val));  
  
        bool if_go = true;  
        while (if_go) {  
            vector<int> number;  
            vector<TreeNode *> newnext;  
            bool if_break = true;  
  
            for (TreeNode *ptr: solve_now) {  
                if (ptr->left != nullptr) {  
                    newnext.push_back(ptr->left);  
                    number.push_back(ptr->left->val);  
                    if_break = false;  
                }  
                if (ptr->right != nullptr) {  
                    newnext.push_back(ptr->right);  
                    number.push_back(ptr->right->val);  
                    if_break = false;  
                }  
            }  
  
            if (if_break) {  
                break;  
            }  
  
            ans.push_back(number);  
            swap(solve_now, newnext);  
        }  
        return ans;  
    }  
};
我自己写的没有用队列，不过用队列更规范。然后我这个想时间复杂度上去的话，最后需要用 swap 交换指针达到最快速度，直接拷贝太慢。
标准一点的用队列：
#include <vector>
#include <queue>
using namespace std;
// TreeNode 定义保持不变...
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        // 作为局部变量，避免被其他测试用例污染
        vector<vector<int>> ans; 
        if (root == nullptr) {
            return ans;
        }
        // 核心：只维护一个队列
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            // 在这一层开始前，队列里的元素数量就是这一层的节点总数
            int currentLevelSize = q.size(); 
            vector<int> currentLevelValues;
            
            // 预分配内存（可选优化，进一步减少动态扩容耗时）
            currentLevelValues.reserve(currentLevelSize);
            // 精准地把当前层的节点处理完
            for (int i = 0; i < currentLevelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                currentLevelValues.push_back(node->val);
                // 让下一层的节点接着排队，它们不会干扰当前层的循环，因为循环次数已经固定了
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            
            // 当前层处理完毕，装入结果
            ans.push_back(std::move(currentLevelValues)); 
        }
        return ans;
    }
};
# 108 将有序数组转换为二叉搜索树
需要明确一下二叉搜索树的概念，然后用递归就好做了。
class Solution {  
public:  
    TreeNode* sortedArrayToBST(vector<int>& nums) {  
        return sorted(nums, 0, nums.size() - 1);  
    }  
  
    TreeNode *sorted(vector<int>& nums, int begin, int end) {  
        if (begin > end)  
        {  
            return nullptr;  
        }  
        int mid = (begin + end) / 2;  
        TreeNode *newNode = new TreeNode(nums[mid]);  
        newNode->left = sorted(nums, begin, mid - 1);  
        newNode->right = sorted(nums, mid + 1, end);  
        return newNode;  
    }  
};
# 98 验证二叉搜索树
动态调整范围限制。注意数据范围，是 long long 类型
bool isValidBST(TreeNode *root)  
{  
    return isVaild(root, LLONG_MIN, LLONG_MAX);  
}  
  
bool isVaild(TreeNode *root, long long min, long long max)  
{  
    if (root == nullptr)  
    {  
        return true;  
    }  
    if (root->val <= min || root->val >= max)  
    {  
        return false;  
    }  
    return isVaild(root->left, min, root->val) && isVaild(root->right, root->val, max);  
}
# 230 二叉搜索树中第 K 小的元素
前面刚说中序遍历，我不想写栈的写法，这下来了，最好就是迭代＋栈。
粗略来讲就是先向左一路走到底，获得最小值，计数减一后转向其右子树，再一路向左，获得最小值计数减一，如此重复。
int kthSmallest(TreeNode *root, int k)  
{  
    stack<TreeNode *> st;  
    while (root != nullptr || st.size() > 0)  
    {  
        while (root != nullptr)  
        {  
            st.push(root);  
            root = root->left;  
        }  
  
        root = st.top();  
        st.pop();  
  
        k--;  
        if (k == 0)  
        {  
            break;  
        }  
  
        root = root->right;  
    }  
  
    return root->val;  
}
# 199 二叉树的右视图
只要会层序遍历那一题，这一题就非常好做了。本质上就是把层序遍历每一行的最后一个元素拿出来。
vector<int> rightSideView(TreeNode *root)  
{  
    vector<int> ans;  
    queue<TreeNode *> q;  
    if (root == nullptr) {  
        return ans;  
    }  
    q.push(root);  
    while (q.size() > 0)  
    {  
        int nowSize = q.size();  
        for (int i = 0; i < nowSize; i++)  
        {  
            TreeNode *a = q.front();  
            q.pop();  
            if (a->left != nullptr)  
            {  
                q.push(a->left);  
            }  
            if (a->right != nullptr)  
            {  
                q.push(a->right);  
            }  
            if (i == nowSize - 1) {  
                ans.push_back(a->val);  
            }  
        }  
    }  
    return ans;  
}
# 114 二叉树展开为链表
感觉只要会前序遍历就很好做。前序遍历得到一个数组然后依次连起来就行。
void flatten(TreeNode *root) {  
    vector<TreeNode *> nodes;  
    preorder(nodes, root);  
    nodes.push_back(nullptr);  
    for (int i = 0; i < nodes.size() - 1; i++) {  
        nodes[i]->left = nullptr;  
        nodes[i]->right = nodes[i + 1];  
    }  
}  
  
void preorder(vector<TreeNode *> &nodes, TreeNode *root) {  
    if (root == nullptr) {  
        return;  
    }  
  
    nodes.push_back(root);  
    preorder(nodes, root->left);  
    preorder(nodes, root->right);  
}
# 105 从前序与中序遍历构造二叉树
你让我脑动构造，我会觉得很容易。但是写成代码这复杂的边界条件就有点难受了。
另外，前序 + 后序遍历无法构造二叉树。当只有前序和后序时，虽然我们知道谁是根，但无法确定一个子节点到底是左孩子还是右孩子。
class Solution  
{  
private:  
    unordered_map<int, int> index;  
public:  
    TreeNode *build(vector<int> &preorder, vector<int> &inorder, int preleft, int preright, int inleft, int inright)  
    {  
        if (preleft > preright || inleft > inright)  
        {  
            return nullptr;  
        }  
        int root = preorder[preleft];  
        int root_in_index = index[root];  
        TreeNode *newNode = new TreeNode(root);  
          
        int left_num = root_in_index - inleft;  
  
        newNode->left = build(preorder, inorder, preleft + 1, preleft + left_num, inleft, root_in_index - 1);  
        newNode->right = build(preorder, inorder, preleft + left_num + 1, preright, root_in_index + 1, inright);  
  
        return newNode;  
    }  
  
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)  
    {  
        int n = inorder.size();  
        for (int i = 0; i < n; ++i)  
        {  
            index[inorder[i]] = i;  
        }  
        return build(preorder, inorder, 0, n - 1, 0, n - 1);  
    }  
};
# 437 路径总和 III
和 53 最大子数组和是相似的思路，前缀和。
不过问题在于，数组是线性的，而二叉树会分叉，那么这个该怎么解决呢？
个人觉得，这边用的像是回溯的思想。
class Solution  
{  
private:  
    unordered_map<long long, int> mp;  
  
public:  
    int dfs(TreeNode *root, long long cur, int targetSum)  
    {  
        if (!root)  
        {  
            return 0;  
        }  
        cur += root->val;  // 累计前缀和
        int ans = 0;  
        if (mp.count(cur - targetSum))  
        {  
            ans += mp[cur - targetSum];  
        }  
        mp[cur]++;  // 和 53 一样，先判断有没有，再给自身加一
        ans += dfs(root->left, cur, targetSum);  
        ans += dfs(root->right, cur, targetSum);  
        mp[cur]--;   // 关键在这！下一步是返回，也即离开本节点回到父节点，那么要把自身状态清除
        return ans;  
    }  
  
    int pathSum(TreeNode *root, int targetSum)  
    {  
        mp[0] = 1;  
        return dfs(root, 0, targetSum);  
    }  
};
# 236 二叉树的最近公共祖先
首先看了灵神的方法，只能说略懂，有点感觉，但不多。
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  
    if (!root || root == p || root == q)  
    {  
        return root;  
    }  
    TreeNode *leftfind = lowestCommonAncestor(root->left, p, q);  
    TreeNode *rightfind = lowestCommonAncestor(root->right, p, q);  
    if (leftfind && rightfind)  
    {  
        return root;  
    }  
    return leftfind ? leftfind : rightfind;  
}
它本质上是一个 “向上汇报” 的机制：对于任何一个节点，它跑去问左子树 “你有没有看到 p 或 q？”，又跑去问右子树 “你有没有看到 p 或 q？”。如果左边说看到了，右边也说看到了，那说明 p 和 q 分居在我的两侧，那我（当前节点）绝对就是它俩的最近公共祖先啦！
然后换了个方法，略慢，但是很直观：
记录所有节点的父节点，然后依次从下往上遍历，判断哪个点两个人同时都经过了。
unordered_map<TreeNode *, TreeNode *> mp;  
unordered_set<TreeNode *> visit;  
void dfs(TreeNode *root) {  
    if (root->left != nullptr)  
    {  
        mp[root->left] = root;  
        dfs(root->left);  
    }  
    if (root->right != nullptr)  
    {  
        mp[root->right] = root;  
        dfs(root->right);  
    }  
}  
  
TreeNode* lowestCommonAncestor2(TreeNode* root, TreeNode* p, TreeNode* q) {  
    mp[root] = nullptr;  
    dfs(root);  
    while (p != nullptr)  
    {  
        visit.insert(p);  
        p = mp[p];  
    }  
  
    while (q != nullptr)  
    {  
        if (visit.count(q))  
        {  
            return q;  
        }  
        q = mp[q];  
    }  
  
    return nullptr;  
}
# 124 二叉树中的最大路径和
本题解法分为两部分：求该节点的贡献值以及求以本节点为根的最大路径和。
贡献值：以本节点为向上遍历的终点，所能够得到的最大值。那么，求以本节点为根的最大路径和，也即左右节点贡献值相加再加上本节点值（ps：左右节点小于 0 的贡献值不加，也即直接不经过）
那么用递归，一直递归到最底层，然后依次向上返回得到每个节点的贡献值。
int ans  = INT_MIN;  
int maxGain(TreeNode *root) {  
    if (!root)  
    {  
        return 0;  
    }  
    int leftGain = max(maxGain(root->left), 0);  
    int rightGain = max(maxGain(root->right), 0);  
  
    ans = max(ans, leftGain + rightGain + root->val);  
  
    return root->val + max(leftGain, rightGain);  
}  
int maxPathSum(TreeNode* root) {  
    maxGain(root);  
    return ans;  
}
# 图论
# 200 岛屿数量
用的 dfs（一开始写成 dps 了说的是），一开始速度非常缓慢，但是后来发现是因为用了双重 vector 导致的，火速改成正常二维数组放到成员变量里了。
是递归，由一个 1 出发把周围的 1 全部变成 0，然后总体是所有点全遍历。
class Solution {  
private:  
    int height;  
    int width;  
    const int a[4][2] = <!--swig1-->;  
public:  
    void dfs(vector<vector<char>> &grid, int x, int y) {  
        grid[x][y] = '0';  
        for (int i = 0; i < 4; ++i) {  
            int xnew = x + a[i][0];  
            int ynew = y + a[i][1];  
            if (xnew >= 0 && xnew < height && ynew >= 0 && ynew < width) {  
                if (grid[xnew][ynew] == '1') {  
                    dfs(grid, xnew, ynew);  
                }  
            }  
        }  
    }  
  
    int numIslands(vector<vector<char>> &grid) {  
        height = grid.size();  
        width = grid[0].size();  
        int sum = 0;  
        for (int i = 0; i < height; ++i) {  
            for (int j = 0; j < width; ++j) {  
                if (grid[i][j] == '1') {  
                    ++sum;  
                    dfs(grid, i, j);  
                }  
            }  
        }  
        return sum;  
    }  
};
# 994 腐烂的橘子
典型的 BFS，解法还是比较简单的。
class Solution  
{  
private:  
    int fang[4][2] = <!--swig2-->;  
  
public:  
    int orangesRotting(vector<vector<int>> &grid)  
    {  
        vector<pair<int, int>> fu_orange;  
        int fresh_count = 0;  
        int n = grid.size();  
        int m = grid[0].size();  
        for (int i = 0; i < n; i++)  
        {  
            for (int j = 0; j < m; j++)  
            {  
                if (grid[i][j] == 1)  
                {  
                    fresh_count++;  
                }  
                else if (grid[i][j] == 2)  
                {  
                    fu_orange.emplace_back(i, j);  
                }  
            }  
        }  
        int ans = 0;  
        while (fresh_count && fu_orange.size() > 0)  
        {  
            ans++;  
            vector<pair<int, int>> next;  
            for (auto& [x, y] : fu_orange)  
            {  
                for (auto di : fang)  
                {  
                    int xnew = x + di[0];  
                    int ynew = y + di[1];  
                    if (xnew < n && xnew >= 0 && ynew < m && ynew >= 0 && grid[xnew][ynew] == 1)  
                    {  
                        grid[xnew][ynew] = 2;  
                        fresh_count--;  
                        next.emplace_back(xnew, ynew);  
                    }  
                }  
            }  
            fu_orange = move(next);  
        }  
        return fresh_count == 0 ? ans : -1;  
    }  
};
三个需要注意的点：
  • emplace_back 是啥？它和 push_back 有什么区别？
    • 它的功能和 push_back 几乎一样，但在底层操作和性能上更优秀。
  • pair 是个什么数据类型？
    • 把两个不同（或相同）类型的数据绑定在一起，变成一个单一的对象。
    • 它内部有两个公开的成员变量： .first 和 .second 。如果用传统写法，你可能会这样写： int current_x = fu_orange[0].first; 。
  • auto& [x, y] : fu_orange 这是啥意思？
    • 首先是 基于范围的 for 循环 (Range-based for loop)，其次是 C++17 引入的杀手级特性 —— 结构化绑定 (Structured Binding)。
    • 有了 结构化绑定 [x, y] ：你相当于告诉编译器，“我知道从 fu_orange 里拿出来的东西是个包含了两个元素的 pair ，请直接帮我把第一个元素命名为 x ，第二个元素命名为 y ”。
    • auto& ： auto 让编译器自己推导类型（这里推导出来就是 int），而 & 表示引用。直接引用原数据，避免了把坐标值再复制一遍的开销。
# 207 课程表
第一个是好懂一点的 bfs 做法。使用拓扑排序。
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 1. 准备阶段：初始化入度数组和邻接表（依赖字典）
        //inDegree 记录每门课有几个 “前置门槛”
        vector<int> inDegree(numCourses, 0);
        //adj 记录学完某门课后，能解锁哪些 “后续课程”
        vector<vector<int>> adj(numCourses);
        for (const auto& pre : prerequisites) {
            int course = pre[0];     // 想要修的课
            int preCourse = pre[1];  // 必须先修的课
            
            inDegree[course]++;                //course 的门槛 +1
            adj[preCourse].push_back(course);  // 记录 preCourse 可以解锁 course
        }
        // 2. 寻找突破口：把所有毫无门槛的课（入度为 0）放进队列
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        // 3. 开始 BFS 闯关
        int count = 0; // 记录我们成功修完了几门课
        
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            count++; // 顺利修完一门！
            // 遍历这门刚修完的课所能解锁的所有后续课程
            for (int nextCourse : adj[current]) {
                inDegree[nextCourse]--; // 既然前置课修完了，后续课的门槛就减 1
                
                // 如果门槛降到 0 了，说明它的前置全修完了，下学期就能上
                if (inDegree[nextCourse] == 0) {
                    q.push(nextCourse);
                }
            }
        }
        // 4. 结算验收
        // 如果修完的课等于总课程数，说明没有死循环，顺利毕业
        return count == numCourses;
    }
};
然后是 bfs 的递归实现，核心思想就是 “三色标记法”。它不需要像 BFS 那样去统计 “入度”，而是直接顺着依赖关系往下找，看看会不会 “撞见自己”。
我们给每一门课设定三种状态（用一个数组 visited 来存）：
  • 0（未访问）： 这门课还没查过。
  • 1（访问中）： 正在排查这门课的后续路线。如果在这条路线上，又碰到了状态为 1 的课，说明发现死循环了！
  • 2（已安全）： 这门课以及它的所有后续路线都查完了，没发现任何问题，是安全的。
#include <vector>
using namespace std;
class Solution {
private:
    vector<vector<int>> adj; // 邻接表，存依赖关系
    vector<int> visited;     // 记录每门课的状态（0：未查，1：排查中，2：安全）
    bool isValid = true;     // 记录是否能修完（如果没有死循环就是 true）
    // DFS 核心逻辑
    void dfs(int current) {
        // 1. 一进来，先把当前这门课标记为 “排查中”（状态 1）
        visited[current] = 1;
        // 2. 顺藤摸瓜，查这门课能解锁的所有后续课程
        for (int nextCourse : adj[current]) {
            if (visited[nextCourse] == 0) {
                // 如果后续课程还没查过，就递归进去接着查
                dfs(nextCourse);
                // 如果查出死循环了，赶紧撤退，不用再往下看了
                if (!isValid) return; 
            } 
            else if (visited[nextCourse] == 1) {
                // 【抓到死循环！】如果后续课程正在 “排查中”，说明绕了一圈又回来了
                isValid = false;
                return;
            }
            // 注意：如果 visited [nextCourse] == 2，说明那条路之前已经验证过绝对安全，直接跳过即可
        }
        // 3. 所有后续路线都查完了，没毛病，把当前课标记为 “已安全”（状态 2）
        visited[current] = 2;
    }
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 初始化数据结构
        adj.resize(numCourses);
        visited.resize(numCourses, 0);
        // 构建邻接表 (前置课程 -> 后续课程)
        for (const auto& pre : prerequisites) {
            adj[pre[1]].push_back(pre[0]); 
        }
        // 遍历每一门课，作为起点开始排查
        for (int i = 0; i < numCourses && isValid; i++) {
            // 只从还没查过的课开始走
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        // 最后返回判断结果
        return isValid;
    }
};
# 回溯
# 46 全排列
软工二就写过这题好像，但是当时看不懂那个 swap 的方法，太乱了。我觉得我就舍弃这个空间复杂度再开个状态数组吧。
几个优化的点：
  • 这道题状态数组比起用 vector<bool> ，用 vector<int> 更快。似乎是因为 CPU 没法直接修改数组导致的？
  • 不要用 for 循环初始化状态数组，直接 vector<int> isused(nums.size(), 0) 。
class Solution {  
private:  
    vector<vector<int>> res;  
  
public:  
    void backtrack(vector<int> &nums, vector<int> &path, vector<int> &isused) {  
        if (nums.size() == path.size()) {  
            res.push_back(path);  
            return;  
        }  
        for (int i = 0; i < nums.size(); ++i) {  
            if (isused[i] == 1) {  
                continue;  
            }  
            path.push_back(nums[i]);  
            isused[i] = 1;  
            backtrack(nums, path, isused);  
            path.pop_back();  
            isused[i] = 0;  
        }  
    }  
  
    vector<vector<int>> permute(vector<int> &nums) {  
        vector<int> path;  
        vector<int> isused(nums.size(), 0);  
        backtrack(nums, path, isused);  
        return res;  
    }  
};
回溯法：
在全排列的底层逻辑里，永远只有三个核心要素：
  1. 路径（已经写好的剧本）：比如目前出场顺序是 [A] 。
  2. 选择列表（还在后台等候的演员）：此时还剩下 B 和 C 。
  3. 结束条件（大结局）：当三个演员全出场了（路径长度等于原数组长度），这本小说的其中一个结局就写完了，把它装订成册（存入最终的二维数组中）。
我们来看看代码在物理世界里到底是怎样一步步执行的。核心全在一个极其精妙的 for 循环里。为了防止一个演员分身出场，我们还需要一个 used 数组（布尔型）来记录谁已经在舞台上了。
//res 是存所有大结局的全局变量
vector<vector<int>> res; 
void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used) {
    // 1. 触发大结局：剧本长度等于演员总数
    if (path.size() == nums.size()) {
        res.push_back(path); // 把这个大结局存档
        return; // 剧终，准备时光倒流，退回上一层
    }
    // 2. 站在岔路口，看着所有演员
    for (int i = 0; i < nums.size(); ++i) {
        // 如果这个演员已经在舞台上了，跳过他
        if (used[i]) continue;
        //---- 下面是回溯的真正灵魂，被称为 “做选择” 与 “撤销选择” ----
        // 【做选择】：决定让你上场！
        path.push_back(nums[i]); // 把演员写进当前剧本
        used[i] = true;          // 给他贴上 “已上场” 的标签
        // 【进入平行宇宙】：带着现在的剧本，走向下一步去安排下一个出场的人
        backtrack(nums, path, used);
        // 【时光倒流（恢复现场）】：
        // 当上面的 backtrack 执行完 return 后，意味着那个平行宇宙的结局已经打出来了。
        // 现在我们要退回到做选择之前的状态，也就是把刚刚上场的演员强行拽下来！
        path.pop_back();         // 从剧本里划掉他的名字
        used[i] = false;         // 撕掉他的 “已上场” 标签，让他重新回到后台待命
    }
}
重点感受一下最后那两行 “时光倒流” 的代码（ pop_back 和 used[i] = false ）。
假设你没有这两行代码。 当你顺着分支一路写下 [A, B, C] 这个结局后，程序执行 return 退回到了第二步（刚选完 A 和 B 的那个时刻）。 如果你不把 C 从剧本里删掉，也不撕掉 C 的 “已上场” 标签，那你的剧本依然定死在 [A, B, C] 。当你想尝试让 C 在第二个出场时，系统会告诉你：“C 的标签还是 true 呢，他不能出场。” 你的整个逻辑就彻底卡死了。
“吃后悔药”，就是回溯算法与普通深度优先搜索（DFS）最大的分水岭。你在深入下一层之前拿走了什么，从下一层退回来的时候，就必须原封不动地还回去，不留一丝痕迹。
变种：47 全排列 II
现在可能出现重复元素了！但是只需要加两个步骤即可解决：
①先对数组排序
②增加一个判断： if (i > 0 && nums[i] == nums[i - 1] && isused[i - 1] == 0)
这个判断意为：如果上一个在这个位置上推演的是与自己一样的数字，那么跳过这次推演。
问题在于为什么是 isused[i - 1] == 0 ，我的理解是本身循环最后就是让数字退场换到下一个数字，这个时候必然是不在场状态。
这就是剪枝：跳过不必要的步骤。
class Solution  
{  
private:  
    vector<vector<int>> res;  
public:  
    void backtrack(vector<int> &nums, vector<int> &path, vector<int> &isused)  
    {  
        if (nums.size() == path.size())  
        {  
            res.push_back(path);  
            return;  
        }  
        for (int i = 0; i < nums.size(); ++i)  
        {  
  
            if (isused[i])  
            {  
                continue;  
            }  
            if (i > 0 && nums[i] == nums[i - 1] && isused[i - 1] == 0)  
            {  
                continue;  
            }  
            path.push_back(nums[i]);  
            isused[i] = 1;  
            backtrack(nums, path, isused);  
            path.pop_back();  
            isused[i] = 0;  
        }  
    }  
    vector<vector<int>> permuteUnique(vector<int> &nums)  
    {  
        sort(nums.begin(), nums.end());  
        vector<int> path;  
        vector<int> isused(nums.size(), 0);  
        backtrack(nums, path, isused);  
        return res;  
    }  
};

持续更新……

 更新于   阅读次数  次
请我喝[茶]~(￣▽￣)~*
北沐清 微信支付
微信支付
北沐清 支付宝
支付宝