Leetcode Hot 100

哈希

两数之和

 0class Solution {
 1    public int[] twoSum(int[] nums, int target) {
 2        HashMap<Integer,Integer> map = new HashMap<>();
 3        for(int i = 0; i < nums.length; i ++){
 4            int a = nums[i];
 5            if(map.containsKey(target - a)){
 6                return new int[] {i,map.get(target - a)};
 7            }
 8            map.put(a,i);
 9        }
10        return null;
11    }
12}

$a + b = c$ 题目类型，因为 $b = c - a$，所以遍历 a，查询 b 即可。
使用哈希表以 $O(1)$ 复杂度查询。

字母异位词分组

 0class Solution {
 1    public List<List<String>> groupAnagrams(String[] strs) {
 2        HashMap<String, List<String>> hashMap = new HashMap<>();
 3        for (String str : strs) {
 4            // 转为字符数组排序
 5            char[] array = str.toCharArray();
 6            Arrays.sort(array);
 7            // 转为String为key，做判断
 8            String key = Arrays.toString(array);
 9            // 判断是否存在该单词
10            List<String> ans = hashMap.getOrDefault(key, new ArrayList<>());
11            ans.add(str);
12            hashMap.put(key,ans);
13        }
14        // 结果集
15        return new ArrayList<List<String>>(hashMap.values());
16    }
17}

将字符串排序后作为 key，从而得到字母异位词分组
Collection<T> values = hashMap.values()，list.addAll(Collection<? extends E> c)

最长连续序列

 0class Solution {
 1    public int longestConsecutive(int[] nums) {
 2        Set<Integer> set = new HashSet<>();
 3        // 去重
 4        for(int num : nums){
 5            set.add(num);
 6        }
 7        int maxL = 0;
 8        //x-1 的序列长度 >> x 的序列长度
 9        for(int x : set){
10            if(set.contains(x - 1)){
11                continue;
12            }else{
13                int curL = 1;
14                while(set.contains(x + 1)){
15                    curL ++;
16                    x ++;
17                }
18                maxL = Math.max(maxL,curL);
19            }
20        }
21        return maxL;
22    }
23}

题解
哈希去重，如果哈希表存在 x - 1，那么以 x - 1 开始的数字序列长度一定大于 x。

双指针

移动零

 0class Solution {
 1    public void moveZeroes(int[] nums) {
 2        int head = 0;
 3        int tail = 0;
 4        // 将不为0的num[tail]依次插入num[head]
 5        while (tail < nums.length) {
 6            if (nums[tail] != 0) {
 7                int temp = nums[head];
 8                nums[head] = nums[tail];
 9                nums[tail] = temp;
10                head++;
11            }
12            tail ++;
13        }
14    }
15}

参考栈的设计，不为 0 的元素依次入栈

盛最多水的容器

 0class Solution {
 1    public int maxArea(int[] height) {
 2        int left = 0;
 3        int right = height.length - 1;
 4        int area = -1;
 5        while(left < right) {
 6            area = Math.max(area,(right - left) * Math.min(height[left],height[right]));
 7            // 移动短板
 8            if(height[left] >= height[right]){
 9                right --;
10            }else{
11                left ++;
12            }
13        }
14        return area;
15    }
16}

题解
若向内移动短板，水槽的短板 min(h[left],h[right]) 可能变大，因此下个水槽的面积可能增大。
若向内移动长板，水槽的短板 min(h[left],h[right]) 不变或变小，因此下个水槽的面积一定变小。

三数之和

 0class Solution {
 1    public List<List<Integer>> threeSum(int[] nums) {
 2        Arrays.sort(nums);
 3        List<List<Integer>> res = new ArrayList<>();
 4        // a + b + c = sum
 5        for(int i = 0; i < nums.length - 2; i++) {
 6            int a = nums[i];
 7            // 去重
 8            if(i > 0 && nums[i] == nums[i - 1]) continue;
 9            // 双指针枚举[i + 1, nums.length]中元素
10            int l = i + 1;
11            int r = nums.length - 1;
12            while(l < r){
13                int sum = a + nums[l] + nums[r];
14                if(sum > 0){
15                    while(l < r && nums[r] == nums[--r]);
16                }else if(sum < 0) {
17                    while(l < r && nums[l] == nums[++l]);
18                }else{
19                    List<Integer> ans = new ArrayList<>();
20                    ans.add(a);
21                    ans.add(nums[l]);
22                    ans.add(nums[r]);
23                    res.add(ans);
24                    // 去重
25                    while(l < r && nums[r] == nums[--r]);
26                    while(l < r && nums[l] == nums[++l]);
27                }
28            }
29        }
30        return res;
31    }
32}

题解
双指针 l , r 交替向中间移动，记录 nums[i] + nums[l] + nums[r] == 0 的 l , r 组合。
通过排序，$a+b+c=sum$ 中，sum 的值可以通过移动 l , r 指针控制。
排序后，nums[i-1]得到的(i-1,l,r)结果一定包含了nums[i]的结果，从而解决重复。

接雨水

 0class Solution {
 1    public int trap(int[] height) {
 2        // maxL[i]为左边柱子的最大高度，包括本身
 3        int[] maxL = new int[height.length]; 
 4        // maxL[i]为右边柱子的最大高度，包括本身
 5        int[] maxR = new int[height.length]; 
 6        maxL[0] = height[0];
 7        maxR[height.length - 1] = height[height.length - 1];
 8        for (int i = 1; i < height.length; i++) {
 9            maxL[i] = Math.max(maxL[i - 1], height[i]);
10        }
11        for (int i = height.length - 2; i >= 0; i --) {
12            maxR[i] = Math.max(maxR[i + 1], height[i]);
13        }
14        // 接的雨水为当前柱子i Min{maxL[i],maxR[i]} - height[i]
15        int cnt = 0;
16        for(int i = 1; i < height.length - 1; i++) {
17            int res = Math.min(maxL[i - 1],maxR[i + 1]) - height[i];
18            cnt += Math.max(res, 0);
19        }
20        return cnt;
21    }
22}

题解
木桶理论，dp 的代码更好理解。
对于每一列可以接的雨水取决于左右两边最高的短木板减去当前木板高度（如下图所示）。

滑动窗口

无重复字符的最长子串

 0class Solution {
 1    public int lengthOfLongestSubstring(String s) {
 2        if(s.length() <= 0) return 0;
 3        char[] arr = s.toCharArray();
 4        Set<Character> set = new HashSet<>();
 5        int head = 0;
 6        int tail = 1;
 7        set.add(arr[0]);
 8        int res = 1;
 9        while(tail < arr.length){
10            // 伸缩
11            while(head < tail && set.contains(arr[tail])) {
12                set.remove(arr[head]);
13                head ++;
14            }
15            // 扩张
16            set.add(arr[tail]);
17            res = Math.max(res,tail - head + 1);
18            tail ++;
19        }
20        return res;
21    }
22}

不定长滑动窗口
通过哈希表去重

找到字符串中所有字母异位词

 0class Solution {
 1    public List<Integer> findAnagrams(String s, String p) {
 2        if(s.length() < p.length()) return new ArrayList<>();
 3        int[] base = new int[26];
 4        for(char c: p.toCharArray()) {
 5            base[c - 'a'] ++;
 6        }
 7        int[] cnt = new int[26];
 8        for(int i = 0; i < p.length(); i++){
 9            cnt[s.charAt(i) - 'a'] ++;
10        }
11        int l = 0;
12        int r = p.length() - 1;
13        List<Integer> res = new ArrayList<>();
14        while(r < s.length()){
15            if(Arrays.equals(cnt,base)){
16                res.add(l);
17            }
18            // 防止越界
19            if(r == s.length() - 1){
20                break;
21            }
22            cnt[s.charAt(l++) - 'a'] --;
23            cnt[s.charAt(++r) - 'a'] ++;
24        }
25        return res;
26    }
27}

定长滑动窗口
通过Arrays.equals()来比较两个数组的值是否相等（只包含小写字母，比较耗时可忽略）。
因为是先定好了窗口（第二个 for 循环）才开始比较，所以需要注意是否索引越界。

子串

和为 K 的子数组

 0// 解法一: 直接枚举所有子数组
 1class Solution {
 2    public int subarraySum(int[] nums, int k) {
 3        int res = 0;
 4        for (int i = 0; i < nums.length; i++) {
 5            int ans = 0;
 6            for (int j = i; j < nums.length; j++) {
 7                ans += nums[j];
 8                if (ans == k) {
 9                    res ++;
10                }
11            }
12        }
13        return res;
14    }
15}
16// 解法二：动态规划
17class Solution {
18    public int subarraySum(int[] nums, int k) {
19        HashMap<Integer, Integer> mp = new HashMap<>();
20        int res = 0;
21        int suf = 0;
22        // 当suf[i] - k = 0 即suf[i] = k时的初始值
23        mp.put(0, 1); 
24        for (int i = nums.length - 1; i >= 0; i--) {
25            suf+=nums[i];
26            if (mp.containsKey(suf - k)) {
27                res += mp.get(suf - k);
28            }
29            mp.put(suf, mp.getOrDefault(suf, 0) + 1);
30        }
31        return res;
32    }
33}

题解
两种解法，枚举 | 前缀和
前缀和需要理解等式 $Sum(nums[i],nums[j-1])=suf[i]-suf[j]$，suf[i] 表示 $Sum(nums[i],nums[n-1])$。（这里是后缀）

滑动窗口最大值

 0class Solution {
 1    public int[] maxSlidingWindow(int[] nums, int k) {
 2        // 优先队列（大根堆）
 3        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
 4            public int compare(int[] pair1, int[] pair2) {
 5                // 如果2个数相等，那么index大的在前面
 6                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
 7            }
 8        });
 9        for (int i = 0; i < k; ++i) {
10            pq.offer(new int[]{nums[i], i});
11        }
12        int[] ans = new int[nums.length - k + 1];
13        ans[0] = pq.peek()[0];
14        for (int i = k; i < nums.length; ++i) {
15            pq.offer(new int[]{nums[i], i});
16            // 只有当最大值不在在窗口内则删除，其余的不用管
17            while (pq.peek()[1] <= i - k) {
18                pq.poll();
19            }
20            ans[i - k + 1] = pq.peek()[0];
21        }
22        return ans;
23    }
24}

题解
关键在于如何优化[i,i+k]之间的最大值求解过程为 $O(1)$。
优先队列，插入和删除的都是 $O(log N)$
维护优先队列，只需要移除 index 在[i,i+k]窗口外的最大值。

最小覆盖子串

 0class Solution {
 1    public String minWindow(String s, String t) {
 2        if(t.length() > s.length()) return "";
 3        HashMap<Character,Integer> map = new HashMap<>();
 4        char[] arr1 = t.toCharArray();
 5        for(char c : arr1){
 6            map.put(c,map.getOrDefault(c,0) + 1);
 7        }
 8        int left = 0;
 9        int right = 0;
10        int need = 0;
11        char[] arr2 = s.toCharArray();
12        int minL = 0;
13        int minR = -1;
14        while(right < s.length()){
15            if(map.containsKey(arr2[right])){
16                int size = map.get(arr2[right]);
17                map.put(arr2[right],size - 1);
18                if(size == 1){
19                    need ++;
20                }
21            }
22            // 收缩
23            while(left <= right && need == map.size()){
24                if(minR == -1 || right - left < minR - minL){
25                    minL = left;
26                    minR = right;
27                }
28                if(map.containsKey(arr2[left])){
29                    int size = map.get(arr2[left]);
30                    map.put(arr2[left],size + 1);
31                    if(size == 0){
32                        need --;
33                    }
34                }
35                left ++;
36            }
37            right ++;
38        }
39        return s.substring(minL,minR + 1);
40    }
41}

哈希表记录 t 字符串中字符个数
遍历 s 字符串，当哈希表中对应字符的个数减到 0 时，表示子串（窗口内）已经满足特定字符的个数，所以 $need + 1$。
当满足 $need=map.size()$ 时，该子串满足记录/收缩条件；比较字串长度来分别设置 minL、minR 索引。
同理，当哈希表中对应字符的个数累加到 0 时，表明子串（窗口内）不再满足特定字符的个数，所以 $need - 1$。

普通数组

最大子数组和

 0class Solution {
 1    public int maxSubArray(int[] nums) {
 2        int[] dp = new int[nums.length];
 3        dp[0] = nums[0];
 4        int res = dp[0];
 5        for(int i = 1; i < nums.length; i++){
 6            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
 7            res = Math.max(dp[i],res);
 8        }
 9        return res;
10    }
11}

理解 $dp[i] = Math.max(dp[i-1] + nums[i],nums[i])$ 表达式：从 nums[0] -> nums[i] 之间连续子数组和的最优解。

合并区间

 0class Solution {
 1    public int[][] merge(int[][] intervals) {
 2        List<int[]> res = new ArrayList<>();
 3        Arrays.sort(intervals, (o1,o2) -> o1[0] - o2[0]);
 4        for(int i = 0; i < intervals.length; i ++){
 5            // 相交 x1<=x2<=y1<=y2(x1<=x2<=y2<=y1)
 6            while(i+1 < intervals.length && intervals[i][1] >= intervals[i+1][0]){
 7                // 合并
 8                intervals[i+1][0] = intervals[i][0];
 9                intervals[i+1][1] = Math.max(intervals[i][1],intervals[i+1][1]);
10                i++;
11            }
12            // 相隔 x1<y1<x2<y2
13            res.add(intervals[i]);
14        }
15        return res.toArray(new int[res.size()][2]);
16    }
17}

理解区间相隔、相交的表达式。
排序后根据 $intervals[i][1] >= intervals[i+1][0]$ 判断是否需要合并。
合并和后的结果可能需要继续参与下一步判断，所以需要使用 while 循环。

轮转数组

解法一

 0class Solution {
 1    public void rotate(int[] nums, int k) {
 2        int n = nums.length;
 3        k %= n;
 4        int count = 0; // 移动的次数，每一个元素移动1次 共n次
 5        int cntIndex = 0; // 初始索引
 6        int nextIndex = k % n ; // 下一个位置索引
 7        int move = nums[0]; // 移动的元素值
 8        while (count < n) {
 9            int next = nums[nextIndex];
10            nums[nextIndex] = move;
11            move = next;
12            count++;
13            // 成环
14            if (count < n && cntIndex == nextIndex) {
15                cntIndex ++;
16                move = nums[cntIndex];
17                nextIndex =  (cntIndex + k) % n;
18                continue;
19            }
20            nextIndex = (nextIndex + k) % n;
21        }
22    }
23}

参考环形链表/反转链表的特点。
通过 cntIndex 和 nextIndex 变量来判断何时成环。

解法二

 0class Solution {
 1    public void rotate(int[] nums, int k) {
 2        int n = nums.length;
 3        k %= n;
 4        // 整体反转 0->n-1
 5        reverse(0,n - 1,nums);
 6        // 反转0->k -1
 7        reverse(0,k-1,nums);
 8        // 反转n-k -> n - 1
 9        reverse(k,n - 1,nums);
10    }
11    public void reverse(int l,int r,int[] nums) {
12        while (l < r) {
13            int temp = nums[l];
14            nums[l ++] = nums[r];
15            nums[r --] = temp;
16        }
17    }
18}

0nums   = "--->-->"; k =3
1result = "-->--->"; 
2// 解释
3reverse "--->-->" we can get "<--<-----" 
4reverse "<--"     we can get "--><-----" 
5reverse "<-----"  we can get "-->----->"

引用自美服翻转做法下面的第一条评论

解法三

 0class Solution {
 1    public void rotate(int[] nums, int k) {
 2        if(k == 0) return;
 3        int n = nums.length;
 4        int index = n - (k % n);
 5        int[] copy = new int[n];
 6        int j = 0;
 7        for(int i = index; i < n; i++){
 8            copy[j++] = nums[i];
 9        }
10        for(int i = 0; i < index; i++){
11            copy[j++] = nums[i];
12        }
13        for(int i = 0; i < n; i++){
14            nums[i] = copy[i];
15        }
16        return;
17    }
18}

扩容

除自身以外数组的乘积

 0class Solution {
 1    public int[] productExceptSelf(int[] nums) {
 2        int n = nums.length;
 3        int[] answer = new int[n];
 4        int[] suf = new int[n];
 5        suf[n-1] = 1;
 6        for(int i = n-2; i >= 0; i--){
 7            suf[i] = suf[i+1] * nums[i+1];
 8        }
 9        int pre = 1;
10        for(int i = 0; i < n; i++){
11            answer[i] = pre * suf[i];
12            pre *= nums[i];
13        }
14        return answer;
15    }
16}

分别求 i 的前/后缀和

缺失的第一个正数

 0class Solution {
 1    public int firstMissingPositive(int[] nums) {
 2        int n = nums.length;
 3        for (int i = 0; i < n; ++i) {
 4            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
 5                int temp = nums[nums[i] - 1];
 6                nums[nums[i] - 1] = nums[i];
 7                nums[i] = temp;
 8            }
 9        }
10        for (int i = 0; i < n; ++i) {
11            if (nums[i] != i + 1) {
12                return i + 1;
13            }
14        }
15        return n + 1;
16    }
17}

题解
x=nums[i]，如果 $x∈[1,N]$，我们就知道 x 应当出现在数组中的 x−1 的位置，因此交换 nums[i] 和 nums[x−1]
如果 $nums[i]=nums[x−1]$，那么就会无限交换下去，因此控制交换条件 $nums[i]!=nums[x−1]$。

矩阵

矩阵置零

解法一

 0class Solution {
 1    public void setZeroes(int[][] matrix) {
 2        int row = matrix.length;
 3        int col = matrix[0].length;
 4        int[] rowS = new int[row];
 5        int[] colS = new int[col];
 6        for (int i = 0; i < row; i++) {
 7            for (int j = 0; j < col; j++) {
 8                if (matrix[i][j] == 0) {
 9                    // i行j列需要为0
10                    rowS[i] = -1;
11                    colS[j] = -1;
12                }
13            }
14        }
15        for (int i = 0; i < row; i++) {
16            if (rowS[i] == -1) {
17                for (int j = 0; j < col; j++) {
18                    matrix[i][j] = 0;
19                }
20            }
21        }
22        for (int i = 0; i < col; i++) {
23            if (colS[i] == -1) {
24                for (int j = 0; j < row; j++) {
25                    matrix[j][i] = 0;
26                }
27            }
28        }
29    }
30}

通过状态数组rowS[i]、colS[j]，分别表示 matrix 数组的 i 行 j 列是否需要全部置换为 0。

解法二

 0class Solution {
 1    public void setZeroes(int[][] matrix) {
 2        int row = matrix.length;
 3        int col = matrix[0].length;
 4        // 第一行和第一列的状态
 5        boolean row0 = false;
 6        boolean col0 = false;
 7        for (int i = 0; i < row; i++) {
 8            if (matrix[i][0] == 0) {
 9                col0 = true;
10                break;
11            }
12        }
13        for (int i = 0; i < col; i++) {
14            if (matrix[0][i] == 0) {
15                row0 = true;
16                break;
17            }
18        }
19        // 用matrix的第一行和第一列记录matrix的状态
20        for (int i = 1; i < row; i++) {
21            for (int j = 1; j < col; j++) {
22                if (matrix[i][j] == 0) {
23                    matrix[i][0] = 0;
24                    matrix[0][j] = 0;
25                }
26            }
27        }
28        for (int i = 1; i < row; i++) {
29            if (matrix[i][0] == 0) {
30                for (int j = 0; j < col; j++) {
31                    matrix[i][j] = 0;
32                }
33            }
34        }
35        for (int i = 1; i< col; i++) {
36            if (matrix[0][i] == 0) {
37                for (int j = 0; j < row; j++) {
38                    matrix[j][i] = 0;
39                }
40            }
41        }
42        if (row0) {
43            for (int i = 0; i < col; i++) {
44                matrix[0][i] = 0;
45            }
46        }
47        if (col0) {
48            for (int i = 0; i < row; i++) {
49                matrix[i][0] = 0;
50            }
51        }
52    }
53}

题解
这个常量空间的解决方案，关键在于利用自身数组的第 1 行、第 1 列作为原数组 i 行 j 列存在 0 的状态数组。

螺旋矩阵

 0class Solution {
 1    public List<Integer> spiralOrder(int[][] matrix) {
 2      int m = matrix.length;
 3      int n = matrix[0].length;
 4      List<Integer> res = new ArrayList<>();
 5      int left = 0;
 6      int right = n-1;
 7      int top = 0;
 8      int down = m-1;
 9      while(res.size() < m*n){
10        for(int i = left; i <= right; i++){
11          res.add(matrix[top][i]);
12        }
13        for(int i = top+1; i <= down; i++){
14          res.add(matrix[i][right]);
15        }
16        if(left < right && top < down){
17          for(int i = right - 1; i > left; i--){
18            res.add(matrix[down][i]);
19          }
20          for(int i = down; i > top; i--){
21            res.add(matrix[i][left]);
22          }
23        }
24        left ++;
25        right --;
26        top ++;
27        down --;
28      }
29      return res;
30    }
31}

题解
向右 $[left,rigth]$、向下 $[top+1,down]$、向左 $[right-1,left)$、向上 $[down,top)$
向左和向上遍历为了避免和向右、向下遍历的是同一行同一列，需要满足 $left

旋转图像

 0 class Solution {
 1    public void rotate(int[][] matrix) {
 2        int n = matrix.length;
 3        // 沿对角线 \ 翻转
 4        for(int i = 0; i < n; i++){
 5            for(int j = i + 1; j < n; j++){
 6                int temp = matrix[j][i];
 7                matrix[j][i] = matrix[i][j];
 8                matrix[i][j] = temp;
 9            }
10        }
11        // 左右翻转
12        for(int i = 0; i < n; i++){
13            for(int l=0,r=n-1; l < r; l++,r--){
14                int temp = matrix[i][r];
15                matrix[i][r] = matrix[i][l];
16                matrix[i][l] = temp;
17            }
18        }
19    }
20}

题解
将旋转通过两次翻转完成（翻转方式有多种，例如先上下再沿 \ 对角线），具体公式见题解。

搜索二维矩阵 II

 0class Solution {
 1    public boolean searchMatrix(int[][] matrix, int target) {
 2        // 模拟搜索树
 3        int row = matrix.length;
 4        int col = matrix[0].length;
 5        int i = 0;
 6        int j = col - 1;
 7        while (i < row && i >= 0 && j < col && j >= 0) {
 8            if (matrix[i][j] == target) {
 9                return true;
10            } else if (matrix[i][j] < target) {
11                i++;
12            } else {
13                j--;
14            }
15        }
16        return false;
17    }
18}

根据题目要求，当根节点为 $(0,n-1)$ 时，本数组是一个逻辑二叉搜索树。
其他解法：每一行二分（升序排列，二分条件天然）

链表

相交链表

 0public class Solution {
 1    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
 2        // a+b+c = c+b+a
 3        ListNode nodeA = headA;
 4        ListNode nodeB = headB;
 5        while(nodeA != null || nodeB != null){
 6            if(nodeA == nodeB){
 7                return nodeA;
 8            }
 9            nodeA = nodeA == null ? headB:nodeA.next;
10            nodeB = nodeB == null ? headA:nodeB.next;
11        }
12        return null;
13    }
14}

速度一致
$a+b+c=c+b+a$

反转链表

 0class Solution {
 1    public ListNode reverseList(ListNode head) {
 2        if(head == null || head.next == null){
 3            return head;
 4        }
 5        ListNode cntNode = head;
 6        ListNode pre = null;
 7        while(cntNode != null){
 8            ListNode temp = cntNode.next;
 9            cntNode.next = pre;
10            pre = cntNode;
11            cntNode = temp;
12        }
13        return pre;
14    }
15}

链表反转：cntNode -> pre

回文链表

 0class Solution {
 1    public boolean isPalindrome(ListNode head) {
 2        if(head.next == null){
 3            return true;
 4        }
 5        // 先反转再判断
 6        ListNode s = head;
 7        ListNode f = head;
 8        while(f != null && f.next != null){
 9            s = s.next;
10            f = f.next.next;
11        }
12        ListNode pre = null;
13        while(s != null){
14            ListNode temp = s.next;
15            s.next = pre;
16            pre = s;
17            s = temp;
18        }
19        while(pre != null && head != null){
20            if(pre.val == head.val){
21                pre = pre.next;
22                head = head.next;
23            }else{
24                return false;
25            }
26        }
27        return true;
28    }
29}

通过快慢指针找到中间节点，$v1:v2=1:2$
反转中间节点到尾节点部分，再比较：A->B->C => A->B<-C

环形链表

 0public class Solution {
 1    public boolean hasCycle(ListNode head) {
 2        Set<ListNode> hashSet = new HashSet<>();
 3        ListNode cur = head;
 4        while(cur != null){
 5            if(hashSet.contains(cur)){
 6                return true;
 7            }
 8            hashSet.add(cur);
 9            cur = cur.next;
10        }
11        return false;
12    }
13}

哈希表、Floyd Cycle Detection Algorithm 都可以

环形链表 II

 0public class Solution {
 1    public ListNode detectCycle(ListNode head) {
 2        if(head == null || head.next == null){
 3            return null;
 4        }
 5        ListNode slow = head;
 6        ListNode fast = head;
 7        while(fast != null && fast.next != null){
 8          slow = slow.next;
 9          fast = fast.next.next;
10          // 有环
11          if(slow == fast){
12            break;
13          }
14        }
15        // 无环
16        if(fast == null || fast.next == null){
17            return null;
18        }
19        // 相交节点
20        while(slow != head){
21            slow = slow.next;
22            head = head.next;
23        }
24        return slow;
25    }
26}

哈希表、Floyd Cycle Detection Algorithm 都可以

合并两个有序链表

 0class Solution {
 1    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
 2        ListNode head = new ListNode();
 3        ListNode node = head;
 4        while(list1 != null && list2 != null){
 5            if(list1.val < list2.val){
 6                node.next = list1;
 7                list1 = list1.next;
 8            }else{
 9                node.next = list2;
10                list2 = list2.next;
11            }
12            node = node.next;
13        }
14        if(list1 == null && list2 != null){
15            node.next = list2;
16        }
17        if(list2 == null && list1 != null){
18            node.next = list1;
19        }
20        return head.next;
21    }
22}

类似归并排序中的有序数组合并过程。

两数相加

 0class Solution {
 1    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 2        ListNode head = new ListNode();
 3        ListNode cnt = head;
 4        int jw = 0;
 5        while(l1 != null || l2 != null){
 6            int val = jw;
 7            if(l1 != null){
 8                val += l1.val;
 9                l1 = l1.next;
10            }
11            if(l2 != null){
12                val += l2.val;
13                l2 = l2.next;
14            }
15            jw = val / 10;
16            val = val % 10;
17            cnt.next = new ListNode(val);
18            cnt = cnt.next;
19        }
20        if(jw != 0){
21            cnt.next = new ListNode(jw);
22        }
23        return head.next;
24    }
25}

注意进位的求解，以及最后一位的进位数需要判断是否 = 1

删除链表的倒数第 N 个结点

 0class Solution {
 1    public ListNode removeNthFromEnd(ListNode head, int n) {
 2        ListNode cnt = head;
 3        for(int i = 0; i < n; i++) {
 4            cnt = cnt.next;
 5        }
 6        ListNode slow = head;
 7        while(cnt != null && cnt.next != null){
 8            slow = slow.next;
 9            cnt = cnt.next;
10        }
11        if(cnt != null) {
12            slow.next = slow.next.next;
13        }
14        else {
15            return head.next;
16        }
17        return head;
18    }
19}

双指针，令 slow 和 cnt 之间的距离为 n。

两两交换链表中的节点

 0class Solution {
 1    public ListNode swapPairs(ListNode head) {
 2        if(head == null) return null;
 3        ListNode newHead = new ListNode();
 4        newHead.next = head;
 5        ListNode cnt = newHead;
 6        while(cnt.next != null && cnt.next.next != null){
 7            ListNode temp = cnt.next;
 8            cnt.next = cnt.next.next;
 9            ListNode temp2 = cnt.next.next;
10            cnt.next.next = temp;
11            cnt = cnt.next.next;
12            cnt.next = temp2;
13        }
14        return newHead.next;
15    }
16}

需要设置一个虚拟头节点方便节点交换
节点交换过程如下图所示

K 个一组翻转链表

 0class Solution {
 1    public ListNode reverseKGroup(ListNode head, int k) {
 2        ListNode dummy = new ListNode();
 3        dummy.next = head;
 4        ListNode newHead = dummy;
 5        // fast 为下一组翻转的 head 节点
 6        ListNode fast = head;
 7        ListNode slow = null;
 8        int cnt = 0;
 9        while(fast != null) {
10            // slow 为当前组翻转的 head 节点
11            slow = fast;
12            while(fast != null && cnt < k){
13                fast = fast.next;
14                cnt ++;
15            }
16            // 满足 k 个节点一组翻转
17            if(cnt == k){
18                ListNode pre = null;
19                ListNode curNode = slow;
20                while(cnt > 0){
21                    ListNode temp = curNode.next;
22                    curNode.next = pre;
23                    pre = curNode;
24                    curNode = temp;
25                    cnt --;
26                }
27                // 翻转后的 slow 变为 tail 节点,链接下一组的 head 节点
28                slow.next = fast;
29                // 当前组的 head 节点链接翻转后的 head 节点
30                newHead.next = pre;
31                // 下一组翻转前的 dummy head node
32                newHead = slow;
33            }else{
34                break;
35            }
36        }
37        return dummy.next;
38    }
39}

dummy head node 技巧
两个关键的节点链接（头和尾），newHead.next = pre 以及 slow.next = fast。

随机链表的复制

 0class Solution {
 1    public Node copyRandomList(Node head) {
 2        if(head == null) return null;
 3        Node dummy = new Node(0);
 4        Node cnt = dummy;
 5        // origin->copy
 6        HashMap<Node,Node> map = new HashMap<>();
 7        while(head != null){
 8            Node copy = null;
 9            if(map.containsKey(head)){
10                copy = map.get(head);
11            }else{
12                copy = new Node(head.val);
13                map.put(head,copy);
14            }
15            if(head.random != null){
16                if(map.containsKey(head.random)){
17                    copy.random = map.get(head.random);
18                }else{
19                    Node n2 = new Node(head.random.val);
20                    map.put(head.random,n2);
21                    copy.random = n2;
22                }            
23            }
24            cnt.next = copy;
25            cnt = cnt.next;
26            head = head.next;
27        }
28        return dummy.next;
29    }
30}

哈希表记录 origin node -> copy node

排序链表

 0class Solution {
 1    public ListNode sortList(ListNode head) {
 2        if(head == null || head.next == null) {
 3            return head;
 4        }
 5        ListNode mid = midNode(head);
 6        ListNode newHead = mid.next;
 7        mid.next = null;
 8        // 归并
 9        ListNode h1 = sortList(head);
10        ListNode h2 = sortList(newHead);
11        ListNode dummy = new ListNode();
12        ListNode cnt = dummy;
13        while(h1 != null && h2 != null){
14            if(h1.val < h2.val){
15                cnt.next = h1;
16                h1 = h1.next;
17            }else{
18                cnt.next = h2;
19                h2 = h2.next;
20            }
21            cnt = cnt.next;
22        }
23        cnt.next = h1 == null ? h2 : h1;
24        return dummy.next;
25    }
26    // 中间节点
27    public ListNode midNode(ListNode head) {
28        ListNode slow = head;
29        ListNode fast = head.next;
30        while (fast != null && fast.next != null)  {
31            slow = slow.next;
32            fast = fast.next.next;
33        }
34        return slow;
35    }
36}

归并排序 + 求链表中间节点的双指针算法

合并 K 个升序链表

方法一：

 0class Solution {
 1    public ListNode mergeKLists(ListNode[] lists) {
 2        ListNode ans = null;
 3        for (int i = 0; i < lists.length; ++i) {
 4            ans = mergeTwoLists(ans, lists[i]);
 5        }
 6        return ans;
 7    }
 8
 9    public ListNode mergeTwoLists(ListNode a, ListNode b) {
10        if (a == null || b == null) {
11            return a != null ? a : b;
12        }
13        ListNode head = new ListNode(0);
14        ListNode tail = head, aPtr = a, bPtr = b;
15        while (aPtr != null && bPtr != null) {
16            if (aPtr.val < bPtr.val) {
17                tail.next = aPtr;
18                aPtr = aPtr.next;
19            } else {
20                tail.next = bPtr;
21                bPtr = bPtr.next;
22            }
23            tail = tail.next;
24        }
25        tail.next = (aPtr != null ? aPtr : bPtr);
26        return head.next;
27    }
28}

方法二：

 0class Solution {
 1    public ListNode mergeKLists(ListNode[] lists) {
 2        return merge(lists, 0, lists.length - 1);
 3    }
 4
 5    public ListNode merge(ListNode[] lists, int l, int r) {
 6        if (l == r) {
 7            return lists[l];
 8        }
 9        if (l > r) {
10            return null;
11        }
12        int mid = (l + r) >> 1;
13        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
14    }
15
16    public ListNode mergeTwoLists(ListNode a, ListNode b) {
17        if (a == null || b == null) {
18            return a != null ? a : b;
19        }
20        ListNode head = new ListNode(0);
21        ListNode tail = head, aPtr = a, bPtr = b;
22        while (aPtr != null && bPtr != null) {
23            if (aPtr.val < bPtr.val) {
24                tail.next = aPtr;
25                aPtr = aPtr.next;
26            } else {
27                tail.next = bPtr;
28                bPtr = bPtr.next;
29            }
30            tail = tail.next;
31        }
32        tail.next = (aPtr != null ? aPtr : bPtr);
33        return head.next;
34    }
35}

方法三：

 0class Solution {
 1    public ListNode mergeKLists(ListNode[] lists) {
 2        // 拼接后排序
 3        int k = lists.length;
 4        if(k == 0) return null;
 5        ListNode dummy = new ListNode();
 6        ListNode cnt = dummy;
 7        for(ListNode h1 : lists){
 8            if(h1 == null) continue;
 9            cnt.next = h1;
10            while(cnt.next != null){
11                cnt = cnt.next;
12            }
13        }
14        return sortList(dummy.next);
15    }
16    // 归并排序
17    public ListNode sortList(ListNode head) {
18        if(head == null || head.next == null) {
19            return head;
20        }
21        ListNode mid = midNode(head);
22        ListNode newHead = mid.next;
23        mid.next = null;
24        // 归并
25        ListNode h1 = sortList(head);
26        ListNode h2 = sortList(newHead);
27        ListNode dummy = new ListNode();
28        ListNode cnt = dummy;
29        while(h1 != null && h2 != null){
30            if(h1.val < h2.val){
31                cnt.next = h1;
32                h1 = h1.next;
33            }else{
34                cnt.next = h2;
35                h2 = h2.next;
36            }
37            cnt = cnt.next;
38        }
39        cnt.next = h1 == null ? h2 : h1;
40        return dummy.next;
41    }
42    // 中间节点
43    public ListNode midNode(ListNode head) {
44        ListNode slow = head;
45        ListNode fast = head.next;
46        while (fast != null && fast.next != null)  {
47            slow = slow.next;
48            fast = fast.next.next;
49        }
50        return slow;
51    }
52}

题解
1、顺序合并（参考合并两个升序链表）
2、分治合并（如下图）
3、拼接整个数组后，归并排序整个链表

LRU 缓存

 0public class LRUCache {
 1    class DLinkedNode {
 2        int key;
 3        int value;
 4        DLinkedNode prev;
 5        DLinkedNode next;
 6        public DLinkedNode() {}
 7        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
 8    }
 9  
10    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
11    private int size;
12    private int capacity;
13    private DLinkedNode head, tail;
14  
15    public LRUCache(int capacity) {
16        this.size = 0;
17        this.capacity = capacity;
18        // 使用伪头部和伪尾部节点
19        head = new DLinkedNode();
20        tail = new DLinkedNode();
21        head.next = tail;
22        tail.prev = head;
23    }
24
25    public int get(int key) {
26        DLinkedNode node = cache.get(key);
27        if (node == null) {
28            return -1;
29        }
30        // 如果 key 存在，先通过哈希表定位，再移到头部
31        moveToHead(node);
32        return node.value;
33    }
34
35    public void put(int key, int value) {
36        DLinkedNode node = cache.get(key);
37        if (node == null) {
38            // 如果 key 不存在，创建一个新的节点
39            DLinkedNode newNode = new DLinkedNode(key, value);
40            // 添加进哈希表
41            cache.put(key, newNode);
42            // 添加至双向链表的头部
43            addToHead(newNode);
44            ++size;
45            if (size > capacity) {
46                // 如果超出容量，删除双向链表的尾部节点
47                DLinkedNode tail = removeTail();
48                // 删除哈希表中对应的项
49                cache.remove(tail.key);
50                --size;
51            }
52        }
53        else {
54            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
55            node.value = value;
56            moveToHead(node);
57        }
58    }
59  
60    private void addToHead(DLinkedNode node) {
61        node.prev = head;
62        node.next = head.next;
63        head.next.prev = node;
64        head.next = node;
65    }
66
67    private void removeNode(DLinkedNode node) {
68        node.prev.next = node.next;
69        node.next.prev = node.prev;
70    }
71
72    private void moveToHead(DLinkedNode node) {
73        removeNode(node);
74        addToHead(node);
75    }
76
77    private DLinkedNode removeTail() {
78        DLinkedNode res = tail.prev;
79        removeNode(res);
80        return res;
81    }
82}

题解
哈希表 + 双向链表，通过双向链表维持 LRU (最近最少使用) 缓存。

LFU 缓存

 0class LFUCache {
 1    private static class Node {
 2        int key, value, freq = 1; // 新书只读了一次
 3        Node prev, next;
 4
 5        Node(int key, int value) {
 6            this.key = key;
 7            this.value = value;
 8        }
 9    }
10
11    private final int capacity;
12    private final Map<Integer, Node> keyToNode = new HashMap<>();
13    private final Map<Integer, Node> freqToDummy = new HashMap<>();
14    private int minFreq;
15
16    public LFUCache(int capacity) {
17        this.capacity = capacity;
18    }
19
20    public int get(int key) {
21        Node node = getNode(key);
22        return node != null ? node.value : -1;
23    }
24
25    public void put(int key, int value) {
26        Node node = getNode(key);
27        if (node != null) { // 有这本书
28            node.value = value; // 更新 value
29            return;
30        }
31        if (keyToNode.size() == capacity) { // 书太多了
32            Node dummy = freqToDummy.get(minFreq);
33            Node backNode = dummy.prev; // 最左边那摞书的最下面的书
34            keyToNode.remove(backNode.key);
35            remove(backNode); // 移除
36            if (dummy.prev == dummy) { // 这摞书是空的
37                freqToDummy.remove(minFreq); // 移除空链表
38            }
39        }
40        node = new Node(key, value); // 新书
41        keyToNode.put(key, node);
42        pushFront(1, node); // 放在「看过 1 次」的最上面
43        minFreq = 1;
44    }
45
46    private Node getNode(int key) {
47        if (!keyToNode.containsKey(key)) { // 没有这本书
48            return null;
49        }
50        Node node = keyToNode.get(key); // 有这本书
51        remove(node); // 把这本书抽出来
52        Node dummy = freqToDummy.get(node.freq);
53        if (dummy.prev == dummy) { // 抽出来后，这摞书是空的
54            freqToDummy.remove(node.freq); // 移除空链表
55            if (minFreq == node.freq) { // 这摞书是最左边的
56                minFreq++;
57            }
58        }
59        node.freq++; // 看书次数 +1
60        pushFront(node.freq, node); // 放在右边这摞书的最上面
61        return node;
62    }
63
64    // 创建一个新的双向链表
65    private Node newList() {
66        Node dummy = new Node(0, 0); // 哨兵节点
67        dummy.prev = dummy;
68        dummy.next = dummy;
69        return dummy;
70    }
71
72    // 在链表头添加一个节点（把一本书放到最上面）
73    private void pushFront(int freq, Node x) {
74        Node dummy = freqToDummy.computeIfAbsent(freq, k -> newList());
75        x.prev = dummy;
76        x.next = dummy.next;
77        x.prev.next = x;
78        x.next.prev = x;
79    }
80
81    // 删除一个节点（抽出一本书）
82    private void remove(Node x) {
83        x.prev.next = x.next;
84        x.next.prev = x.prev;
85    }
86}

题解
哈希表（分别维护 KEY -> Node，Freq -> NodeHead）+ 双向链表，最不经常使用（LFU）。

二叉树

二叉树的遍历-7种

  0// 前序遍历 (Preorder Traversal)
  1// 递归
  2public void dfs(TreeNode root) {
  3    if (root == null) {
  4        return;
  5    }
  6    System.out.print(root.val + " "); // 访问根节点
  7    dfs(root.left);
  8    dfs(root.right);
  9}
 10// 迭代
 11import java.util.Stack;
 12public void main(TreeNode root) {
 13    if (root == null) {
 14        return;
 15    }
 16    Stack<TreeNode> stack = new Stack<>();
 17    stack.push(root);
 18    while (!stack.isEmpty()) {
 19        TreeNode node = stack.pop();
 20        System.out.print(node.val + " ");
 21        // 关键点：先入栈右孩子，再入栈左孩子
 22        if (node.right != null) {
 23            stack.push(node.right);
 24        }
 25        if (node.left != null) {
 26            stack.push(node.left);
 27        }
 28    }
 29}
 30
 31// 中序遍历 (Inorder Traversal)
 32// 递归
 33public void dfs(TreeNode root) {
 34    if (root == null) {
 35        return;
 36    }
 37    dfs(root.left);
 38    System.out.print(root.val + " "); // 访问根节点
 39    dfs(root.right);
 40}
 41// 迭代
 42import java.util.Stack;
 43public void main(TreeNode root) {
 44    Stack<TreeNode> stack = new Stack<>();
 45    TreeNode curr = root;
 46    while (curr != null || !stack.isEmpty()) {
 47        // 一路向左，将所有左子节点入栈
 48        while (curr != null) {
 49            stack.push(curr);
 50            curr = curr.left;
 51        }
 52        curr = stack.pop();
 53        System.out.print(curr.val + " ");
 54        curr = curr.right;
 55    }
 56}
 57
 58// 后序遍历 (Postorder Traversal)
 59// 递归
 60public void dfs(TreeNode root) {
 61    if (root == null) {
 62        return;
 63    }
 64    dfs(root.left);
 65    dfs(root.right);
 66    System.out.print(root.val + " "); // 访问根节点
 67}
 68//迭代
 69import java.util.Stack;
 70import java.util.LinkedList;
 71import java.util.Collections;
 72public void postorderTraversalIterative(TreeNode root) {
 73    if (root == null) {
 74        return;
 75    }
 76    Stack<TreeNode> stack1 = new Stack<>();
 77    Stack<TreeNode> stack2 = new Stack<>();
 78    stack1.push(root);
 79    // 第一个栈用于以“根右左”的顺序遍历
 80    while (!stack1.isEmpty()) {
 81        TreeNode node = stack1.pop();
 82        stack2.push(node);
 83        if (node.left != null) {
 84            stack1.push(node.left);
 85        }
 86        if (node.right != null) {
 87            stack1.push(node.right);
 88        }
 89    }
 90    // 第二个栈以“左右根”的顺序输出
 91    while (!stack2.isEmpty()) {
 92        System.out.print(stack2.pop().val + " ");
 93    }
 94}
 95
 96// 层序遍历 (Level Order Traversal) - 迭代
 97import java.util.Queue;
 98import java.util.LinkedList;
 99public void bfs(TreeNode root) {
100    if (root == null) {
101        return;
102    }
103    Queue<TreeNode> queue = new LinkedList<>();
104    queue.offer(root);
105    while (!queue.isEmpty()) {
106        TreeNode node = queue.poll();
107        System.out.print(node.val + " ");
108        if (node.left != null) {
109            queue.offer(node.left);
110        }
111        if (node.right != null) {
112            queue.offer(node.right);
113        }
114    }
115}

二叉树的中序遍历

1、递归

 0class Solution {
 1    public List<Integer> inorderTraversal(TreeNode root) {
 2        List<Integer> res = new ArrayList<>();
 3        dfs(res,root);
 4        return res;
 5    }
 6    // 中序遍历
 7    public void dfs(List<Integer> ans, TreeNode node){
 8        if(node == null){
 9            return;
10        }
11        dfs(ans,node.left);
12        ans.add(node.val);
13        dfs(ans,node.right);
14    }
15}

2、迭代

 0class Solution {
 1    public List<Integer> inorderTraversal(TreeNode root) {
 2        List<Integer> res = new ArrayList<>();
 3        Stack<TreeNode> stack = new Stack<>();
 4        TreeNode cur = root;
 5        while(cur != null || !stack.empty()){
 6            if(cur != null){
 7                stack.push(cur);
 8                cur = cur.left;
 9            }else {
10                cur = stack.pop();
11                res.add(cur.val);
12                cur = cur.right;
13            }
14        }
15        return res;
16    }
17}

深度优先搜索 - 中序遍历的迭代方式 - 栈

二叉树的最大深度

1、迭代

 0class Solution {
 1    public int maxDepth(TreeNode root) {
 2        Deque<TreeNode> queue = new ArrayDeque<>();
 3        int res = 0;
 4        if(root != null){
 5            queue.add(root);
 6        }else{
 7            return res;
 8        }
 9        while(!queue.isEmpty()){
10            res ++;
11            int size = queue.size();
12            while(size -- > 0){
13                TreeNode cur = queue.pop();
14                if(cur.left != null) queue.add(cur.left);
15                if(cur.right != null) queue.add(cur.right);
16            }
17        }
18        return res;
19    }
20}

2、递归

 0class Solution {
 1    public int maxDepth(TreeNode root) {
 2        if(root == null){
 3            return 0;
 4        }else{
 5            int leftHeight = maxDepth(root.left);
 6            int rightHeight = maxDepth(root.right);
 7            return 1 + Math.max(leftHeight,rightHeight);
 8        }
 9    }
10}

广度优先搜索 - 层序遍历 - 队列
前序求深度与后序求高度，最大高度等于最大深度
求树的最大深度可以理解为是左子树或者右子树里最大深度 +1，这样就把原问题拆解成了两个子问题

翻转二叉树

 0class Solution {
 1    public TreeNode invertTree(TreeNode root) {
 2        dfs(root);
 3        return root;
 4    }
 5    // 翻转当前 root 节点的左右子树
 6    public void dfs(TreeNode root) {
 7        if(root == null){
 8            return;
 9        }
10        TreeNode temp = root.left;
11        root.left = root.right;
12        root.right = temp;
13        dfs(root.left);
14        dfs(root.right);
15    }
16}

dfs(TreeNode root)：翻转当前节点的左右子树（理解该方法的这个功能即可，不要人脑压栈）。

对称二叉树

 0class Solution {
 1    public boolean isSymmetric(TreeNode root) {
 2        if(root == null) {
 3            return true;
 4        }
 5        return compare(root.left, root.right);
 6    }
 7    public boolean compare(TreeNode left, TreeNode right) {
 8        if (left != null && right == null) {
 9            return false;
10        }
11        else if (left == null && right != null) {
12            return false;
13        }
14        else if (left == null && right == null) {
15            return true;
16        }
17        else if (left.val != right.val) {
18            return false;
19        }
20        boolean outside = compare(left.left, right.right); // 左子树左、右子树右
21        boolean inside = compare(left.right, right.left); // 左子树右、右子树左
22        return outside && inside; // 内侧和外侧值是否相等
23    }
24}

递归传递左右子树的根节点，不是之前只传当前子树根节点。

二叉树的直径

 0class Solution {
 1    int ans;
 2    public int diameterOfBinaryTree(TreeNode root) {
 3        ans = 1;
 4        depth(root);
 5        return ans - 1;
 6    }
 7    public int depth(TreeNode node) {
 8        if (node == null) {
 9            return 0; // 访问到空节点了，返回0
10        }
11        int L = depth(node.left); // 左儿子为根的子树的深度
12        int R = depth(node.right); // 右儿子为根的子树的深度
13        ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans
14        return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
15    }
16}

题解
假设我们知道对于该节点的左儿子向下遍历经过最多的节点数 L （即以左儿子为根的子树的深度）和其右儿子向下遍历经过最多的节点数 R （即以右儿子为根的子树的深度），那么以该节点为起点的路径经过节点数的最大值即为 $L+R+1$。

二叉树的层序遍历

 0class Solution {
 1    public List<List<Integer>> levelOrder(TreeNode root) {
 2        if(root == null){
 3            return new ArrayList();
 4        }
 5        Deque<TreeNode> queue = new LinkedList();
 6        queue.add(root);
 7        List<List<Integer>> res = new ArrayList<>();
 8        while(!queue.isEmpty()){
 9            List<Integer> ans = new ArrayList<>();
10            int size = queue.size();
11            while(size-- > 0){
12                TreeNode cur = queue.pop();
13                ans.add(cur.val);
14                if(cur.left != null) queue.add(cur.left);
15                if(cur.right != null) queue.add(cur.right);
16            }
17            res.add(ans);
18        }
19        return res;
20    }
21}

借助队列的“先进先出”特点

将有序数组转换为二叉搜索树

 0class Solution {
 1    public TreeNode sortedArrayToBST(int[] nums) {
 2        if(nums.length == 0) return null;
 3        return dfs(nums,0,nums.length - 1);
 4    }
 5    public TreeNode dfs(int[] nums,int l,int r){
 6        if(l > r){
 7            return null;
 8        }
 9        int mid = (l + r) >> 1;
10        TreeNode root = new TreeNode(nums[mid]);
11        root.left = dfs(nums,l,mid-1);
12        root.right = dfs(nums,mid+1,r);
13        return root;
14    }
15}

想要二叉搜索树平衡，需要始终选用数组中间节点。
选取的子数组范围采用闭区间 [l,r]，递归需注意区间的开闭统一。

验证二叉搜索树

 0class Solution {
 1    TreeNode pre = null;
 2    public boolean isValidBST(TreeNode root) {
 3        return dfs(root);
 4    }
 5    public boolean dfs(TreeNode root){
 6        if(root == null){
 7            return true;
 8        }
 9        boolean leftTree = dfs(root.left);
10        if(pre != null && pre.val >= root.val) {
11            return false;
12        }else{
13            pre = root;
14        }
15        boolean rightTree = dfs(root.right);
16        return leftTree && rightTree;
17    }
18}

二叉搜素树的中序遍历元素是递增的。
可以存储在数组后进行判断；优化就是直接遍历二叉树的过程中比较，定义一个全局变量记录前一个节点数值。

二叉搜索树中第 K 小的元素

 0class Solution {
 1    int size = 0;
 2    int res = -1;
 3    boolean st = false;
 4    public int kthSmallest(TreeNode root, int k) {
 5        dfs(root,k);
 6        return res;        
 7    }
 8    public void dfs(TreeNode root,int k){
 9        if(root == null || st){
10            return;
11        }
12        dfs(root.left,k);
13        if(st) return;
14        size++;
15        if(size == k){
16            res = root.val;
17            st = true;
18            return;
19        }
20        dfs(root.right,k);
21    }
22}

二叉搜素树的中序遍历元素是递增的。
通过计数器以及找到第 K 小的数后剪枝。

二叉树的右视图

 0class Solution {
 1    List<Integer> res = new ArrayList<>();
 2    public List<Integer> rightSideView(TreeNode root) {
 3        dfs(root,0);
 4        return res;
 5    }
 6    public void dfs(TreeNode root,int depth){
 7        if(root == null) return;
 8        if(res.size() == depth){
 9            res.add(root.val);
10        }
11        dfs(root.right,depth+1);
12        dfs(root.left,depth+1);
13    }
14}

每一层最多只能添加一个节点值
利用 res.size() 来判断当前的最大深度
先右节点再左节点，当某个深度首次到达时，对应的节点就在右视图中

从前序与中序遍历序列构造二叉树

 0class Solution {
 1    public TreeNode buildTree(int[] inorder, int[] postorder) {
 2        return dfs(inorder,postorder);
 3    }
 4    public TreeNode dfs(int[] inorder,int[] postorder) {
 5        if(postorder.length == 0 || inorder.length == 0) return null;
 6        // 后序数组最后一个元素为节点
 7        int rootValue = postorder[postorder.length - 1];
 8        TreeNode root = new TreeNode(rootValue);
 9        // 只有一个叶子节点
10        if(postorder.length == 1) return root;
11        // 切割中序，根据后序数组节点切割
12        int index;
13        for(index = 0; index < inorder.length; index ++){
14            if(inorder[index] == rootValue) break;
15        }
16        int[] leftInorder = Arrays.copyOfRange(inorder,0,index);
17        int[] rightInorder = Arrays.copyOfRange(inorder,index + 1,inorder.length);
18        // 切割后序,根据左中序切割
19        int[] leftPostorder = Arrays.copyOfRange(postorder,0,leftInorder.length);
20        int[] rightPostorder = Arrays.copyOfRange(postorder,leftInorder.length,postorder.length-1);
21        root.left = dfs(leftInorder,leftPostorder);
22        root.right = dfs(rightInorder,rightPostorder);
23        return root;
24    }
25}

题解
根据中序+后序的遍历数组，还原二叉树。
当后序数组长度为 0，中序数组也一定为 0。同理后序数组长度为 1 时元素值为叶子节点。
先根据后序数组的根节点切割中序数组得到左/右子树，再根据中序数组的左子树确定后序数组的切割位置，从而切割后续数组。
Arrays.copyOfRange(int[] original, int from, int to)：复制 original 数组，包前不包后。

二叉树展开为链表

方法1：

 0class Solution {
 1    List<TreeNode> res = new ArrayList<>();
 2    public void flatten(TreeNode root) {
 3        dfs(root);
 4        TreeNode cur = root;
 5        for(int i = 1; i < res.size(); i++){
 6            cur.left = null;
 7            cur.right = res.get(i);
 8            cur = cur.right;
 9        }
10    }
11    public void dfs(TreeNode root){
12        if(root == null){
13            return;
14        }
15        res.add(root);
16        dfs(root.left);
17        dfs(root.right);
18    }
19}

先遍历后展开

方法2：

 0class Solution {
 1    public void flatten(TreeNode root) {
 2        TreeNode curr = root;
 3        while (curr != null) {
 4            if (curr.left != null) {
 5                TreeNode next = curr.left;
 6                TreeNode pre = next;
 7                while (pre.right != null) {
 8                    pre = pre.right;
 9                }
10                pre.right = curr.right;
11                curr.left = null;
12                curr.right = next;
13            }
14            curr = curr.right;
15        }
16    }
17}

题解
该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点，也是该节点的前驱节点，然后将当前节点的右子节点赋给前驱节点的右子节点。

从前序与中序遍历序列构造二叉树

 0class Solution {
 1    public TreeNode buildTree(int[] preorder, int[] inorder) {
 2        if(preorder.length == 0 || inorder.length == 0) {
 3            return null;
 4        }
 5        // 根节点
 6        TreeNode root = new TreeNode(preorder[0]);
 7        // 叶子节点
 8        if(preorder.length == 1){
 9            return root;
10        }
11        // 切割中序数组
12        int index;
13        for(index = 0; index < inorder.length; index++){
14            if(inorder[index] == preorder[0]) {
15                break;
16            }
17        }
18        int[] lInorder = Arrays.copyOfRange(inorder,0,index);
19        int[] rInorder = Arrays.copyOfRange(inorder,index + 1,inorder.length);
20        // 切割前序数组
21        int[] lPreorder = Arrays.copyOfRange(preorder,1,lInorder.length + 1);
22        int[] rPreorder = Arrays.copyOfRange(preorder,lInorder.length + 1,inorder.length);
23        root.left = buildTree(lPreorder,lInorder);
24        root.right = buildTree(rPreorder,rInorder);
25        return root;
26    }
27}

只有中序同前序/后序的组合才可以确定一颗二叉树
关键在于，前序数组的第 1 个元素就是子树的根节点，然后根据根节点确定中序/前序数组的左右子树，最后递归。
注意数组复制的边界。

路径总和 III

方法一：

 0class Solution {
 1    public int pathSum(TreeNode root, long targetSum) {
 2        if(root == null) return 0;
 3        // 这里相当于先序遍历每个 root 起点，然后统计该起点满足结果的路径数
 4        int res = dfs(root,targetSum);
 5        res += pathSum(root.left,targetSum);
 6        res += pathSum(root.right,targetSum);
 7        return res;
 8    }
 9
10    // 表示以节点 root 为起点向下且满足路径总和为 val 的路径数目。
11    public int dfs(TreeNode root,long targetSum){
12        if(root == null) return 0;
13        int res = 0;
14        int val = root.val;
15        // 当前节点值就满足
16        if (val == targetSum) {
17            res++;
18        }
19        res += dfs(root.left,targetSum - val);
20        res += dfs(root.right,targetSum - val);
21        return res;
22    }
23}

题解
暴力解法：先序遍历每一个节点 root，然后求以节点 root 为起点向下且满足路径总和为 targetSum 的路径数目
dfs(TreeNode root,long targetSum) = dfs(root.left,targetSum - val) + dfs(root.right,targetSum - val)

方法二：

 0class Solution {
 1    public int pathSum(TreeNode root, int targetSum) {
 2        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
 3        prefix.put(0L, 1);
 4        return dfs(root, prefix, 0, targetSum);
 5    }
 6  
 7    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
 8        if (root == null) {
 9            return 0;
10        }
11        int ret = 0;
12        curr += root.val;
13        ret = prefix.getOrDefault(curr - targetSum, 0);
14        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
15        ret += dfs(root.left, prefix, curr, targetSum);
16        ret += dfs(root.right, prefix, curr, targetSum);
17        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
18        return ret;
19    }
20}

题解
同和为 K 的子数组题的思路一致，考察前缀和。

二叉树的最近公共祖先

 0class Solution {
 1    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
 2        return dfs(root,p,q);
 3    }
 4    public TreeNode dfs(TreeNode root,TreeNode p,TreeNode q){
 5        if(root == null) return null;
 6        if(root == p || root == q) return root;
 7        // 在左子树中找 p 或 q
 8        TreeNode left = dfs(root.left,p,q);
 9        // 在右子树中找 p 或 q
10        TreeNode right = dfs(root.right,p,q);
11        // 左右都找到 → 当前 root 就是最近公共祖先
12        if(left != null && right != null) return root;
13        // 情况2：只找到一个 → 把那个往上返回
14        if(left != null && right == null) return left;
15        if(left == null && right != null) return right;
16        return null;
17    }
18}

画图
后序遍历，这样结果是向上返回（回溯）
公共祖先的两种情况

二叉树中的最大路径和

 0class Solution {
 1    int maxSum = Integer.MIN_VALUE;
 2    public int maxPathSum(TreeNode root) {
 3        maxGain(root);
 4        return maxSum;
 5    }
 6    public int maxGain(TreeNode node) {
 7        if (node == null) {
 8            return 0;
 9        }
10        // 递归计算左右子节点的最大贡献值
11        // 只有在最大贡献值大于 0 时，才会选取对应子节点
12        int leftGain = Math.max(maxGain(node.left), 0);
13        int rightGain = Math.max(maxGain(node.right), 0);
14        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
15        int priceNewpath = node.val + leftGain + rightGain;
16        // 更新答案
17        maxSum = Math.max(maxSum, priceNewpath);
18        // 返回节点的最大贡献值
19        return node.val + Math.max(leftGain, rightGain);
20    }
21}

题解
后序遍历，统计每个节点的最大贡献值（该节点为起点的一条路径，路径的和最大）
节点的最大路径和等于该节点的值加上左右子节点的最大贡献值（大于 0）。

图论

岛屿数量

 0class Solution {
 1    // 方向数组：右、上、左、下
 2    int[] dx = {1, 0, -1, 0};
 3    int[] dy = {0, -1, 0, 1};
 4
 5    public int numIslands(char[][] grid) {
 6        int m = grid.length;
 7        int n = grid[0].length;
 8        int islands = 0;
 9
10        for (int i = 0; i < m; i++) {
11            for (int j = 0; j < n; j++) {
12                if (grid[i][j] == '1') { // 发现未访问的陆地
13                    dfs(grid, i, j);
14                    islands++;
15                }
16            }
17        }
18        return islands;
19    }
20  
21    private void dfs(char[][] grid, int x, int y) {
22        // 标记当前格子为已访问（直接修改网格）
23        grid[x][y] = '0';
24        // 遍历四个方向
25        for (int i = 0; i < 4; i++) {
26            int nx = x + dx[i];
27            int ny = y + dy[i];
28            // 检查是否越界或是否为陆地
29            if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == '1') {
30                dfs(grid, nx, ny);
31            }
32        }
33    }
34}

DFS
经典连通量问题

腐烂的橘子

 0class Solution {
 1    int[] dx = new int[]{1, 0, -1, 0}; 
 2    int[] dy = new int[]{0, -1, 0, 1};
 3
 4    public int orangesRotting(int[][] grid) {
 5        int m = grid.length;
 6        int n = grid[0].length;
 7        Deque<int[]> queue = new LinkedList<>();
 8        int freshCount = 0; // 统计新鲜橘子数量
 9        boolean[][] visited = new boolean[m][n];
10        // 统计新鲜橘子和初始腐烂橘子
11        for (int i = 0; i < m; i++) {
12            for (int j = 0; j < n; j++) {
13                if (grid[i][j] == 1) {
14                    freshCount++;
15                } else if (grid[i][j] == 2) {
16                    queue.add(new int[]{i, j}); // 将所有腐烂橘子加入队列
17                    visited[i][j] = true; // 标记初始腐烂橘子
18                }
19            }
20        }
21        int time = 0; // 时间计数
22        // 运行 BFS
23        while (!queue.isEmpty()) {
24            int size = queue.size();
25            boolean hasNewRotten = false; // 是否有新的腐烂橘子
26            for (int i = 0; i < size; i++) {
27                int[] curr = queue.poll();
28                int x = curr[0], y = curr[1];
29                // 检查四个方向
30                for (int j = 0; j < 4; j++) {
31                    int nx = x + dx[j];
32                    int ny = y + dy[j];
33                    // 跳过越界或已访问或非新鲜橘子
34                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny] || grid[nx][ny] != 1) {
35                        continue;
36                    }
37                    // 新鲜橘子变为腐烂
38                    grid[nx][ny] = 2;
39                    visited[nx][ny] = true;
40                    queue.add(new int[]{nx, ny});
41                    freshCount--; // 减少新鲜橘子计数
42                    hasNewRotten = true; // 标记有新的腐烂橘子
43                }
44            }
45            // 只有当有新的腐烂橘子时才增加时间（关键）
46            if (hasNewRotten) {
47                time++;
48            }
49        }
50        // 如果仍有新鲜橘子未腐烂，返回 -1
51        return freshCount == 0 ? time : -1;
52    }
53}

BFS
有一个关键点是在每一次腐烂的过程中，需要通过 hasNewRotten 变量来判断是否有新的橘子被腐烂然后才增加时间。

课程表

 0class Solution {
 1    public boolean canFinish(int numCourses, int[][] prerequisites) {
 2        // 初始化邻接表和入度数组
 3        Map<Integer, List<Integer>> adjList = new HashMap<>();
 4        int[] indegree = new int[numCourses];
 5        // 构建图：记录课程依赖关系并统计入度
 6        for (int[] pre : prerequisites) {
 7            int course = pre[1]; // 被依赖的课程
 8            int prereq = pre[0]; // 前置课程
 9            adjList.computeIfAbsent(prereq, k -> new ArrayList<>()).add(course);
10            indegree[course]++;
11        }
12        // 将入度为0的课程加入队列
13        Queue<Integer> queue = new LinkedList<>();
14        for (int i = 0; i < numCourses; i++) {
15            if (indegree[i] == 0) {
16                queue.offer(i);
17            }
18        }
19        // BFS处理课程
20        int completedCourses = 0;
21        while (!queue.isEmpty()) {
22            int current = queue.poll();
23            completedCourses++;
24            // 处理依赖当前课程的后续课程
25            List<Integer> dependents = adjList.getOrDefault(current, Collections.emptyList());
26            for (int next : dependents) {
27                indegree[next]--;
28                if (indegree[next] == 0) {
29                    queue.offer(next);
30                }
31            }
32        }
33        // 判断是否所有课程都能完成
34        return completedCourses == numCourses;
35    }
36}

拓扑排序
BFS 解决拓扑排序，统计入度节点和邻接边，队列里记录入度为 0 的节点（可处理课程）。

实现 Trie (前缀树)

 0class Trie {
 1    // 先创建 node 节点的数据结构
 2    public class Node {
 3        Node[] son = new Node[26];
 4        boolean end = false;
 5    }
 6    public Node root;
 7
 8    public Trie() {
 9        // 初始化 root
10        root = new Node();
11    }
12
13    public void insert(String word) {
14        Node cur = root;
15        for(char c : word.toCharArray()) {
16	        int index = c-'a';
17            if(cur.son[index] == null){
18                cur.son[index] = new Node();
19            }
20            cur = cur.son[index];
21        }
22        // 完整单词
23        cur.end = true;
24    }
25    
26    public boolean search(String word) {
27        return find(word) == 1;
28    }
29    
30    public boolean startsWith(String prefix) {
31        return find(prefix) != 0;
32    }
33    
34    // 搜索前缀树
35    public int find(String word) {
36        Node cur = root;
37        for(char c : word.toCharArray()) {
38        	int index = c-'a';
39            if(cur.son[index] == null) {
40                // 不存在当前字符
41                return 0;
42            }
43            cur = cur.son[index];
44        }
45        // 完整单词
46        if(cur.end == true) return 1;
47        // 只是字符前缀匹配
48        return 2;
49    }
50}

题解
二十六叉树

回溯

全排列

 0class Solution {
 1    public List<List<Integer>> res = new ArrayList<>();
 2    public boolean[] st;
 3    public List<List<Integer>> permute(int[] nums) {
 4        st = new boolean[nums.length];
 5        dfs(nums,new ArrayList());
 6        return res;
 7    }
 8
 9    public void dfs(int[] nums,List<Integer> path){
10        if(path.size() >= nums.length) {
11            res.add(new ArrayList(path));
12            return;
13        }
14        for(int i = 0; i < nums.length; i++){
15            if(st[i]) continue;
16            st[i] = true;
17            path.add(nums[i]);
18            dfs(nums,path);
19            st[i] = false;
20            path.remove(path.size() - 1);
21        }
22    }
23}

回溯算法总结

子集

 0class Solution {
 1    public List<List<Integer>> res = new ArrayList<>();
 2    public List<List<Integer>> subsets(int[] nums) {
 3        res.add(new ArrayList());
 4        dfs(nums,0,new ArrayList());
 5        return res;
 6    }
 7
 8    public void dfs(int[] nums,int startIndex,List<Integer> node){
 9        if(node.size() >= nums.length) {
10            return;
11        }
12        for(int i = startIndex; i < nums.length; i++){
13            node.add(nums[i]);
14            res.add(new ArrayList(node));
15            dfs(nums,i + 1,node);
16            node.remove(node.size() - 1);
17        }
18    }
19}

回溯算法总结
注意 startIndex 是 i + 1，也就是下一层遍历从 num[i+1] 开始

电话号码的字母组合

 0class Solution {
 1    public List<String> res = new ArrayList<>();
 2    public String[] phone;
 3    public List<String> letterCombinations(String digits) {
 4        int n = digits.length();
 5        if(n == 0) return res;
 6        phone = new String[] {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
 7        dfs(digits,0,"");
 8        return res;
 9    }
10
11    public void dfs(String digits,int index,String ans){
12        if(ans.length() >= digits.length()){
13            res.add(ans);
14            return;
15        }
16        String arr = phone[digits.charAt(index) - '0'];
17        for(int i = 0; i < arr.length(); i++) {
18            dfs(digits,index + 1,ans + arr.charAt(i));
19        }
20    }
21}

通过递归来 n 重循环
每一层是 phone[digits.charAt(index) - '0']，不再是同一数组

组合总和

 0class Solution {
 1    public List<List<Integer>> res = new ArrayList<>();
 2    public int goal;
 3    public List<List<Integer>> combinationSum(int[] candidates, int target) {
 4        Arrays.sort(candidates);
 5        goal = target;
 6        dfs(candidates,0,0,new ArrayList());
 7        return res;
 8    }
 9
10    public void dfs(int[] candidates,int sum,int startIndex,List<Integer> ans){
11        if(sum > goal){
12            return;
13        }else if(sum == goal){
14            res.add(new ArrayList(ans));
15            return;
16        }
17
18        for(int i = startIndex; i < candidates.length; i++) {
19            sum += candidates[i];
20            if(sum > goal) break;
21            ans.add(candidates[i]);
22            // 这个 i 是关键,避免重复搜索
23            dfs(candidates,sum,i,ans);
24            sum -= candidates[i];
25            ans.remove(ans.size() - 1);
26        }
27    }
28}

startIndex 不是 i + 1，因为可以重复选自己；为了不递归重复答案，不能重复选前面已经选过的，所以每一层从 i 开始遍历。

括号生成

方法一：

 0class Solution {
 1    public List<String> res = new ArrayList<>();
 2    public int goal;
 3    public List<String> generateParenthesis(int n) {
 4        if(n == 1) {
 5            res.add("()");
 6            return res;
 7        }
 8        goal = n;
 9        dfs(new char[]{'(',')'},0,0,"");
10        return res;
11    }
12
13    public void dfs(char[] arr,int l,int r,String ans) {
14        if(ans.length() > 0 && ans.charAt(0) == ')') return;
15        // 右括号的个数不能超过左括号的个数。比如 ())( 是不合法的
16        if(l > goal || r > goal || r > l) return;
17        while(l == goal && r != goal) {
18            ans += ')';
19            r ++;
20        }
21        if(l == goal && r == goal){            
22            res.add(ans);
23            return;
24        }
25
26        for(int i = 0; i < 2; i++){
27            if(arr[i] == '(') l++;
28            else r++;
29            dfs(arr,l,r,ans + arr[i]);
30            if(arr[i] == '(') l--;
31            else r--;
32        }
33    }
34}

关键：if(r > l) return，省去了判断是否有效括号对这一步。

方法二：

 0class Solution {
 1    public List<String> generateParenthesis(int n) {
 2        char[] path = new char[2*n];
 3        List<String> ans = new ArrayList<>();
 4        int left=0,rigth=0;
 5        backtrack(left,rigth,n,ans,path);
 6        return ans;
 7    }        
 8
 9        private void backtrack(int left,int rigth,int n,List<String> ans,char[] path){
10        if(rigth==n){
11            ans.add(new String(path));
12        }
13        if(left<n){
14            path[left+rigth]='(';
15            backtrack(left+1,rigth,n,ans,path);
16        }
17        if(rigth<left){
18            path[left+rigth]=')';
19            backtrack(left,rigth+1,n,ans,path);
20        }
21    }
22}

题解

单词搜索

 0class Solution {
 1    public boolean[][] st;
 2    public int[] dx = new int[] {0,1,0,-1};
 3    public int[] dy = new int[] {1,0,-1,0};
 4    public boolean res = false;
 5
 6    public boolean exist(char[][] board, String word) {
 7        int m = board.length;
 8        int n = board[0].length;
 9        st = new boolean[m][n];
10        char[] words = word.toCharArray();
11        for(int i = 0; i<m; i++){
12            for(int j = 0; j<n; j++){
13                if(board[i][j] == words[0]) {
14                    st[i][j] = true;
15                    dfs(i,j,board,1,words);
16                    st[i][j] = false;
17                    if(res) {
18                        break;
19                    }
20                }
21            }
22        }
23        return res;
24    }
25
26    public void dfs(int x, int y,char[][] board,int index,char[] word) {
27        if(res) {
28            return;
29        }
30        if(index >= word.length) {
31            res = true;
32            return;
33        }
34        for(int i = 0; i < 4; i++) {
35            int x1 = x + dx[i];
36            int y1 = y + dy[i];
37            if(x1 < 0 || x1 >= board.length || y1 < 0 || y1 >= board[0].length) {
38                continue;
39            }
40            if(st[x1][y1] || board[x1][y1] != word[index]) {
41                continue;
42            }
43            st[x1][y1] = true;
44            dfs(x1,y1,board,index + 1,word);
45            st[x1][y1] = false;
46        }
47    }
48}

对于每一个 word[0] 都需要进行一次搜索
通过 index 控制下一个字母是否符合搜索条件 board[x1][y1] == word[index]

分割回文串

 0class Solution {
 1    public List<List<String>> res = new ArrayList<>();
 2
 3    public List<List<String>> partition(String s) {
 4        dfs(s,0,new ArrayList<>());
 5        return res;
 6    }
 7  
 8    public void dfs(String s,int startIndex,List<String> path) {
 9        if(startIndex >= s.length()) {
10            res.add(new ArrayList(path));
11            return;
12        }
13        for(int i = startIndex; i < s.length(); i++) {
14	        // 插板，得到子集
15            String son = s.substring(startIndex,i + 1);
16            // 回文子串
17            if(isValid(son)){
18                path.add(son);
19                dfs(s,i + 1,path);
20                path.removeLast();
21            }
22        }
23    }
24
25    public boolean isValid(String str) {
26        if(str == null || str.isEmpty()) {
27            return false;
28        }
29        String reversed = new StringBuilder(str).reverse().toString();
30        return str.equals(reversed);
31    }
32}

递归的过程相当于在每个字母之间插板，选取插板得到的回文子串再递归

N 皇后

 0class Solution {
 1    public char[][] chess;
 2    public List<List<String>> res = new ArrayList<>();
 3    public boolean[] st;
 4    
 5    public List<List<String>> solveNQueens(int n) {
 6        chess = new char[n][n];
 7        st = new boolean[n];
 8        for(int i = 0; i < n; i++) {
 9            for(int j = 0; j < n; j++) {
10                chess[i][j] = '.';
11            }
12        }
13        dfs(0);
14        return res;
15    }
16  
17    public void dfs(int row) {
18        if(row >= chess.length) {
19            List<String> ans = new ArrayList<>();
20            for(char[] c : chess) {
21                ans.add(new String(c));
22            }
23            res.add(ans);
24            return;
25        }
26  
27        for(int i = 0; i < chess.length; i++){
28            if(isValid(row,i)) {
29                st[i] = true;
30                chess[row][i] = 'Q';
31                dfs(row + 1);
32                st[i] = false;
33                chess[row][i] = '.';
34            }
35        }
36    }
37
38    public boolean isValid(int x,int y){
39        if(st[y]) {
40            return false;
41        }
42        for(int i = x-1,j = y-1; i>=0 && j>=0; i--,j--) {
43            if(chess[i][j] == 'Q') return false;
44        }
45        for(int i = x-1, j = y+1; i>=0 && j<chess.length; i--,j++){
46            if(chess[i][j] == 'Q') return false;
47        }
48        return true;
49    }
50}

树的高度是棋盘的行，宽度是棋盘的宽
通过列状态数组，避免一次循环判断

二分查找

搜索插入位置

 0class Solution {
 1    public int searchInsert(int[] nums, int target) {
 2        int n = nums.length;
 3        int l = -1;
 4        int r = n;
 5        while(l + 1 < r) {
 6            int mid = (l + r) >> 1;
 7            if(nums[mid] <= target) {
 8                l = mid;
 9            }else {
10                r = mid;
11            }
12        }
13        // 边界条件
14        if(l == -1) return 0;
15        return nums[l] == target ? l : l + 1;
16    }
17}

这个二分模板最好记，哔哩哔哩搜“五点七边”的二分视频
注意 l == -1 的边界条件

搜索二维矩阵

 0class Solution {
 1    public boolean searchMatrix(int[][] matrix, int target) {
 2        int m = matrix.length;
 3        int n = matrix[0].length;
 4        int i = 0;
 5        int j = n - 1;
 6        while(i < m &&  j >= 0) {
 7            if(matrix[i][j] > target) {
 8                j --;
 9                continue;
10            }
11            if(matrix[i][j] < target) {
12                i ++;
13                continue;
14            }
15            return true;
16        }
17        return false;
18    }
19}

二叉搜索树的思路
二分的做法，1、将二维变为一维数组，然后二分；2、先对第一列二分得到 matrix[0][i] <= target，然后再二分第 i 行。

在排序数组中查找元素的第一个和最后一个

 0class Solution {
 1    public int[] searchRange(int[] nums, int target) {
 2	    // >= target 和 >= target + 1 两种边界情况
 3        int start = f(nums,target,true); // 开始位置
 4        int end = f(nums,target + 1,false); // 结束位置
 5        return new int[]{start,end};
 6    }
 7
 8    public int f(int[] nums, int target,boolean flag) {
 9        int n = nums.length;
10        if(n == 0) return -1;
11        int l = -1;
12        int r = n;
13        while(l + 1 < r) {
14            int mid = (l + r) >> 1;
15            if(nums[mid] >= target) {
16                r = mid;
17            }else{
18                l = mid;
19            }
20        }
21        if(r != n && flag && nums[r] == target) return r;
22        if(l != -1 && !flag && nums[l] == target - 1) return l;
23        return -1;
24    }
25}

分别二分 target 和 target + 1

搜索旋转排序数组

 0class Solution {
 1    public int search(int[] nums, int target) {
 2        int n = nums.length;
 3        int k = 0;
 4        for(int i = 1; i < n; i ++){
 5            if(nums[i] < nums[i-1]) {
 6                k = i;
 7                break;
 8            }
 9        }
10        int l1 = binaryS(nums,target,-1,k);
11        if(l1 != -1 && nums[l1] == target) {
12            return l1;
13        }
14        int l2 = binaryS(nums,target,k-1,n);
15        if(l2 != -1 && nums[l2] == target) {
16            return l2;
17        }
18        return -1;
19    }
20
21    public int binaryS(int[] nums,int target,int l,int r) {
22        while(l + 1 < r) {
23            int mid = (l + r) >> 1;
24            if(nums[mid] <= target) {
25                l = mid;
26            }else{
27                r = mid;
28            }
29        }
30        return l;
31    }
32}

找到切割点 k，然后分别二分左右两个有序数组

寻找旋转排序数组中的最小值

 0class Solution {
 1    public int findMin(int[] nums) {
 2        int n = nums.length;
 3        int l = 0;
 4        int r = n;
 5        while(l + 1 < r) {
 6            int mid = (l + r) >> 1;
 7            if(nums[mid] > nums[n-1]){
 8                l = mid;
 9            }else{
10                r = mid;
11            }
12        }
13        if(l == -1 || n == 1) {
14            return nums[0];
15        }
16        return nums[l] > nums[l + 1] ? nums[l+1] : nums[l];
17    }
18}

题解
还可以直接双指针前后判断二种情况（旋转后不变、旋转后改变）

寻找两个正序数组的中位数

 0class Solution {
 1    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 2        int m = nums1.length;
 3        int n = nums2.length;
 4        int[] nums = new int[m+n];
 5        int i = 0;
 6        int j = 0;
 7        int index = 0;
 8        while(i < m && j < n) {
 9            if(nums1[i] > nums2[j]) {
10                nums[index++] = nums2[j++];
11            }else{
12                nums[index++] = nums1[i++];
13            }
14        }
15        while (i < m) {
16            nums[index++] = nums1[i++];
17        }
18        while (j < n) {
19            nums[index++] = nums2[j++];
20        }
21        if(index % 2 == 0) {
22            return (nums[(m+n) / 2] + nums[(m+n) / 2 - 1]) * 1.0 / 2;
23        }
24        return nums[(m+n) / 2] * 1.0;
25    }
26}

先归并后判断

栈

有效的括号

 0class Solution {
 1    public boolean isValid(String s) {
 2        int n = s.length();
 3        if (n % 2 == 1) {
 4            return false;
 5        }
 6        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
 7            put(')', '(');
 8            put(']', '[');
 9            put('}', '{');
10        }};
11        Deque<Character> stack = new LinkedList<Character>();
12        for (int i = 0; i < n; i++) {
13            char ch = s.charAt(i);
14            if (pairs.containsKey(ch)) {
15                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
16                    return false;
17                }
18                stack.pop();
19            } else {
20                stack.push(ch);
21            }
22        }
23        return stack.isEmpty();
24    }
25}

利用栈的先进后出特性

最小栈

方法一：

 0class MinStack {
 1    Deque<Integer> xStack;
 2    Deque<Integer> minStack;
 3
 4    public MinStack() {
 5        xStack = new LinkedList<Integer>();
 6        minStack = new LinkedList<Integer>();
 7        minStack.push(Integer.MAX_VALUE);
 8    }
 9    
10    public void push(int x) {
11        xStack.push(x);
12        minStack.push(Math.min(minStack.peek(), x));
13    }
14    
15    public void pop() {
16        xStack.pop();
17        minStack.pop();
18    }
19    
20    public int top() {
21        return xStack.peek();
22    }
23    
24    public int getMin() {
25        return minStack.peek();
26    }
27}

利用一个辅助栈记录每一个进栈元素对应的当前最小值

方法二：

 0class MinStack {
 1    private Deque<Long> stack;
 2    private long minValue;
 3
 4    public MinStack() {
 5        stack = new LinkedList<>();
 6    }
 7    
 8    public void push(int val) {
 9        if (stack.isEmpty()) {
10            minValue = val;
11            stack.push(0L);
12        } else {
13            long diff = (long) val - minValue;
14            stack.push(diff);
15            if (diff < 0) {
16                minValue = val;
17            }
18        }
19    }
20    
21    public void pop() {
22        if (!stack.isEmpty()) {
23            long diff = stack.pop();
24            if (diff < 0) {
25                minValue = minValue - diff;
26            }
27        }
28    }
29    
30    public int top() {
31        long diff = stack.peek();
32        if (diff >= 0) {
33            return (int) (minValue + diff);
34        } else {
35            return (int) minValue;
36        }
37    }
38    
39    public int getMin() {
40        return (int) minValue;
41    }
42}

通过 long diff = (long) val - minValue 来达到同样效果，注意当栈为空时需要 stack.push(0L);，来统一通过 diff 获取栈顶值。

字符串解码

 0class Solution {
 1    public String decodeString(String s) {
 2        Deque<Character> stack = new LinkedList<>();
 3        
 4        for (int i = 0; i < s.length(); i++) {
 5            char c = s.charAt(i);
 6            if (c != ']') {
 7                stack.push(c);
 8            } else {
 9                // 1. 提取字母
10                StringBuilder strBuilder = new StringBuilder();
11                while (!stack.isEmpty() && stack.peek() != '[') {
12                    strBuilder.append(stack.pop());
13                }
14                String str = strBuilder.reverse().toString(); // 反转回正确顺序
15                
16                // 2. 移除 '['
17                if (!stack.isEmpty()) stack.pop();
18                
19                // 3. 提取数字（可能是多位数）
20                StringBuilder numBuilder = new StringBuilder();
21                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
22                    numBuilder.append(stack.pop());
23                }
24                int times = Integer.parseInt(numBuilder.reverse().toString()); // 反转回正确顺序
25                
26                // 4. 重复字符串并重新压入栈中
27                String repeated = str.repeat(times);
28                for (int j = 0; j < repeated.length(); j++) {
29                    stack.push(repeated.charAt(j));
30                }
31            }
32        }
33        
34        // 构建最终结果
35        StringBuilder res = new StringBuilder();
36        while (!stack.isEmpty()) {
37            res.append(stack.pop());
38        }
39        return res.reverse().toString(); // 需要反转，因为栈是后进先出
40    }
41}

模拟
注意字符出栈后需要反转，其次提取的数字可能十多位数（也需要反转）

每日温度

 0class Solution {
 1    public int[] dailyTemperatures(int[] temperatures) {
 2        int n = temperatures.length;
 3        Deque<Integer> stack = new LinkedList<>();
 4        int[] res = new int[n];
 5        for(int i = n-1; i >= 0; i--) {
 6            if(stack.isEmpty()) {
 7                res[i] = 0;
 8            }else{
 9                while(!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) {
10                    stack.pop();
11                }
12                res[i] = stack.isEmpty() ? 0 : stack.peek() - i;         
13            }
14            // 保存元素 index,方便计算相差天数
15            stack.push(i);
16        }
17        return res;
18    }
19}

正序遍历方式

 0class Solution {
 1    public int[] dailyTemperatures(int[] temperatures) {
 2        int length = temperatures.length;
 3        int[] ans = new int[length];
 4        Deque<Integer> stack = new LinkedList<Integer>();
 5        for (int i = 0; i < length; i++) {
 6            int temperature = temperatures[i];
 7            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
 8                int prevIndex = stack.pop();
 9                ans[prevIndex] = i - prevIndex;
10            }
11            stack.push(i);
12        }
13        return ans;
14    }
15}

单调栈，单调栈能够让不需要你需要走重复走的路，刚刚走过一遍的路可以造福后面人。
通过保存元素 index 计算天数

总结

1、什么时候用单调栈？答: 对于求某元素左边和右边第一个比它大或第一个比它小的元素位置（值）时，都可以使用单调栈，比如说“接雨水”这题。

2、单挑递增栈和单调递减栈分别对应那种情况？答：对于求当前元素左/右两边第一个比它大的元素，使用单挑递增栈。反之，用单调递减栈。

柱状图中最大的矩形

 0class Solution {
 1    public int largestRectangleArea(int[] heights) {
 2        int n = heights.length;
 3        if(n == 1) return heights[0];
 4        int[] left = new int[n];
 5        int[] rigth = new int[n];
 6        Deque<Integer> stack = new LinkedList<>();
 7        for(int i = n-1; i >= 0; i--) {
 8            if(stack.isEmpty()) {
 9                rigth[i] = n - i - 1;
10            }else{
11                while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
12                    stack.pop();
13                }
14                rigth[i] = stack.isEmpty() ? n - i - 1 : stack.peek() - i - 1;
15            }
16            stack.push(i);
17        }
18        stack.clear();
19        for(int i = 0; i < n; i++) {
20            if(stack.isEmpty()) {
21                left[i] = i;
22            }else{
23                while(!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
24                    stack.pop();
25                }
26                left[i] = stack.isEmpty() ? i : i - stack.peek() - 1;
27            }
28            stack.push(i);
29        }
30        int max = Integer.MIN_VALUE;
31        for(int i = 0; i < n; i++) {
32            max = Math.max(max,heights[i] * (1 + left[i] + rigth[i]));
33        }
34
35        return max;
36    }
37}

题解
先理解暴力做法：枚举每个heights[i]然后求最大宽度，也就是向左/右遍历找最近小于heights[i]的位置
单调栈做法：通过单调栈减少不必要的比较（只需要找小于heights[i]最近的索引）

堆

数组中的第K个最大元素

快速排序板子：

 0class Solution {
 1    public int findKthLargest(int[] nums, int k) {
 2        quicksort(nums,0,nums.length - 1);
 3        return nums[nums.length - k];
 4    }
 5    
 6    public void quicksort(int[] nums,int left,int right) {
 7        if(left >= right) {
 8            return;
 9        }
10        // 求基准值
11        setPivot(nums,left,right);
12        // 分区
13        int pivotIndex = partition(nums,left,right);
14        quicksort(nums,left,pivotIndex - 1);
15        quicksort(nums,pivotIndex + 1,right);
16    }
17
18    // 挖坑法分区
19    public int partition(int[] nums, int left, int right) {
20    int pivot = nums[left];
21    int i = left;
22    int j = right;
23    while (i < j) {
24        while (i < j && nums[j] >= pivot) {
25            j--;
26        }
27        if (i < j) {
28            nums[i] = nums[j];
29            i++;
30        }
31        while (i < j && nums[i] <= pivot) {
32            i++;
33        }
34        if (i < j) {
35            nums[j] = nums[i];
36            j--;
37        }
38    }
39    // 循环结束时，i 和 j 相遇，此时 i (或 j) 就是 pivot 最终的位置
40    nums[i] = pivot;
41    return i;
42}
43
44    // 三数取中法取 pivot,然后设置 nums[left] = pivot;
45    public void setPivot(int[] nums,int left,int right) {
46        int valLeft = nums[left];
47        int valRight = nums[right];
48        int valMid = nums[left + (right - left) / 2];
49        int maxVal = Math.max(valLeft, Math.max(valRight, valMid));
50        int minVal = Math.min(valLeft, Math.min(valRight, valMid));
51        nums[left] = valLeft + valRight + valMid - maxVal - minVal;
52        if(nums[left] == valLeft) return;
53        if(nums[left] == valRight) {
54            nums[right] = valLeft;
55            return;
56        }
57        nums[left + (right - left) / 2] = valLeft;
58    }
59}

时间复杂度：$O(NlogN)$
需要知道每次选取的基准值在分区后的位置不会再改变
不稳定排序

快速选择算法：

 0class Solution {
 1    public int findKthLargest(int[] nums, int k) {
 2        return quickselect(nums, 0, nums.length - 1, nums.length - k);
 3    }
 4    
 5    public int quickselect(int[] nums,int left,int right,int targetIndex) {
 6        if(left >= right) {
 7            return nums[left];
 8        }
 9        // 设置 nums[left] = pivot
10        setPivot(nums,left,right);
11        // 分区
12        int pivotIndex = partition(nums,left,right);
13        // 选择分区
14        if(pivotIndex == targetIndex) {
15            return nums[pivotIndex];
16        }else if(pivotIndex < targetIndex) {
17            return quickselect(nums,pivotIndex + 1,right,targetIndex);
18        }else {
19            return quickselect(nums,left,pivotIndex - 1,targetIndex);
20        }
21    }
22
23    // 挖坑法
24    public int partition(int[] nums, int left, int right) {
25    int pivot = nums[left];
26    int i = left;
27    int j = right;
28    while (i < j) {
29        while (i < j && nums[j] >= pivot) {
30            j--;
31        }
32        if (i < j) {
33            nums[i] = nums[j];
34            i++;
35        }
36        while (i < j && nums[i] <= pivot) {
37            i++;
38        }
39        if (i < j) {
40            nums[j] = nums[i];
41            j--;
42        }
43    }
44    // 循环结束时，i 和 j 相遇，此时 i (或 j) 就是 pivot 最终的位置
45    nums[i] = pivot;
46    return i;
47}
48
49    // 三数取中法求 pivot
50    public void setPivot(int[] nums,int left,int right) {
51        int valLeft = nums[left];
52        int valRight = nums[right];
53        int valMid = nums[left + (right - left) / 2];
54        int maxVal = Math.max(valLeft, Math.max(valRight, valMid));
55        int minVal = Math.min(valLeft, Math.min(valRight, valMid));
56        nums[left] = valLeft + valRight + valMid - maxVal - minVal;
57        if(nums[left] == valLeft) return;
58        if(nums[left] == valRight) {
59            nums[right] = valLeft;
60            return;
61        }
62        nums[left + (right - left) / 2] = valLeft;
63    }
64}

根据基准值的索引和目标索引判断来选择性的分区
时间复杂度近似 $O(N)$
本题还可以用堆排序，$O(NlogK)$

前 K 个高频元素

方法一：

 0class Solution {
 1    public int[] topKFrequent(int[] nums, int k) {
 2        // 统计频率
 3        Map<Integer,Integer> map = new HashMap<>();
 4        int n = nums.length;
 5        for(int i = 0; i < n; i++) {
 6            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
 7        }
 8        List<int[]> values = new ArrayList<int[]>();
 9        for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
10            int key = entry.getKey();
11            int count = entry.getValue();
12            values.add(new int[]{key, count});
13        }
14        // 快选
15        int m = values.size();
16        quickselect(values,0,m - 1,m - k);
17        // 收集
18        int[] res = new int[k];
19        for(int i = 0; i < k; i++) {
20            res[i] = values.get(m - k + i)[0];
21        }
22        return res;
23    }
24    
25    public void quickselect(List<int[]> nums,int left,int right,int targetIndex) {
26        if(left >= right) {
27            return;
28        }
29        // 设置 nums[left] = pivot
30        setPivot(nums,left,right);
31        // 分区
32        int pivotIndex = partition(nums,left,right);
33        // 选择分区
34        if(pivotIndex == targetIndex) {
35            return;
36        }else if(pivotIndex < targetIndex) {
37            quickselect(nums,pivotIndex + 1,right,targetIndex);
38        }else {
39            quickselect(nums,left,pivotIndex - 1,targetIndex);
40        }
41    }
42
43    // 挖坑法
44    public int partition(List<int[]> nums, int left, int right) {
45        int[] pivot = nums.get(left);
46        int i = left;
47        int j = right;
48        while (i < j) {
49            while (i < j && nums.get(j)[1] >= pivot[1]) {
50                j--;
51            }
52            if (i < j) {
53                nums.set(i,nums.get(j));
54                i++;
55            }
56            while (i < j && nums.get(i)[1] <= pivot[1]) {
57                i++;
58            }         
59            if (i < j) {
60                nums.set(j,nums.get(i));
61                j--;
62            }
63        }
64        // 循环结束时，i 和 j 相遇，此时 i (或 j) 就是 pivot 最终的位置
65        nums.set(i,pivot); 
66        return i;
67    }
68
69    // 三数取中法求 pivot，并将其交换到 left 位置
70    public void setPivot(List<int[]> nums, int left, int right) {
71        if (left >= right) return;
72        int mid = left + (right - left) / 2;
73        // 确保 nums.get(left).freq <= nums.get(mid).freq <= nums.get(right).freq
74        if (nums.get(left)[1] > nums.get(mid)[1]) {
75            swap(nums, left, mid);
76        }
77        if (nums.get(left)[1] > nums.get(right)[1]) {
78            swap(nums, left, right);
79        }
80        if (nums.get(mid)[1] > nums.get(right)[1]) {
81            swap(nums, mid, right);
82        }
83        swap(nums, left, mid);
84    }
85    // 辅助交换函数
86    public void swap(List<int[]> nums, int i, int j) {
87        int[] temp = nums.get(i);
88        nums.set(i, nums.get(j));
89        nums.set(j, temp);
90    }
91}

快选，targetIndex 前面的元素一定是前 k 个高频率元素
通过排序集合，元素数组可以在排序后知道当前频率对应的 key
注意，通过传递集合排序，分区和取 pivot 时需要交换的应该是数组

方法二：

 0class Solution {
 1    public int[] topKFrequent(int[] nums, int k) {
 2        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
 3        for (int num : nums) {
 4            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
 5        }
 6
 7        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
 8        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
 9            public int compare(int[] m, int[] n) {
10                return m[1] - n[1];
11            }
12        });
13        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
14            int num = entry.getKey(), count = entry.getValue();
15            // 维护前k个高频数组元素
16            if (queue.size() == k) {
17                if (queue.peek()[1] < count) {
18                    queue.poll();
19                    queue.offer(new int[]{num, count});
20                }
21            } else {
22                queue.offer(new int[]{num, count});
23            }
24        }
25        int[] ret = new int[k];
26        for (int i = 0; i < k; ++i) {
27            ret[i] = queue.poll()[0];
28        }
29        return ret;
30    }
31}

题解
利用小根堆的性质，堆顶一定是当前 k 个元素最小值来判断

数据流的中位数

 0class MedianFinder {
 1    private final PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a); // 最大堆
 2    private final PriorityQueue<Integer> right = new PriorityQueue<>(); // 最小堆
 3
 4    public void addNum(int num) {
 5        if (left.size() == right.size()) {
 6            right.offer(num);
 7            left.offer(right.poll());
 8        } else {
 9            left.offer(num);
10            right.offer(left.poll());
11        }
12    }
13
14    public double findMedian() {
15        if (left.size() > right.size()) {
16            return left.peek();
17        }
18        return (left.peek() + right.peek()) / 2.0;
19    }
20}

题解
大根堆+小根堆

贪心

买卖股票的最佳时机

 0class Solution {
 1    public int maxProfit(int[] prices) {
 2        int res = 0;
 3        int n = prices.length;
 4        int max = prices[n - 1];
 5        for(int i = n - 1; i >= 0; i--) {
 6            if(prices[i] < max) {
 7                res = Math.max(res,max - prices[i]);
 8            }else{
 9                max = prices[i];
10            }
11        }
12        return res;
13    }
14}

当天买入的最佳利润应该等后续股票价格的最大值减去当天的价格，也就是 $max - prices[i]$，所以维护 i 之后的股票价格即可

跳跃游戏

 0class Solution {
 1    public boolean canJump(int[] nums) {
 2        int n = nums.length;
 3        int idx = n - 1;
 4        for(int i = n - 2; i >= 0; i --) {
 5            if(i + nums[i] >= idx) {
 6                idx = i;
 7            }
 8        }
 9        return idx == 0;
10    }
11}

从后向前遍历，如果当前位置移动的最远距离大于等于目标位置（idx），则能否从 0 到 idx 变为了求从 0 到 i

跳跃游戏 II

 0class Solution {
 1    public int jump(int[] nums) {
 2        int n = nums.length;
 3        int t = n - 1;
 4        int res = 0;
 5        for(int i = 0; i < n-1; i++) {
 6            if(i + nums[i] >= t) {
 7                t = i;
 8                res ++;
 9                i = -1;
10            }
11            if(t == 0) {
12                break;
13            }
14        }
15        return res;
16    }
17}

每次都从头走，找到可以到达 t 的最近 i，直到 i = 0。

划分字母区间

 0class Solution {
 1    public List<Integer> partitionLabels(String S) {
 2        char[] s = S.toCharArray();
 3        int n = s.length;
 4        int[] last = new int[26];
 5        for (int i = 0; i < n; i++) {
 6            last[s[i] - 'a'] = i; // 每个字母最后出现的下标
 7        }
 8
 9        List<Integer> ans = new ArrayList<>();
10        int start = 0, end = 0;
11        for (int i = 0; i < n; i++) {
12            end = Math.max(end, last[s[i] - 'a']); // 更新当前区间右端点的最大值
13            if (end == i) { // 当前区间合并完毕
14                ans.add(end - start + 1); // 区间长度加入答案
15                start = i + 1; // 下一个区间的左端点
16            }
17        }
18        return ans;
19    }
20}
21
22// 同样的方法，不过这个思路简单
23
24class Solution {
25    public List<Integer> partitionLabels(String s) {
26         List<Integer> res = new ArrayList<>();
27         int n = s.length();
28         int next = -1;
29         int last = 0;
30         for(int i = 0; i < n; i ++) {
31            char c = s.charAt(i);
32            next = Math.max(next,s.lastIndexOf(c));
33            if(i == next) {
34                res.add(next - last + 1);
35                last = next + 1;
36                next = -1;
37            }
38        }
39        return res;
40    }
41}

题解
合并区间
第二个方法，next 是我们字符放的最远的位置， last 是划分字符串之前的位置；当 i = next 时，说明后面不再会出现前面的相同字符。第一个相当于优化了 s.lastIndexOf(c) 求解。

动态规划

背包问题

DFS -> 记忆化搜索 -> 递推（将 DFS 1:1 翻译） -> 空间优化。

如何确定递归边界、递归入口等。

关键中在于 $dfs(i,v) = Math.max(dfs(i-1,v),dfs(i-1,v-nums[i]) + value[i])$ 这个转移方程。

完全背包：$dfs(i,v) = Math.max(dfs(i-1,v),dfs(i,v-nums[i]) + value[i])$ 。

爬楼梯

 0class Solution {
 1    public int climbStairs(int n) {
 2        if (n == 0) {
 3            return 0; // 或者根据题目定义，如果 n=0 算作 1 种方法（不走）
 4        }
 5        if (n == 1) {
 6            return 1;
 7        }
 8        // dp[i] 存储到达第 i 级台阶的方法数
 9        int[] dp = new int[n + 1];
10        // 基本情况
11        dp[0] = 1; // 理论上到达第0级台阶只有一种方法（不走），方便计算dp[2]
12        dp[1] = 1; // 到达第1级台阶只有一种方法 (1步)
13        // 从第2级台阶开始计算
14        for (int i = 2; i <= n; i++) {
15            dp[i] = dp[i - 1] + dp[i - 2];
16        }
17
18        return dp[n];
19    }
20}

斐波那契数列

杨辉三角

 0class Solution {
 1    public List<List<Integer>> generate(int numRows) {
 2        List<List<Integer>> res = new ArrayList<>(numRows);
 3        res.add(List.of(1));
 4        for(int i = 1; i < numRows; i++) {
 5            List<Integer> list = new ArrayList<>(i+1);
 6            list.add(1);
 7            for(int j = 1; j < i; j++) {
 8                // 左上方的数 + 正上方的数
 9                list.add(res.get(i-1).get(j) + res.get(i-1).get(j-1));
10            }
11            list.add(1);
12            res.add(list);
13        }
14        return res;
15    }
16}

理解等式：$c[i][j]=c[i−1][j−1]+c[i−1][j]$，与 $(a+b)^n$ 求组合数系数一致。

打家劫舍

 0class Solution {
 1    public int rob(int[] nums) {
 2        int n = nums.length;
 3        // dp[i] 表示当天“抢和不抢”的最大利益
 4        // 转移方程: 当天抢：dp[i] = nums[i] + dp[i+2]; 不抢 dp[i] = dp[i+1];
 5        int[] dp = new int[n+1];
 6        dp[n-1] = nums[n-1];
 7        for(int i = n-2; i >= 0; i--) {
 8            dp[i] = Math.max(nums[i] + dp[i+2],dp[i+1]);
 9        }
10        return dp[0];
11    }
12}

哈希

双指针

滑动窗口

子串

普通数组

矩阵

链表

二叉树

二叉树的遍历-7种

图论

回溯

二分查找

栈

堆

贪心

动态规划

背包问题

Related Posts