推荐网站

Hello 算法：学习数据结构与算法基础

代码随想录：按照顺序刷题

本文的序号是在力扣题库中的题号，本文的题目顺序是按照代码随想录排列的；但是如果后面的题目可以用前面的算法类似解出，那么该题将不会被记录。

如果题目没有序号，说明该题出自代码随想录。

注意事项

  1. 为了避免大数越界，取中值时采用 m = i + (j - i)/2 来计算中点，而不是 m = (i + j)/2 。
  2. 递归和和迭代是编程方法，往往递归更简洁，迭代更易于理解；分治、回溯、动态规划和贪心是算法。

数组

209长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int minSubArrayLen(int target, int[] nums) {
    // 头尾双指针，比较大小
    int result = nums.length + 1;
    int sum = 0;
    int i = 0;
    for (int j = 0; j < nums.length; j++) {
        sum += nums[j];
        while (sum >= target) {
            result = Math.min(result, j - i + 1);
            sum -= nums[i++];
        }
    }
    return result == nums.length + 1 ? 0 : result;
}

小结

  1. 一道经典数组题目是在一个已经排好序的数组里面找目标值 target，一般采用二分迭代法；其中遵循左闭右开的原则，在迭代时，如果 target 偏大，left = mid + 1；反之，right = mid；循环终止条件是 while (left < right)。

链表

注意

  1. 涉及到对链表节点中的的增删改操作，使用虚拟头节点，如果只是查询，则不需使用。同时，在增删改操作中，如果使用递归，则不需要虚拟头节点，如果使用迭代，则需要。
  2. 链表问题常考虑使用双指针法来解决，例如寻找距离尾部第 K 个节点、寻找环入口、寻找公共尾部入口等。

203移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

img

1
2
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

1
2
输入：head = [], val = 1
输出：[]

示例 3：

1
2
输入：head = [7,7,7,7], val = 7
输出：[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 方式一:递归
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}
// 方式二:迭代
// 使用虚拟头节点可以避免对头结点的单独判断
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }
}
// 不使用虚拟头节点的情况
public ListNode removeElements(ListNode head, int val) {
    // 需要特殊处理头节点
    while (head != null && head.val == val) {
        head = head.next;  // 头节点需要单独处理
    }
    
    if (head == null) return null;
    
    ListNode temp = head;
    while (temp.next != null) {
        if (temp.next.val == val) {
            temp.next = temp.next.next;
        } else {
            temp = temp.next;
        }
    }
    return head;
}

206反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 方式一:递归
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
// 方式二:迭代
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

步骤图解

递归

以反转 1->2->3 为例：

初始状态：

1
1 -> 2 -> 3 -> null

递归到底：

1
2
3
1 -> 2 -> 3 -> null
     ↑
    head (3的next是null，返回3)

回溯第一步（处理节点2）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 -> 2 -> 3 -> null
     ↑    ↑
    head next

head.next.next = head  // 3.next = 2
1 -> 2 -> 3 -> 2 (形成环)
     ↑    ↑
    head next

head.next = null       // 2.next = null
1 -> 2 -> null  ← 3
     ↑         
    head

返回 newHead = 3

回溯第二步（处理节点1）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1 -> 2 -> null  ← 3
↑    ↑
head next

head.next.next = head  // 2.next = 1
1 -> 2 -> 1 (形成环)
↑    ↑
head next

head.next = null       // 1.next = null
null ← 1 ← 2 ← 3
       ↑
      head

返回 newHead = 3

最终结果

1
2
null ← 1 ← 2 ← 3
        (反转完成)
迭代

初始状态

1
2
3
4
5
6
7
prev = null
curr = 1
next = 2

[null]   [1] -> [2] -> [3] -> [4] -> [5] -> null
  ↑       ↑      ↑
 prev    curr   next

第一步操作

1
2
3
4
5
6
7
8
1. 保存next (2)
2. curr.next = prev (1指向null)
3. prev = curr (prev移动到1)
4. curr = next (curr移动到2)

[null] <- [1]   [2] -> [3] -> [4] -> [5] -> null
           ↑     ↑      ↑
          prev  curr   next

第二步操作

1
2
3
[null] <- [1] <- [2]   [3] -> [4] -> [5] -> null
                 ↑     ↑      ↑
                prev  curr   next

继续直到完成

1
2
3
[null] <- [1] <- [2] <- [3] <- [4] <- [5]
                                      ↑
                                     prev

24两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

img

1
2
输入：head = [1,2,3,4]
输出：[2,1,4,3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 方式一:递归
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}
// 方式二:迭代
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            // 因为是要交换两个节点，所以这里有两个
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            // temp每次向后移,选择node1是因为此时node1已在node2之后
            temp = node1;
        }
        return dummyHead.next;
    }
}

步骤图解

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
第1层：swapPairs(1)
  第2层：swapPairs(3)
    第3层：swapPairs(null)  // 3.next = 4，4.next = null，所以传入的是null
    第3层返回：null
    
  第2层执行：
    head = 3, newHead = 4
    head.next = swapPairs(4.next) = swapPairs(null) = null  // 3.next = null
    newHead.next = head  // 4.next = 3
    return newHead  // 返回 4 -> 3 -> null
    
  第2层返回：4 -> 3 -> null

第1层执行：
  head = 1, newHead = 2
  head.next = swapPairs(2.next) = swapPairs(3) 得到的 4->3->null  // 1.next = 4
  newHead.next = head  // 2.next = 1
  return newHead  // 返回 2 -> 1 -> 4 -> 3 -> null

面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

示例 1：

img

1
2
3
4
5
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

142环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    // 两次相遇，追击问题，具体解析见LeetCode的解析
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}
// 解析：
// 采用快慢双节点的方法
// 第一次追击:fast = 2 * slow;两节点相遇时:fast = slow + n * b;可得slow = n * b;
// 第二次追击:此时fast从head开始,slow仍停留在第一次两节点相遇处,两节点同时走,当再次相遇时,slow = a + n * b,快慢节点此时都在环起始处

哈希表

242有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 一增一减
class Solution {
    public boolean isAnagram(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        if (len1 != len2)
            return false;
        HashMap<Character, Integer> dic = new HashMap<>();
        for (int i = 0; i < len1; i++) {
            dic.put(s.charAt(i) , dic.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int i = 0; i < len2; i++) {
            dic.put(t.charAt(i) , dic.getOrDefault(t.charAt(i), 0) - 1);
        }
        for (int val : dic.values()) {
            if (val != 0)
                return false;
        }
        return true;
    }
}

349两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

1
2
3
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 使用HashSet来存储结果（自动去重）
        Set<Integer> resultSet = new HashSet<>();
        // 将nums2转换为HashSet，便于快速查找
        Set<Integer> set2 = new HashSet<>();
        for (int num : nums2) {
            set2.add(num);
        }
        // 遍历nums1，检查元素是否在set2中
        for (int num : nums1) {
            // 只有在set中才有contains方法
            if (set2.contains(num)) {
                resultSet.add(num);
            }
        }
        // 将Set转换为数组
        int[] result = new int[resultSet.size()];
        int index = 0;
        for (int num : resultSet) {
            // 如果是ArrayList的话,可以直接add;但此时要求的返回值是Java自带的数组,没有add方法!
            result[index++] = num;
        }
        return result;
    }
}

202快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isHappy(int n) {
        // 数学上可以证明只要结果不等于1结果一定是遇到了环
        if(n == 0){
            return false;
        }
        Set<Integer> res = new HashSet<>();
        while(n != 1 && !res.contains(n)){
            res.add(n);
            n = sumOfSquare(n);
        }
        return n == 1;
    }
    private int sumOfSquare(int n){
        int temp = 0;
        while(n > 0){
            int num = n%10;
            temp += num * num;
            n = n/10;
        }
        return temp;
    }
}

454四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

1
2
3
4
5
6
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 四数相加直接两两比较
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
        for (int u : A) {
            for (int v : B) {
                countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
            }
        }
        int ans = 0;
        for (int u : C) {
            for (int v : D) {
                if (countAB.containsKey(-u - v)) {
                    ans += countAB.get(-u - v);
                }
            }
        }
        return ans;
    }
}

步骤图解

假设：

1
2
3
4
A = [1, 2]
B = [-2, -1]
C = [-1, 2]
D = [0, 2]

第一步结果（A+B）：

  • 1 + (-2) = -1
  • 1 + (-1) = 0
  • 2 + (-2) = 0
  • 2 + (-1) = 1

countAB = {-1:1, 0:2, 1:1}

第二步查找（C+D = -x）：

  • (-1,0): -( -1+0 ) = 1 → countAB[1] = 1
  • (-1,2): -( -1+2 ) = -1 → countAB[-1] = 1
  • (2,0): -( 2+0 ) = -2 → 不存在
  • (2,2): -( 2+2 ) = -4 → 不存在
    结果 ans = 2

15三数之和(重要)

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }        
        return ans;
    }
}

18四数之和(难题)

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

1
2
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 4) return ans;
        Arrays.sort(nums); // 排序
        
        for (int i = 0; i < len - 3; i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue; 	// 去重
            
            for (int j = i + 1; j < len - 2; j++) {
                if(j > i + 1 && nums[j] == nums[j-1]) continue; 	// 去重
                
                int L = j + 1;
                int R = len - 1;
                
                while (L < R) {
                    // 使用long防止溢出
                    long sum = (long)nums[i] + (long)nums[j] + (long)nums[L] + (long)nums[R];
                    
                    if (sum == target) {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[L], nums[R]));
                        
                        while (L < R && nums[L] == nums[L+1]) L++; 	// 去重
                        while (L < R && nums[R] == nums[R-1]) R--;
                        
                        L++;
                        R--;
                    }
                    else if (sum < target) {
                        L++;
                    }
                    else {
                        R--;
                    }
                }
            }
        }
        return ans;
    }
}

字符串

541反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String reverseStr(String S, int k) {
        char[] s = S.toCharArray();
        int n = s.length;
        for (int i = 0; i < n; i += k * 2) {
            reverse(s, i, Math.min(i + k, n) - 1);
        }
        return new String(s);
    }

    private void reverse(char[] s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }
}

151翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String reverseWords(String s) {
        s = s.trim();                                    // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ') i--;     // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while (i >= 0 && s.charAt(i) == ' ') i--;     // 跳过单词间空格
            j = i;                                       // j 指向下个单词的尾字符
        }
        return res.toString().trim();                    // 转化为字符串并返回
    }
}

步骤图解

输入：" hello world "

  1. trim()后："hello world"
  2. 第一次循环：
    • i从末尾向前移动，找到空格前："world"
    • 添加："world "
  3. 第二次循环：
    • i继续向前，找到下一个单词："hello"
    • 添加："world hello "
  4. 返回："world hello"

28找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

1
2
3
4
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

1
2
3
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 可以直接用java中的indexOf方法，return ss.indexOf(pp);
// 朴素解法
class Solution {
    public int strStr(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        char[] s = ss.toCharArray(), p = pp.toCharArray();
        // 枚举原串的「发起点」
        for (int i = 0; i <= n - m; i++) {
            // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
            int a = i, b = 0;
            while (b < m && s[a] == p[b]) {
                a++;
                b++;
            }
            // 如果能够完全匹配，返回原串的「发起点」下标
            if (b == m) return i;
        }
        return -1;
    }
}

步骤图解

示例1： ss = "hello", pp = "ll"

1
2
3
i=0: h vs l ❌
i=1: e vs l ❌
i=2: l vs l ✓, l vs l ✓ → b=2 == m=2 → 返回 2

KMP方法(待补充)

栈与队列

注意

  1. Hello 算法 中的栈和队列讲解是用链表和数组实现栈和队列的功能，以下的算法题是让栈和队列互相实现彼此。

常用方法

push-入 pop-出 peek-查找
栈 Deque stack= new ArrayDeque<>(); push() pop() peek()
队列 Queue queue = new LinkedList<>(); offer() poll() peek()
双向队列 Deque deque = new LinkedList<>(); offerLast()/offerFirst() pollLast()/pollFirst() peekLast()/peekFirst()

💡 Java 官方文档明确建议：使用 ArrayDeque 来代替 Stack 类实现栈功能。原先的建栈方法如下：

Stack stack = new Stack<>();

232用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MyQueue {
    private Stack<Integer> A;
    private Stack<Integer> B;

    public MyQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }

    public void push(int x) {
        A.push(x);
    }

    public int pop() {
        int peek = peek();
        B.pop();
        return peek;
    }

	public int peek() {
		// 如果输出栈B不为空，队首就是B的栈顶
		if (!B.isEmpty()) return B.peek();
		// 如果B为空且A也为空，队列为空，按题目假设此情况不会发生peek操作
		if (A.isEmpty()) return -1;
		// 核心：当B为空时，将A中所有元素转移到B中
		while (!A.isEmpty()){
			B.push(A.pop());
		}
		// 此时B的栈顶就是原A的栈底，即最先入队的元素
		return B.peek();
	}

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

225用队列实现栈

你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

步骤图解

我们模拟执行 push(1)、push(2)、pop() 的过程：

操作 queue1 的内容 (队首 -> 队尾) queue2 的内容 (队首 -> 队尾) 步骤解释
初始 [] [] 两个队列都为空。
push(1) [1] [] 1. queue2 加入 1 → [1]。 2. queue1 为空，不转移。 3. 交换引用后，queue1 变为 [1]，queue2 变为 []。
push(2) 关键步骤：
[] [2] 1. 先将新元素 2 放入 queue2。
[] [2, 1] 2. 将 queue1 中的 [1] 转移到 queue2，queue2 变为 [2, 1]。
[2, 1] [] 3. 交换引用。现在 queue1 为 [2, 1] (队首 2 是栈顶)，queue2 为空。
pop() [1] [] 直接从 queue1 的队首取出元素 2 并返回。queue1 变为 [1]。

20有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

1
2
输入：s = "()"
输出：true

示例 2：

1
2
输入：s = "()[]{}"
输出：true

示例 3：

1
2
输入：s = "(]"
输出：false

示例 4：

1
2
输入：s = "([])"
输出：true

示例 5：

1
2
输入：s = "([)]"
输出：false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                // 情况一：遇到的是右括号
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                // 情况二：遇到的是左括号
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

1047删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

1
2
3
4
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String removeDuplicates(String s) {
        StringBuffer stack = new StringBuffer();
        int top = -1;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (top >= 0 && stack.charAt(top) == ch) {
                // 情况一：当前字符与栈顶字符相同
                stack.deleteCharAt(top);
                --top;
            } else {
                // 情况二：栈为空，或当前字符与栈顶字符不同
                stack.append(ch);
                // 此处使用 ++top 更多是一种习惯和逻辑上的自然选择。
                ++top;
            }
        }
        return stack.toString();
    }
}

步骤图解

s = "abbaca"

当前字符 ch 栈 stack (左侧是栈底，右侧是栈顶) top 索引 操作与说明
初始 "" (空) -1
‘a’ "a" 0 栈空，直接入栈。
‘b’ "ab" 1 栈顶 ‘a’ ≠ ‘b’，入栈。
‘b’ "a" 0 发现重复：栈顶 ‘b’ == 当前 ‘b’。 删除栈顶 ‘b’，top 变为 0。
‘a’ "" (空) -1 发现重复：栈顶 ‘a’ == 当前 ‘a’。 删除栈顶 ‘a’，top 变为 -1，栈空。
‘c’ "c" 0 栈空，直接入栈。
‘a’ "ca" 1 栈顶 ‘c’ ≠ ‘a’，入栈。

遍历结束，栈中字符为 "ca"，即为最终结果。

为什么不用 Stack 类？

Java 的 Stack 类继承自 Vector，是线程安全的，但在单线程环境下会有不必要的性能开销（如加锁）。它的 push 和 pop 操作也是基于数组的。官方题解中使用 StringBuffer 和整型指针 top 手动模拟，直接操作底层数组，避免了方法调用的开销，是更高效的做法。

150逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

1
2
3
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

1
2
3
4
5
6
7
8
9
10
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
}

步骤图解

以 tokens = ["2", "1", "+", "3", "*"] 为例（对应中缀表达式 (2 + 1) * 3）：

当前 token 栈的操作 栈的内容 (栈底 -> 栈顶) 说明
"2" push(2) 2 数字，直接入栈
"1" push(1) 2, 1 数字，直接入栈
"+" 弹出 1 和 2，计算 2 + 1 = 3，push(3) 3 运算符，进行计算
"3" push(3) 3, 3 数字，直接入栈
"*" 弹出 3 和 3，计算 3 * 3 = 9，push(9) 9 运算符，进行计算

最终栈顶弹出结果 9。

239滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(i > 0 && deque.peekFirst() == nums[i - 1])
                deque.pollFirst();
            // 保持 deque 递减
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.pollLast();
            deque.offerLast(nums[j]);
            // 记录窗口最大值
            if(i >= 0)
                res[i] = deque.peekFirst();
        }
        return res;
    }
}

总结

  1. 每次遍历到一个新值时，要做一个事情：删除队列中所有比这个值小的值。因为这个值入队之后，所以比这个值小的，并且在这个值之前的，都不可能是答案。
  2. 另外，不管最新遍历到的这个值，大小如何，都要加入队列。因为这个值有可能是后面的答案。

347前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

**输入：**nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

**输入：**nums = [1], k = 1

输出：[1]

示例 3：

**输入：**nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

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

步骤图解

输入：nums = [1,1,1,2,2,3], k = 2

  1. 统计频率：{1:3, 2:2, 3:1}
  2. 小顶堆维护过程：
    • 加入[1,3] → 堆：[1,3]
    • 加入[2,2] → 堆：[2,2], [1,3]
    • 遇到[3,1]，堆已满，1<2，不加入
  3. 结果：[2,1] ，因为是小顶堆

二叉树

注意

  1. 二叉树代码使用递归居多

常用代码

1
2
if (root == null)
    return;

二叉树的遍历方式

层序遍历

广度优先（必背）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 层序遍历 */
// 注意层序遍历先让左子节点入队，后让右子节点入队，最后列表中最后一个节点是最右子节点
// 如果是让先让右子节点入队，后让左子节点入队，最后列表中的最后一个节点是最左子节点
List<Integer> levelOrder(TreeNode root) {
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    // 初始化一个列表，用于保存遍历序列
    List<Integer> list = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // 队列出队
        list.add(node.val);           // 保存节点值
        if (node.left != null)
            queue.offer(node.left);   // 左子节点入队
        if (node.right != null)
            queue.offer(node.right);  // 右子节点入队
    }
    return list;
}

前/中/后序遍历

深度优先（必背）

二叉搜索树的前序、中序、后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* 前序遍历 */
void preOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：根节点 -> 左子树 -> 右子树
    list.add(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

/* 中序遍历 */
void inOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(root.left);
    list.add(root.val);
    inOrder(root.right);
}

/* 后序遍历 */
void postOrder(TreeNode root) {
    if (root == null)
        return;
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(root.left);
    postOrder(root.right);
    list.add(root.val);
}

226翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

img

1
2
3
// 采用层序遍历的方法
输入：root = [4,2,7,1,3,6,9] 
输出：[4,7,2,9,6,3,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode invertTree(TreeNode root) {
        //翻转这棵二叉树，并返回其根节点。
        invert(root);
        return root;
    }

    public void invert(TreeNode root){
        if(root == null){
            return;
        }

        //交换左右子树,交换根节点,交换左节点,交换右节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        invert(root.left);
        invert(root.right);
    }
}

101对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

img

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }

    public boolean check(TreeNode L, TreeNode R) {
        // 判断极端条件
        if (L == null && R == null) {
            return true;
        }
        if (L == null || R == null) {
            return false;
        }
        return L.val == R.val && check(L.left, R.right) && check(L.right, R.left);
    }
}

104二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

img

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

111二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

为什么最大深度和最小深度的解法有较大不同？

最大深度可以简单的原因：

  1. 只要树不为空，深度至少为1
  2. 可以直接递归比较左右子树
  3. 空子树返回0，不影响最大值计算

最小深度需要复杂处理的原因：

  1. 需要跳过非叶子节点
    • 如果一个节点只有一个子节点，这个节点不是叶子节点
    • 必须沿着有子节点的方向继续查找
  2. 不能简单取最小值
    • 如果直接取左右子树的最小值
    • 当一边为空时，会错误地返回1（实际上不是叶子节点）
  3. 初始化最大值的原因
    • 需要确保能正确找到最小值
    • 避免空子树影响结果

110. 平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

img

1
2
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

注意

这道题目是在 二叉树的最大深度 的基础上增加了对于左右子树深度差距的判断。

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

示例 1：

img

1
2
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

1
2
输入：root = [1]
输出：["1"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 代码框架参考下文的回溯算法
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<TreeNode> state = new ArrayList<>();
        state.add(root);
        List<TreeNode> choices = Arrays.asList(root.left, root.right);
        backtrack(state, choices, res);
        return res;

    }

    /* 判断当前状态是否为解 */
    boolean isSolution(List<TreeNode> state) {
        return !state.isEmpty() && state.get(state.size() - 1).left == null && state.get(state.size() - 1).right == null;
    }

    /* 记录解 */
    void recordSolution(List<TreeNode> state, List<String> res) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < state.size(); i++) {
            if (i > 0){
                sb.append("->");
            }
            sb.append(state.get(i).val);
        }
        res.add(sb.toString());
    }

    /* 判断在当前状态下，该选择是否合法 */
    boolean isValid(List<TreeNode> state, TreeNode choice) {
        return choice != null;
    }

    /* 更新状态 */
    void makeChoice(List<TreeNode> state, TreeNode choice) {
        state.add(choice);
    }

    /* 恢复状态 */
    void undoChoice(List<TreeNode> state, TreeNode choice) {
        state.remove(state.size() - 1);
    }

    void backtrack(List<TreeNode> state, List<TreeNode> choices, List<String> res) {
        // 检查是否为解
        if (isSolution(state)) {
            // 记录解
            recordSolution(state, res);
        }
        // 遍历所有选择
        for (TreeNode choice : choices) {
            // 剪枝：检查选择是否合法
            if (isValid(state, choice)) {
                // 尝试：做出选择，更新状态
                makeChoice(state, choice);
                // 进行下一轮选择
                backtrack(state, Arrays.asList(choice.left, choice.right), res);
                // 回退：撤销选择，恢复到之前的状态
                undoChoice(state, choice);
            }
        }
    }
}

404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

img

1
2
3
输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

1
2
输入: root = [1]
输出: 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 代码在层序遍历的基础上修改
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        int res = 0;
        // 初始化队列，加入根节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 初始化一个列表，用于保存遍历序列
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll(); // 队列出队
            list.add(node.val);           // 保存节点值
            if (node.left != null) {      // 左子节点入队
                queue.offer(node.left);
                // 判断左子节点为左叶子节点
                if (node.left.left == null && node.left.right == null){
                    res += node.left.val;
                }
            }
            if (node.right != null)
                queue.offer(node.right);  // 右子节点入队
        }
        return res;
    }
}

构建树问题《Hello 算法》

给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder ，请从中构建二叉树，返回二叉树的根节点。假设二叉树中没有值重复的节点

该图截自《Hello 算法》

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 构建二叉树：分治 */
TreeNode dfs(int[] preorder, Map<Integer, Integer> inorderMap, int i, int l, int r) {
    // 子树区间为空时终止
    if (r - l < 0)
        return null;
    // 初始化根节点
    TreeNode root = new TreeNode(preorder[i]);
    // 查询 m ，从而划分左右子树
    int m = inorderMap.get(preorder[i]);
    // 子问题：构建左子树
    root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
    // 子问题：构建右子树
    root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
    // 返回根节点
    return root;
}

/* 构建二叉树 */
TreeNode buildTree(int[] preorder, int[] inorder) {
    // 初始化哈希表，存储 inorder 元素到索引的映射
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    TreeNode root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
    return root;
}

解析

见链接

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

img

1
2
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

1
2
输入：inorder = [-1], postorder = [-1]
输出：[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 仿照上述的构建树问题修改代码
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return dfs(postorder, inorderMap, inorder.length - 1, 0, inorder.length - 1);
    }

    TreeNode dfs(int[] postorder, Map<Integer, Integer> inorderMap, int i, int l, int r) {
        // 子树区间为空时终止
        if (r - l < 0)  
            return null;
        // 查询 m ，从而划分左右子树
        int m = inorderMap.get(postorder[i]);
        // 初始化根节点
        TreeNode root = new TreeNode(postorder[i]);
        // 子问题：构建右子树
        root.right = dfs(postorder, inorderMap, i - 1, m + 1, r);
        // 子问题：构建左子树
        root.left = dfs(postorder, inorderMap, i - (r - m) - 1, l, m - 1);
        // 返回根节点
        return root;
    }
}
// 两个问题：
// 后序遍历应该是 左右根，这里构建顺序为 根右左，颠倒过来的原因
// 构建左子树时 (r - m) 指的是 右子树 的节点数量

654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 *最大二叉树* 。

示例 1：

img

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

img

1
2
输入：nums = [3,2,1]
输出：[3,null,2,null,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 满足分治条件
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length - 1);
    }

    public TreeNode construct(int[] nums, int left, int right){
        if (left > right){
            return null;
        }
        int maxNumLoc = left;
        for(int i = left + 1; i <= right; i++){
            if(nums[i] > nums[maxNumLoc]){
                maxNumLoc = i;
            }
        }
        TreeNode node = new TreeNode(nums[maxNumLoc]);
        node.left = construct(nums, left, maxNumLoc - 1);
        node.right = construct(nums, maxNumLoc + 1, right);
        return node;
    }
}

617. 合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

img

1
2
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

1
2
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
1
2
3
4
5
6
7
8
9
10
11
// 不需要遍历二叉树，直接相加即可
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        TreeNode merged = new TreeNode(root1.val + root2.val);
        merged.left = mergeTrees(root1.left, root2.left);
        merged.right = mergeTrees(root1.right, root2.right);
        return merged;
    }
}

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

img

1
2
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

img

1
2
输入：root = [4,2,7,1,3], val = 5
输出：[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 注意二叉搜索树的性质
// 方式一:递归
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val == root.val) {
            return root;
        }
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}

// 方式二:迭代
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode cur = root;
        // 循环查找，越过叶节点后跳出
        while (cur != null) {
            // 目标节点在 cur 的右子树中
            if (cur.val < val)
                cur = cur.right;
            // 目标节点在 cur 的左子树中
            else if (cur.val > val)
                cur = cur.left;
            // 找到目标节点，跳出循环
            else
                break;
        }
        // 返回目标节点
        return cur;
    }
}

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 严格小于 当前节点的数。
  • 节点的右子树只包含 严格大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

img

1
2
输入：root = [2,1,3]
输出：true

示例 2：

img

1
2
3
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 注意，对于二叉搜索树，中序遍历值就是从小到大的
// 如果迭代判断单个节点的左子节点是否比它小，右子节点是否比它大。那么无法比较其子节点和其父节点的大小，如示例二所示
// 这里引入了一个成员变量list，也可以将list作为isValidBST方法的局部变量，那么需要给inOrder方法增加list传参
class Solution {
    private List<Integer> list = new ArrayList<>();  // 改为成员变量

    public boolean isValidBST(TreeNode root) {
        boolean flag = true;
        // 部分递归
        inOrder(root);
        if (list == null) return flag;
        int temp = list.get(0);
        for (int i = 1; i < list.size(); i++){
            if (list.get(i) <= temp){
                flag = false;
                return flag;
            }
            temp = list.get(i);
        }
        return flag;
    }

    /* 中序遍历 */
    void inOrder(TreeNode root) {
        if (root == null)
            return;
        // 访问优先级：左子树 -> 根节点 -> 右子树
        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }

}

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例 1：

img

1
2
输入：root = [1,null,2,2]
输出：[2]

示例 2：

1
2
输入：root = [0]
输出：[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 注意其中列表到数组的转换
class Solution {
    private List<Integer> list = new ArrayList<>();  // 改为成员变量

    public int[] findMode(TreeNode root) {
        // 获取list，并用HashMap统计次数
        inOrder(root);
        HashMap<Integer, Integer> dic = new HashMap<>();
        for (int i = 0; i < list.size(); i++){
            dic.put(list.get(i) , dic.getOrDefault(list.get(i), 0) + 1);
        }
        // 找出最大出现次数
        int maxCount = 0;
        for (int count : dic.values()) {
            maxCount = Math.max(maxCount, count);
        }
        
        // 收集出现次数等于最大次数的数字
        List<Integer> resultList = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : dic.entrySet()) {
            if (entry.getValue() == maxCount) {
                resultList.add(entry.getKey());
            }
        }

        // 转换为int数组返回
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }

    /* 中序遍历 */
    void inOrder(TreeNode root) {
        if (root == null)
            return;
        // 访问优先级：左子树 -> 根节点 -> 右子树
        inOrder(root.left);
        list.add(root.val);
        inOrder(root.right);
    }
}

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

img

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

1
2
输入：root = [1,2], p = 1, q = 2
输出：1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 注意要包括本节点
class Solution {
    private HashMap<TreeNode, TreeNode> dic = new HashMap<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 利用哈希表存储每个节点的父节点,采用前序遍历
        preOrder(root);
        // 获取p节点的所有父级节点
        List<TreeNode> list = new ArrayList<>();
        getFatherNode(p, list);
        // 获取q节点的在list中出现的第一个父节点
        TreeNode result = getFirstAppearNode(q, list);
        return result;
    }

    // 前序遍历，不需要记录该节点，所以只包括“左”，“右”两部分
    void preOrder(TreeNode root){
        if (root.left != null){
            dic.put(root.left, root);
            preOrder(root.left);
        }
        if (root.right != null){
            dic.put(root.right, root);
            preOrder(root.right);
        }
    }

    void getFatherNode(TreeNode p, List<TreeNode> list){
        list.add(p);  // 添加当前节点
        if (dic.containsKey(p)){
            getFatherNode(dic.get(p), list);
        }
    }

    public TreeNode getFirstAppearNode(TreeNode q, List<TreeNode> list){
        // 题目的意思是一定存在公共祖先
        if (list.contains(q)) {
            return q;
        }
        return getFirstAppearNode(dic.get(q), list);
    }
}

解析

存储父节点

我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。

701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 注意，如果不将 root 作为参数返回，那么如果 root 参数为 null，在 insert 方法中修改后，因为修改的是局部变量，将 null 修改为 TreeNode 不影响外部的 root。
// 这里使用的是《Hello 算法》中的 insert 方法。
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 从根节点开始寻找插入位置，记录前一个节点
        return insert(val, root);
    }

    /* 插入节点 */
    public TreeNode insert(int val, TreeNode root) {
        // 若树为空，则初始化根节点
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }
        TreeNode cur = root, pre = null;
        // 循环查找，越过叶节点后跳出
        while (cur != null) {
            // 找到重复节点，直接返回
            if (cur.val == val)
                return root;
            pre = cur;
            // 插入位置在 cur 的右子树中
            if (cur.val < val)
                cur = cur.right;
            // 插入位置在 cur 的左子树中
            else
                cur = cur.left;
        }
        // 插入节点
        TreeNode node = new TreeNode(val);
        if (pre.val < val)
            pre.right = node;
        else
            pre.left = node;
        return root;
    }
}

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 注意，如果不将 root 作为参数返回，那么会出现和上述同样的问题，只不过在这里删除的过程中，会把只有一个元素的树节点变为 null，同样改变了引用。
// 这里使用的是《Hello 算法》中的 remove 方法。
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        return remove(root, key);
    }

    /* 删除节点 */
    public TreeNode remove(TreeNode root, int num) {
        // 若树为空，直接提前返回
        if (root == null)
            return root;
        TreeNode cur = root, pre = null;
        // 循环查找，越过叶节点后跳出
        while (cur != null) {
            // 找到待删除节点，跳出循环
            if (cur.val == num)
                break;
            pre = cur;
            // 待删除节点在 cur 的右子树中
            if (cur.val < num)
                cur = cur.right;
            // 待删除节点在 cur 的左子树中
            else
                cur = cur.left;
        }
        // 若无待删除节点，则直接返回
        if (cur == null)
            return root;
        // 子节点数量 = 0 or 1
        if (cur.left == null || cur.right == null) {
            // 当子节点数量 = 0 / 1 时， child = null / 该子节点
            TreeNode child = cur.left != null ? cur.left : cur.right;
            // 删除节点 cur
            if (cur != root) {
                if (pre.left == cur)
                    pre.left = child;
                else
                    pre.right = child;
            } else {
                // 若删除节点为根节点，则重新指定根节点
                root = child;
            }
        }
        // 子节点数量 = 2
        else {
            // 获取中序遍历中 cur 的下一个节点
            TreeNode tmp = cur.right;
            while (tmp.left != null) {
                tmp = tmp.left;
            }
            // 递归删除节点 tmp
            remove(root, tmp.val);
            // 用 tmp 覆盖 cur
            cur.val = tmp.val;
        }
        return root;
    }
}

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：

img

1
2
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 采用递归的方法针对左右子树情况进行判断
public TreeNode trimBST(TreeNode root, int low, int high) {
    // 1. 基础情况：空节点直接返回
    if (root == null) {
        return null;
    }
    
    // 2. 当前节点值小于low：整个左子树都小于low，全部丢弃
    //    修剪右子树，返回的结果作为新的根
    if (root.val < low) {
        return trimBST(root.right, low, high);
    } 
    // 3. 当前节点值大于high：整个右子树都大于high，全部丢弃
    //    修剪左子树，返回的结果作为新的根
    else if (root.val > high) {
        return trimBST(root.left, low, high);
    } 
    // 4. 当前节点在范围内：保留当前节点，递归修剪左右子树
    else {
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

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

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

img

1
2
3
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

img

1
2
3
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 调用辅助函数，初始范围是整个数组（0 到 length-1）
        return helper(nums, 0, nums.length - 1);
    }

    public TreeNode helper(int[] nums, int left, int right) {
        // 递归终止条件：左指针超过右指针，表示当前区间没有元素
        if (left > right) {
            return null;
        }

        // 1. 选择中间位置（偏左）的元素作为当前子树的根节点
        // 例如：left=0, right=4 → mid=2
        //       left=0, right=3 → mid=1
        int mid = (left + right) / 2;

        // 2. 创建根节点
        TreeNode root = new TreeNode(nums[mid]);

        // 3. 递归构建左子树（左区间 [left, mid-1]）
        root.left = helper(nums, left, mid - 1);

        // 4. 递归构建右子树（右区间 [mid+1, right]）
        root.right = helper(nums, mid + 1, right);

        // 5. 返回当前子树的根
        return root;
    }
}

回溯

注意

  1. 回溯是递归的副产品，只要有递归就会有回溯。
  2. 回溯法就是暴力搜索，遍历出所有可选列表。
  3. 每一道回溯法的题目都可以抽象为树形结构。

待做事项&&疑问

  1. 回溯题目常参考灵茶山艾府(以下简称灵神)的代码，发现灵神常用五个参数，与代码框架中的不同，需要比对这其中的差距。

代码框架（必背）

注意，本文涉及到回溯的代码都会用该框架来写！！但不会创建像下面这么多的函数，因为只有一两行代码。

详见 《Hello 算法》：在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为 3 的节点。

Shut up and calculate! -David Mermin && Feynman

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 状态 state 为节点遍历路径，选择 choices 为当前节点的左子节点和右子节点，结果 res 是路径列表
/* 判断当前状态是否为解 */
boolean isSolution(List<TreeNode> state) {
    return !state.isEmpty() && state.get(state.size() - 1).val == 7;
}

/* 记录解 */
void recordSolution(List<TreeNode> state, List<List<TreeNode>> res) {
    res.add(new ArrayList<>(state));
}

/* 判断在当前状态下，该选择是否合法 */
boolean isValid(List<TreeNode> state, TreeNode choice) {
    return choice != null && choice.val != 3;
}

/* 更新状态 */
void makeChoice(List<TreeNode> state, TreeNode choice) {
    state.add(choice);
}

/* 恢复状态 */
void undoChoice(List<TreeNode> state, TreeNode choice) {
    state.remove(state.size() - 1);
}

/* 回溯算法：例题三 */
void backtrack(List<TreeNode> state, List<TreeNode> choices, List<List<TreeNode>> res) {
    // 检查是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
    }
    // 遍历所有选择
    for (TreeNode choice : choices) {
        // 剪枝：检查选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            // 进行下一轮选择
            backtrack(state, Arrays.asList(choice.left, choice.right), res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void backtrack(List<TreeNode> state, List<TreeNode> choices, List<List<TreeNode>> res) {
    // 检查是否为解
    if (!state.isEmpty() && state.get(state.size() - 1).val == 7) {
        // 记录解
        res.add(new ArrayList<>(state));
    }
    // 遍历所有选择
    for (TreeNode choice : choices) {
        // 剪枝：检查选择是否合法
        if (choice != null && choice.val != 3) {
            // 尝试：做出选择，更新状态
            state.add(choice);
            // 进行下一轮选择
            backtrack(state, Arrays.asList(choice.left, choice.right), res);
            // 回退：撤销选择，恢复到之前的状态
            state.remove(state.size() - 1);
        }
    }
}

共有七步：检查是否为解、记录解、遍历所有选择、剪枝(检查选择是否合法)、尝试(做出选择,更新状态)、进行下一轮选择、回退(撤销选择)

背诵口诀：简(检)记便(遍)笺(剪)常(尝)晋(进)会(回)：简单记录在便笺上，常晋集团要开会

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：

1
2
输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        getCombine(n, k, 1, new ArrayList<>());
        return ans;
    }
    
    public void getCombine(int n, int k, int start, List<Integer> list) {
        // 检查是否为解
        if(k == 0) {
            // 记录解
            ans.add(new ArrayList<>(list));
            return;
        }
        // 遍历所有选择
        for(int i = start;i <= n - k + 1;i++) {
            // 尝试：做出选择，更新状态
            list.add(i);
            // 进行下一轮选择
            getCombine(n, k - 1, i+1, list);
            // 回退：撤销选择，恢复到之前的状态
            list.remove(list.size() - 1);
        }
    }
}

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

1
2
3
4
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>(k);
        dfs(9, n, k, ans, path); // 从 i=9 开始倒着枚举
        return ans;
    }

    private void dfs(int i, int leftSum, int k, List<List<Integer>> ans, List<Integer> path) {
        int d = k - path.size(); // 还要选 d 个数
        if (leftSum == 0 && d == 0) { // 找到一个合法组合
            ans.add(new ArrayList<>(path));
            return;
        }
        // 枚举的数不能太小，否则后面没有数可以选
        for (int j = i; j >= d; j--) {
            if (leftSum < 0 || leftSum > (i * 2 - d + 1) * d / 2) { // 剪枝
                return;
            }
            path.add(j);
            dfs(j - 1, leftSum - j, k, ans, path);
            path.removeLast(); // path.remove(path.size() - 1);
        }
    }
}

// 将剪枝操作提前，在进行检查是否为解判断时可以少判断条件
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>(k);
        dfs(9, n, k, ans, path); // 从 i=9 开始倒着枚举
        return ans;
    }

    private void dfs(int i, int leftSum, int k, List<List<Integer>> ans, List<Integer> path) {
        int d = k - path.size(); // 还要选 d 个数

        if (leftSum < 0 || leftSum > (i * 2 - d + 1) * d / 2) { // 剪枝
            return;
        }
        if (d == 0) { // 找到一个合法组合
            ans.add(new ArrayList<>(path));
            return;
        }
        // 枚举的数不能太小，否则后面没有数可以选
        for (int j = i; j >= d; j--) {
            path.add(j);
            dfs(j - 1, leftSum - j, k, ans, path);
            path.removeLast(); // path.remove(path.size() - 1);
        }
    }
}

注意

这里的回溯代码，剪枝操作放在了检查是否为解之前；需要总结在什么情况下剪枝操作要提前？

剪枝操作中包含的参数影响检查是否为解的判断时要把剪枝操作提前

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
输入：digits = "2"
输出：["a","b","c"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        if (n == 0) {
            return List.of();
        }

        List<String> ans = new ArrayList<>();
        char[] path = new char[n]; // 注意 path 长度一开始就是 n，不是空数组
        dfs(0, ans, path, digits.toCharArray());
        return ans;
    }

    private void dfs(int i, List<String> ans, char[] path, char[] digits) {
        if (i == digits.length) {
            ans.add(new String(path));
            return;
        }
        String letters = MAPPING[digits[i] - '0'];
        for (char c : letters.toCharArray()) {
            path[i] = c; // 直接覆盖
            dfs(i + 1, ans, path, digits);
        }
    }
}

注意

此处回溯代码代码没有在进行下一轮选择后使用回退，因为采用的是固定数组，每次重新选择都会覆盖之前的值

即 path[i] = c 的直接覆盖取代了回退！状态的更新是必须的！！

使用 ArrayList（需要回退）
1
2
3
4
5
6
7
8
9
10
11
递归树：
            []
      /     |     \
    [a]    [b]    [c]      // path 长度 = 1
   /  \    /  \    /  \
 [ad][ae][bd][be][cd][ce]   // path 长度 = 2

// 如果不回退：
从 [a] 到 [ad]：path = [a,d]
回溯到 [a] 时，如果不删除 'd'：path = [a,d] 长度2
尝试 'e'：path.add('e') → [a,d,e] 长度3 ❌ 错误！
使用固定数组（不需要回退）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
char[] path = new char[2];  // 固定长度2

递归树：
dfs(0): path[0] = 'a'  → path = ['a', _ ]
  dfs(1): path[1] = 'd' → path = ['a','d']
  得到 "ad"
  
回溯到 dfs(0)：
  不需要删除！因为 path[1] 的值 'd' 会被下一轮覆盖
  
dfs(0): path[0] = 'b'  → path = ['b','d']  // 覆盖了 path[0]
  dfs(1): path[1] = 'd' → path = ['b','d']
  得到 "bd"
  
// path[1] 的 'd' 不会被自动清除，但会被覆盖

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, target, candidates, ans, path);
        return ans;
    }

    private void dfs(int i, int left, int[] candidates, List<List<Integer>> ans, List<Integer> path) {
        if (left == 0) {
            // 找到一个合法组合
            ans.add(new ArrayList<>(path));
            return;
        }

        // 枚举选哪个
        for (int j = i; j < candidates.length; j++) {
            if (candidates[j] <= left){
                path.add(candidates[j]);
                dfs(j, left - candidates[j], candidates, ans, path);
                path.remove(path.size() - 1); // 恢复现场
            }
        }
    }
}

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

**注意：**解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, target, candidates, ans, path);
        return ans;
    }

    private void dfs(int i, int left, int[] candidates, List<List<Integer>> ans, List<Integer> path) {
        if (left == 0) {
            // 找到一个合法组合
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int j = i; j < candidates.length && candidates[j] <= left; j++) {
            if (j > i && candidates[j] == candidates[j - 1]) {
                continue;
            }
            path.add(candidates[j]);
            dfs(j + 1, left - candidates[j], candidates, ans, path);
            path.remove(path.size() - 1); // 恢复现场
        }
    }
}

注意

与 组合总和 相比，这里的剪枝更为复杂，所以对遍历之中和尝试之前的逻辑进行了修改，本质上还是剪枝

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
输入：s = "a"
输出：[["a"]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(0, s, path, ans);
        return ans;
    }


    // 标准回溯模块代码
    private void dfs(int i, String s, List<String> path, List<List<String>> ans) {
        if (i == s.length()) { // s 分割完毕
            ans.add(new ArrayList<>(path)); // 复制 path
            return;
        }
        for (int j = i; j < s.length(); j++) { // 枚举子串的结束位置
            if (isPalindrome(s, i, j)) { // 判断 [i, j] 是不是回文串
                path.add(s.substring(i, j + 1)); // 分割！
                // 现在 s 未被分割的部分为 [j+1, n-1]
                dfs(j + 1, s, path, ans);
                path.removeLast(); // path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

1
2
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public List<String> restoreIpAddresses(String s) {
        int n = s.length();
        List<String> ans = new ArrayList<>();
        String[] path = new String[4];
        dfs(0, 0, s, s.length(), path, ans);
        return ans;
    }

    // 分割 s[i] 到 s[n-1]，现在在第 j 段（j 从 0 开始）
    private void dfs(int i, int j, String s, int n, String[] path, List<String> ans) {
        // 剪枝：还剩下 n-i 个字符，需要分成 4-j 段，每段至少 1 个字符，至多 3 个字符，所以 4-j <= n-i <= (4-j)*3
        if (n - i < 4 - j || n - i > (4 - j) * 3) {
            return;
        }

        if (i == n) { // s 分割完毕
            ans.add(String.join(".", path));
            return;
        }

        // 子串左端点为 i
        // 枚举子串右端点 right
        int ipVal = 0;
        for (int right = i; right < n; right++) {
            ipVal = ipVal * 10 + (s.charAt(right) - '0');
            if (ipVal > 255 || ) { // 不合法
                break;
            }
            path[j] = s.substring(i, right + 1); // 直接覆盖 path[j]，无需恢复现场
            dfs(right + 1, j + 1, s, n, path, ans);
            if (ipVal == 0) { // 前导零，对于后续循环不合法
                break;
            }
        }
    }
}

注意

该题目涉及到的剪枝操作过多，在实际中如果没记住可不考虑做出

步骤图解

递归过程较长，只显示前面的内容

例子： s = "255255"

目标：分割成 4 个 0–255 之间的数字，且不能有前导零（除非本身就是 “0”）。

初始调用

1
dfs(i=0, j=0, s="255255", n=6)

此时 n - i = 6，4 - j = 4，(4 - j) * 3 = 12，满足：
4 <= 6 <= 12 ✅

第一层 (j=0, 枚举第 1 段)

s = “255255”, i = 0 开始枚举 right

right = 0

子串 "2"
ipVal = 0*10 + 2 = 2
2 <= 255 ✅
path[0] = "2"
进入 dfs(1, 1)

进入 dfs(1, 1)

1
2
3
n - i = 5（剩下 "55255"）
4 - j = 3
条件：3 <= 5 <= 9 ✅

枚举子串 right 从 1 开始（因为 i=1）

right=1："5"
ipVal = 5 ✅
path[1] = "5"
进入 dfs(2, 2)

进入 dfs(2, 2)

1
2
3
n - i = 4（剩下 "5255"）
4 - j = 2
条件：2 <= 4 <= 6 ✅

枚举子串 right 从 2 开始

right=2："5"
ipVal = 5 ✅
path[2] = "5"
进入 dfs(3, 3)

进入 dfs(3, 3)

1
2
3
n - i = 3（剩下 "255"）
4 - j = 1
条件：1 <= 3 <= 3 ✅

枚举子串 right 从 3 开始

right=3："2"
ipVal = 2 ✅
path[3] = "2"
进入 dfs(4, 4)

进入 dfs(4, 4)

1
2
3
4
i = 4，n = 6
n - i = 2
4 - j = 0
条件：0 <= 2 <= 0 ❌ （2 > 0）

直接 return

所以 right=3 这条路失败。

回溯到 dfs(3, 3) 继续循环

right=4：子串 "25"（i=3 到 4）
ipVal = 2*10 + 5 = 25 ✅
path[3] = "25"（覆盖掉之前的 "2"）

进入 dfs(5, 4)

进入 dfs(5, 4)

1
2
3
n - i = 1
4 - j = 0
条件：0 <= 1 <= 0 ❌

失败。

right=5：子串 "255"
ipVal = 2*10 + 5 = 25 → 25*10 + 5 = 255 ✅
path[3] = "255"

进入 dfs(6, 4)

进入 dfs(6, 4)

1
2
i == n（6 == 6）
ans.add(String.join(".", path))
1
2
path` 当前内容：
`["2", "5", "5", "255"]

组成 IP：2.5.5.255 ✅

回到 dfs(2,2) 继续

此时 dfs(2,2) 里的循环 right 继续：

之前 right=2 已经试过（"5"），
现在 right=3：子串 "52"（i=2 到 3）
ipVal = 5*10 + 2 = 52 ✅
path[2] = "52"

进入 dfs(4, 3)

dfs(4, 3)

1
2
3
n - i = 2（剩下 "55"）
4 - j = 1
条件：1 <= 2 <= 3 ✅

枚举子串 right 从 4 开始

right=4："5"
ipVal = 5 ✅
path[3] = "5"
进入 dfs(5, 4) → 失败

right=5："55"
ipVal = 5*10 + 5 = 55 ✅
path[3] = "55"
进入 dfs(6, 4) → 成功

添加 IP：["2", "5", "52", "55"] → 2.5.52.55 ✅

继续回溯到 dfs(2,2)，right=4
子串 "525"（i=2 到 4）
ipVal = 5*10 + 2 = 52 → 52*10 + 5 = 525
525 > 255 ❌ break

后续过程省略…

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 改代码只需要在 77.组合 的基础上稍加修改即可
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        getCombine(0, n, nums, new ArrayList<>());
        return ans;
    }

    public void getCombine(int start, int n, int[] nums, List<Integer> list) {
        // 记录解
        ans.add(new ArrayList<>(list));
        // 遍历所有选择
        for (int i = start; i < n; i++) {
            // 尝试：做出选择，更新状态
            list.add(nums[i]);
            // 进行下一轮选择
            getCombine(i + 1, n, nums, list);
            // 回退：撤销选择，恢复到之前的状态
            list.remove(list.size() - 1);
        }
    }
}

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

1
2
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        getCombine(0, n, nums, new ArrayList<>());
        return ans;
    }

    public void getCombine(int start, int n, int[] nums, List<Integer> list) {
        // 记录解
        ans.add(new ArrayList<>(list));
        // 遍历所有选择
        for (int i = start; i < n; i++) {
            // 剪枝,消除掉重复元素
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            // 尝试：做出选择，更新状态
            list.add(nums[i]);
            // 进行下一轮选择
            getCombine(i + 1, n, nums, list);
            // 回退：撤销选择，恢复到之前的状态
            list.remove(list.size() - 1);
        }
    }

}

注意

这里的剪枝条件 i > start确保了只有当具有相同值的数不处于同一层，才能纳入选择：如示例1，在start为0时，比较后两个2的值，只取其中一个2，而当start为1时，已经取得了[1,2]，这时可以将最后一个2纳入其中。

491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

1
2
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

1
2
输入：nums = [4,4,3,2,1]
输出：[[4,4]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(0, nums, new ArrayList<>());
        return ans;
    }
    
    private void dfs(int start, int[] nums, List<Integer> path) {
        if (path.size() >= 2) {
            ans.add(new ArrayList<>(path));
        }
        
        Set<Integer> used = new HashSet<>(); // 本层去重
        for (int i = start; i < nums.length; i++) {
            // 非递减条件
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
                continue;
            }
            // 同一层重复元素剪枝
            if (used.contains(nums[i])) {
                continue;
            }
            used.add(nums[i]);
            path.add(nums[i]);
            dfs(i + 1, nums, path);
            path.remove(path.size() - 1);
        }
    }
}

注意

涉及到的剪枝条件过多，需要分成两部分

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1]
输出：[[1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<Integer> path = Arrays.asList(new Integer[n]); // 所有排列的长度都是一样的 n
        boolean[] onPath = new boolean[n];
        List<List<Integer>> ans = new ArrayList<>();

        dfs(0, nums, ans, path, onPath);
        return ans;
    }

    // 枚举 path[i] 填 nums 的哪个数
    private void dfs(int i, int[] nums, List<List<Integer>> ans, List<Integer> path, boolean[] onPath) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int j = 0; j < nums.length; j++) {
            if (!onPath[j]) {
                path.set(i, nums[j]); // 从没有选的数字中选一个
                onPath[j] = true; // 已选上
                dfs(i + 1, nums, ans, path, onPath);
                onPath[j] = false; // 恢复现场
                // 注意 path 无需恢复现场，因为排列长度固定，直接覆盖就行
            }
        }
    }
}

步骤图解

1. 初始状态

  • nums = [1, 2, 3]
  • n = 3
  • path = [_, _, _] （长度为 3，初始占位）
  • onPath = [false, false, false]
  • ans = []

调用 dfs(0, ...)。

2. 递归树展开

2.1 第一层：i = 0

循环 j = 0,1,2，尝试填充 path[0]。

j = 0

  • path[0] = 1, onPath[0] = true
  • 调用 dfs(1, ...)

2.2 第二层：i = 1

当前 path: [1, _, _]
onPath: [T, F, F]

循环 j = 0,1,2：跳过 j=0（已用）。

j = 1

  • path[1] = 2, onPath[1] = true
  • 调用 dfs(2, ...)

2.3 第三层：i = 2

当前 path: [1, 2, _]
onPath: [T, T, F]

循环 j = 0,1,2：跳过 j=0,1。

j = 2

  • path[2] = 3, onPath[2] = true
  • 调用 dfs(3, ...)

3.1 第四层：i = 3（叶子）

  • i == n（3），ans.add([1,2,3])
  • 返回上一层

3.2 回到第三层：i = 2，j = 2 执行完成

  • 恢复现场：onPath[2] = false
  • 循环结束，返回上一层

2.4 回到第二层：i = 1，j = 1 执行完成

恢复现场：onPath[1] = false
继续循环 j=2。

j = 2（在 i=1 层）

  • path[1] = 3, onPath[2] = true
  • 调用 dfs(2, ...)

第三层：i = 2

当前 path: [1, 3, _]
onPath: [T, F, T]

循环 j = 0,1,2：跳过 j=0,2。

j = 1

  • path[2] = 2, onPath[1] = true
  • 调用 dfs(3, ...)

叶子

i=3 → ans 添加 [1, 3, 2]

返回上一级，恢复 onPath[1] = false。

i=2 层循环结束，返回上一层。

回到第二层 i=1，j=2 结束

恢复 onPath[2] = false。

第二层循环结束，返回第一层。

2.5 回到第一层 i=0，j=0 结束

恢复 onPath[0] = false。

2.6 第一层，i=0，j=1

1
path[0] = 2`, `onPath[1] = true
  • 继续递归，过程类似，生成以 2 开头的排列 [2, 1, 3] 和 [2, 3, 1]

2.7 第一层，i=0，j=2

1
path[0] = 3`, `onPath[2] = true
  • 生成以 3 开头的排列 [3, 1, 2] 和 [3, 2, 1]

3. 最终 ans 收集的排列顺序

(按递归深度优先遍历生成顺序)：

  1. [1, 2, 3]
  2. [1, 3, 2]
  3. [2, 1, 3]
  4. [2, 3, 1]
  5. [3, 1, 2]
  6. [3, 2, 1]

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);

        int n = nums.length;
        List<Integer> path = Arrays.asList(new Integer[n]); // 所有排列的长度都是 n
        boolean[] onPath = new boolean[n]; // onPath[j] 表示 nums[j] 是否已经填入排列
        List<List<Integer>> ans = new ArrayList<>();

        dfs(0, nums, path, onPath, ans);
        return ans;
    }

    // i 表示当前要填排列的第几个数
    private void dfs(int i, int[] nums, List<Integer> path, boolean[] onPath, List<List<Integer>> ans) {
        if (i == nums.length) { // 填完了
            ans.add(new ArrayList<>(path));
            return;
        }

        // 枚举 nums[j] 填入 path[i]
        for (int j = 0; j < nums.length; j++) {
            // 如果 nums[j] 已填入排列，continue
            // 如果 nums[j] 和前一个数 nums[j-1] 相等，且 nums[j-1] 没填入排列，continue
            if (onPath[j] // 情况1：当前数字已经在排列中
                ||
                (j > 0 && nums[j] == nums[j - 1] && !onPath[j - 1]) // 情况2：重复数字且前一个未被使用
               ) {
                continue;
            }
            path.set(i, nums[j]); // 填入排列
            onPath[j] = true; // nums[j] 已填入排列（注意标记的是下标，不是值）
            dfs(i + 1, nums, path, onPath, ans); // 填排列的下一个数
            onPath[j] = false; // 恢复现场
            // 注意 path 无需恢复现场，因为排列长度固定，直接覆盖 path[i] 就行
        }
    }
}

注意

  1. 去重问题需要排列。
  2. 该题的复杂度已超过了临场理解的范畴，需要结合 90. 子集 II 和 46. 全排列 来理解；实战中不要求做出。

难题暂缓

37. 解数独

51. N 皇后

动态规划

注意

动态规划(Dynamic Programming，DP)是由前一个状态推导出来的，而贪心是局部直接选最优的

目前动态规划类问题只考虑0-1背包问题和完全背包问题

解题步骤(必背)

  1. 思考每轮的决策，定义状态，从而得到 dp 表
  2. 找出最优子结构，进而推导出状态转移方程
  3. 确定边界条件和状态转移顺序

该步骤参考 《Hello 算法》

dp数组不一定是一维数组，也可能是二维表

本文将列举出所有递推结果，而不考虑缩小空间复杂度

509. 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

1
2
3
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

1
2
3
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

1
2
3
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int fib(int n) {
        int[] f = new int[n + 2];
        f[1] = 1;
        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

1
2
3
4
5
6
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 选自<<Hello 算法>>
class Solution {
    public int climbStairs(int n) {
        if (n == 1 || n == 2)
        return n;
        // 初始化 dp 表，用于存储子问题的解
        int[] dp = new int[n + 1];
        // 初始状态：预设最小子问题的解
        dp[1] = 1;
        dp[2] = 2;
        // 状态转移：从较小子问题逐步求解较大子问题
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

1
2
3
4
5
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

1
2
3
4
5
6
7
8
9
10
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] f = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            f[i] = Math.min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
        }
        return f[n];
    }
}

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

img

1
2
输入：m = 3, n = 7
输出：28

示例 2：

1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

1
2
输入：m = 7, n = 3
输出：28

示例 4：

1
2
输入：m = 3, n = 3
输出：6
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int uniquePaths(int m, int n) {
        // 创建一个 int 类型的二维数组时，所有元素都会被初始化为 0。
        int[][] f = new int[m + 1][n + 1];
        f[0][1] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                f[i + 1][j + 1] = f[i][j + 1] + f[i + 1][j];
            }
        }
        return f[m][n];
    }
}

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

img

1
2
输入：n = 3
输出：5

示例 2：

1
2
输入：n = 1
输出：1
1
2
3
4
5
6
7
8
9
10
11
public int numTrees(int n) {
    int[] dp = new int[n+1];  // dp[i] 表示 i 个节点能组成的 BST 数量
    dp[0] = 1;  // 空树也算一种情况
    dp[1] = 1;  // 1个节点只有1种树
    
    for(int i = 2; i < n + 1; i++)      // i: 节点总数，从2开始计算
        for(int j = 1; j < i + 1; j++)  // j: 选哪个节点作为根节点
            dp[i] += dp[j-1] * dp[i-j]; // 左子树有 j-1 个节点，右子树有 i-j 个节点
    
    return dp[n];
}

0-1 背包问题(参考Hello 算法)

0-1背包问题是从上方或者左上方转移状态

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 相比于0-1背包问题不涉及到比较大小的问题，状态转移方程用i+1表示整体更加简洁
class Solution {
    public boolean canPartition(int[] nums) {
        // 1. 计算总和
        int s = 0;
        for (int x : nums) {
            s += x;
        }
        // 2. 奇数直接返回 false
        if (s % 2 != 0) {
            return false;
        }
        s /= 2;  // 此时 s 变成了目标值 target

        int n = nums.length;
        // 3. 定义 dp 数组
        // f[i][j] 表示：考虑前 i 个数字（下标 0..i-1），能否选出和恰好为 j 的子集
        boolean[][] f = new boolean[n + 1][s + 1];
        
        // 4. 边界条件：不选任何数字，和可以凑成 0
        f[0][0] = true;
        
        // 5. 状态转移
        for (int i = 0; i < n; i++) {          // i 是当前处理的原数组下标
            int x = nums[i];                   // 当前数字
            for (int j = 0; j <= s; j++) {    // j 是目标和
                // 关键转移方程：
                // f[i+1][j] 表示考虑前 i+1 个数（即包含 nums[i]）
                // = (如果 j >= x 且 不选 nums[i] 时能凑出 j-x)  或者  (不选 nums[i] 时就能凑出 j)
                // 如果能凑出s，那么必然能够凑出另一个s！
                f[i + 1][j] = (j >= x && f[i][j - x]) || f[i][j];
            }
        }
        // 6. 返回结果：考虑所有 n 个数字，能否凑出目标和 s
        return f[n][s];
    }
}

1049. 最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

1
2
3
4
5
6
7
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：

1
2
输入：stones = [31,26,33,21,40]
输出：5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int s = 0;
        for (int x : stones) {
            s += x;
        }
        int target = s / 2;      // 与上题 s 含义一致
        int n = stones.length;
        boolean[][] f = new boolean[n + 1][target + 1];
        f[0][0] = true;

        for (int i = 0; i < n; i++) {
            int x = stones[i];
            for (int j = 0; j <= target; j++) {
                f[i + 1][j] = (j >= x && f[i][j - x]) || f[i][j];
            }
        }

        // 找到能凑出的、不超过 target 的最大重量 j
        for (int j = target; j >= 0; j--) {
            if (f[n][j]) {
                return s - 2 * j;
            }
        }
        return 0; // 实际不会执行到这里
    }
}

494. 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

1
2
输入：nums = [1], target = 1
输出：1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 类似于分割等和子集，只是将布尔值改为具体的数值
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int s = 0;
        for (int x : nums) {
            s += x;  // 计算所有数的和
        }

        // 注意：这里用的公式是 p = (s - target)/2 的变体
        // 等价于判断 (s + target) 是否为偶数且非负
        s -= Math.abs(target);  // 实际是 s - |target|
        if (s < 0 || s % 2 == 1) {  // 容量为负数或奇数，无解
            return 0;
        }

        int m = s / 2;  // 背包容量：需要凑成的和
        int n = nums.length;
        int[][] f = new int[n + 1][m + 1];
        f[0][0] = 1;  // 前0个数，凑成0有1种方式

        // 动态规划填表
        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= m; c++) {
                if (c < nums[i]) {
                    // 容量不够，只能不选当前数
                    f[i + 1][c] = f[i][c];
                } else {
                    // 不选 + 选当前数，方案数相加
                    f[i + 1][c] = f[i][c] + f[i][c - nums[i]];
                }
            }
        }

        return f[n][m];  // 前n个数凑成容量m的方案
    }
}

完全背包问题(参考 Hello 算法)

完全背包问题和 0-1 背包问题非常相似，区别仅在于不限制物品的选择次数。

完全背包问题是从上方或者左方转移状态（不从左上方是因为可以选择多次）

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据 保证 最终 结果符合 32 位 带符号整数。

示例 1：

1
2
3
4
5
6
7
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

1
2
3
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

1
2
输入：amount = 10, coins = [10] 
输出：1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] f = new int[n + 1][amount + 1];
        f[0][0] = 1;
        // 物品在外层
        for (int i = 0; i < n; i++) {
            // 金额在里层
            for (int c = 0; c <= amount; c++) {
                if (c < coins[i]) {
                    // 不选硬币
                    f[i + 1][c] = f[i][c];
                } else {
                    // 选硬币
                    f[i + 1][c] = f[i][c] + f[i + 1][c - coins[i]];
                }
            }
        }
        return f[n][amount];
    }
}

377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

1
2
输入：nums = [9], target = 3
输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] f = new int[target + 1];
        f[0] = 1;
        // 外层循环容量，内层循环物品 —— 这样才能计算排列数
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    f[i] += f[i - num];
                }
            }
        }
        return f[target];
    }
}

注意

顺序不同结果不同
1
2
3
4
5
6
7
8
9
10
11
// 物品在外层：物品 [1,2] 容量 3
// 只会遍历到 [1,2] 不会遍历到 [2,1]
物品1: dp[1]=1, dp[2]=1, dp[3]=1
物品2: dp[2]=1+dp[0]=2, dp[3]=1+dp[1]=2
// 最终 dp[3]=2 ([1,1,1], [1,2])

// 容量在外层：物品 [1,2] 容量 3
容量1: dp[1]=dp[0]=1
容量2: dp[2]=dp[1]+dp[0]=1+1=2 ([1,1], [2])
容量3: dp[3]=dp[2]+dp[1]=2+1=3 ([1,1,1], [1,2], [2,1])
// 最终 dp[3]=3，包含了 [1,2] 和 [2,1] 两种排列
步骤图解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
1. 初始化
dp[0] = 1。表示凑成总和为 0 的方法有 1 种：什么都不选。

2. 容量 1 （外层循环 i = 1）
我们需要计算 dp[1]，即凑出总和 1 的方法数。
内层循环遍历所有数字 num：

使用数字 1：
判断 1 >= 1，成立。
dp[1] = dp[1] + dp[1-1] = 0 + dp[0] = 1。
此时 dp[1] = 1，对应组合：[1]。

使用数字 2：
判断 1 >= 2，不成立（无法用 2 凑出 1），跳过。

结论：dp[1] = 1。此时能凑出 1 的只有 [1]。

3. 容量 2 （外层循环 i = 2）
我们需要计算 dp[2]，即凑出总和 2 的方法数。注意，这里会利用刚才算好的 dp[1] 的结果。

使用数字 1（最后一位放 1）：
判断 2 >= 1，成立。
dp[2] = dp[2] + dp[2-1] = 0 + dp[1]。
因为 dp[1] 等于 1，所以这里加 1。
这代表：在凑出 1 的所有方案 [1] 后面加上一个 1，得到 [1, 1]。

使用数字 2（最后一位放 2）：
判断 2 >= 2，成立。
dp[2] = dp[2] + dp[2-2] = 1（上一步结果） + dp[0]。
dp[0] 等于 1，所以这里再加 1。
这代表：在凑出 0 的所有方案 [] 后面加上一个 2，得到 [2]。

结论：dp[2] = 2。对应组合：[1, 1] 和 [2]。

4. 容量 3 （外层循环 i = 3）
这是最关键的步骤，解释为什么会出现 [1,2] 和 [2,1]。

我们需要计算 dp[3]，即凑出总和 3 的方法数。它会利用 dp[2] 和 dp[1] 的结果。

使用数字 1（最后一位放 1）：
判断 3 >= 1，成立。
dp[3] = dp[3] + dp[3-1] = 0 + dp[2]。
刚才算出 dp[2] = 2，所以这里加 2。
这代表的含义是：在凑出 2 的所有方案的末尾，加上一个 1。

凑出 2 的方案有 [1,1] 和 [2]。

在末尾加 1，得到 [1,1,1] 和 [2,1]。

使用数字 2（最后一位放 2）：
判断 3 >= 2，成立。
dp[3] = dp[3] + dp[3-2] = 2（上一步结果） + dp[1]。
刚才算出 dp[1] = 1，所以这里再加 1。
这代表的含义是：在凑出 1 的所有方案的末尾，加上一个 2。

凑出 1 的方案有 [1]。

在末尾加 2，得到 [1,2]。

最终结论：dp[3] = 2 + 1 = 3。
对应方案：

[1, 1, 1]（来自 dp[2] 的 [1,1] + 1）

[2, 1]（来自 dp[2] 的 [2] + 1）

[1, 2]（来自 dp[1] 的 [1] + 2）

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2
输入：coins = [1], amount = 0
输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] f = new int[n + 1][amount + 1];
        Arrays.fill(f[0], Integer.MAX_VALUE / 2); // 除 2 防止下面 + 1 溢出
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int c = 0; c <= amount; c++) {
                if (c < coins[i]) {
                    f[i + 1][c] = f[i][c];
                } else {
                    // 需正确区分状态转移方程
                    f[i + 1][c] = Math.min(f[i][c], f[i + 1][c - coins[i]] + 1);
                }
            }
        }
        int ans = f[n][amount];
        return ans < Integer.MAX_VALUE / 2 ? ans : -1;
    }
}

279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3
输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

  • 1 <= n <= 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    private static final int N = 10000;
    private static final int[][] f = new int[101][N + 1];

    static {
        Arrays.fill(f[0], Integer.MAX_VALUE);
        f[0][0] = 0;
        for (int i = 1; i * i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                if (j < i * i) {
                    f[i][j] = f[i - 1][j]; // 只能不选
                } else {
                    f[i][j] = Math.min(f[i - 1][j], f[i][j - i * i] + 1); // 不选 vs 选
                }
            }
        }
    }

    public int numSquares(int n) {
        return f[(int) Math.sqrt(n)][n]; // 也可以写 f[100][n]
        // 例如 n=12，sqrt(12)=3.46，取整得 3，使用 1²,2²,3² 就够用了
    }
}

难题暂缓

343. 整数拆分

474. 一和零

139. 单词拆分

其他动态规划

包括代码随想录中用动态规划做更简便的题和在其他刷题过程中未出现在代码随想录中的题

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int[] f = new int[nums.length];
        f[0] = nums[0];
        int ans = f[0];
        for (int i = 1; i < nums.length; i++) {
            f[i] = Math.max(f[i - 1], 0) + nums[i];
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。

返回 你能获得的 最大 利润 。

示例 1：

1
2
3
4
5
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

1
2
3
4
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][] f = new int[n + 1][2];          // 1. 建立DP表，+1是为了方便处理第0天的边界
    
    f[0][1] = Integer.MIN_VALUE;            // 2. 第0天不可能持有股票，设为负无穷
    
    for (int i = 0; i < n; i++) {
        // 第 i 天的价格是 prices[i]，但状态对应的是第 i+1 天结束后的结果
        // 3. 状态转移：第 i+1 天不持有股票的最大利润
        f[i + 1][0] = Math.max(f[i][0], f[i][1] + prices[i]);
        // 4. 状态转移：第 i+1 天持有股票的最大利润
        f[i + 1][1] = Math.max(f[i][1], f[i][0] - prices[i]);
    }
    
    return f[n][0];                         // 5. 最后一天不持有股票的利润就是答案
}

贪心

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

示例 1:

1
2
3
4
5
6
输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。
所以你应该输出 1。

示例 2:

1
2
3
4
5
6
输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0;
        // 对食品大小进行遍历，每个视频只比较一次
        for (int x : s) {
            if (i < g.length && g[i] <= x) {
                i++;
            }
        }
        return i;
    }
}

376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 **摆动序列 。**第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

1
2
3
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

1
2
3
4
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

1
2
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int prevdiff = nums[1] - nums[0];
        int ret = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            // 可以跳过中间不摆动的序列
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                ret++;
                prevdiff = diff;
            }
        }
        return ret;
    }
}

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canJump(int[] nums) {
        int mx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > mx) { // 无法到达 i
                return false;
            }
            mx = Math.max(mx, i + nums[i]); // 从 i 最右可以跳到 i + nums[i]
        }
        return true;
    }
}

步骤图解

示例1： nums = [2,3,1,1,4]

i nums[i] i > mx? i+nums[i] mx(更新前→后)
0 2 false 2 0 → 2
1 3 false 4 2 → 4
2 1 false 3 4(不变)
3 1 false 4 4(不变)
4 4 false 8 4 → 8

最终 mx >= nums.length-1，返回 true ✅

示例2： nums = [3,2,1,0,4]

i nums[i] i > mx? i+nums[i] mx(更新前→后)
0 3 false 3 0 → 3
1 2 false 3 3(不变)
2 1 false 3 3(不变)
3 0 false 3 3(不变)
4 ? i=4 > mx=3 - 无法到达i=4

返回 false ❌

45. 跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

  • 0 <= j <= nums[i] 且
  • i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int jump(int[] nums) {
    	int ans = 0;      // 记录跳跃次数
    	int curEnd = 0;   // 当前跳跃能到达的右边界
    	int nextEnd = 0;  // 再跳一次能到达的最远右边界
	
    	// 关键：只遍历到倒数第二个元素，因为到达最后一个元素就成功了
    	for (int i = 0; i < nums.length - 1; i++) {
    	    // 1. 探索：每走一步，都更新“再跳一次”能到达的最远位置
    	    // 位置i可以跳到的最远点是 i + nums[i]，取所有可能中的最大值
    	    nextEnd = Math.max(nextEnd, i + nums[i]);
	
    	    // 2. 决策：如果走到了当前跳跃能到达的边界
    	    if (i == curEnd) {
    	        // 必须进行下一次跳跃，并且能跳到的最远位置是之前探索好的 nextEnd
    	        curEnd = nextEnd;
    	        ans++; // 跳跃次数增加
    	    }
    	}
    	return ans;
	}
}

步骤图解

这个算法是 贪心策略 的一种经典实现。它不是“每步都跳最远”，而是“在不得不跳的时候，跳到能到达最远的位置”。代码通过 curEnd 和 nextEnd 两个变量，巧妙地分离了“探索”和“决策”两个阶段。

以 nums = [2, 3, 1, 1, 4] 为例，手动模拟：

索引 i nums[i] i + nums[i] nextEnd (更新后) 是否 i == curEnd curEnd (更新后) ans
0 2 2 max(0,2)=2 是 (0==0) 2 1
1 3 4 max(2,4)=4 否 (1!=2) 2 (不变) 1
2 1 3 max(4,3)=4 是 (2==2) 4 2
3 1 4 max(4,4)=4 否 (3!=4) 4 (不变) 2
  • 循环结束，返回 ans = 2。这对应从位置0跳到位置1（步长1），然后从位置1跳到位置4（步长3）。

1005. K 次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

  • 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：

1
2
3
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

1
2
3
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

1
2
3
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums); // 从小到大排序

        int sum = 0;
        int mn = Integer.MAX_VALUE;
        for (int x : nums) { // 优先改最小的
            if (k > 0 && x < 0) { // 还有修改次数，且 x 是负数
                x = -x; // 取反
                k--; // 消耗一次修改次数
            }
            sum += x;
            mn = Math.min(mn, x);
        }

        // 如果剩余的 k 是奇数，选最小的数取反
        return sum - (k % 2 > 0 ? mn * 2 : 0);
    }
}

860. 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

1
2
3
4
5
6
7
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

1
2
3
4
5
6
7
输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

  • bills[i] 不是 5 就是 10 或是 20
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        for (int b : bills) {
            if (b == 5) { // 无需找零
                five++;
            } else if (b == 10) { // 返还 5
                five--;
                ten++;
            } else if (ten > 0) { // 此时 b=20，优先用 10 美元，返还 10+5
                five--;
                ten--;
            } else { // 此时 b=20，返还 5+5+5
                five -= 3;
            }
            if (five < 0) { // 无法正确找零
                return false;
            }
        }
        return true;
    }
}

452. 用最少数量的箭引爆气球

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

1
2
3
4
5
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

1
2
3
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

1
2
3
4
5
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int findMinArrowShots(int[][] points) {
    // 1. 按照每个气球的右端点坐标从小到大排序
    Arrays.sort(points, Comparator.comparingInt(p -> p[1])); 

    int ans = 0;           // 记录需要的最少箭数
    long pre = Long.MIN_VALUE;  // 上一支箭放置的x坐标，初始为极小值

    // 2. 遍历所有气球（此时已按右端点升序）
    for (int[] p : points) {
        // 当前气球的左端点 > 上一支箭的x坐标
        // 说明上一支箭射不到当前气球，必须射新箭
        if (p[0] > pre) {
            ans++;          // 箭数+1
            pre = p[1];     // 新箭放在当前气球的右端点位置（最优选择）
        }
        // 否则（左端点 <= pre），当前气球能被上一支箭射中，跳过
    }
    return ans;
}

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

示例 1:

1
2
3
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

1
2
3
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

1
2
3
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 类似于上题的 用最少数量的箭引爆气球
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int nums = intervals.length;

        // 1. 按照每个气球的右端点坐标从小到大排序
        Arrays.sort(intervals, Comparator.comparingInt(p -> p[1])); 

        int ans = 0;           // 记录需要的最少箭数
        long pre = Long.MIN_VALUE;  // 上一支箭放置的x坐标，初始为极小值

        // 2. 遍历所有气球（此时已按右端点升序）
        for (int[] p : intervals) {
            // 当前气球的左端点 > 上一支箭的x坐标
            // 说明上一支箭射不到当前气球，必须射新箭
            if (p[0] >= pre) {
                ans++;          // 箭数+1
                pre = p[1];     // 新箭放在当前气球的右端点位置（最优选择）
            }
            // 否则（左端点 <= pre），当前气球能被上一支箭射中，跳过
        }
        return nums - ans;
    }
}

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

1
2
3
4
5
6
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

1
2
输入：s = "eccbbbbdec"
输出：[10]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> partitionLabels(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int[] last = new int[26];
        for (int i = 0; i < n; i++) {
            last[s[i] - 'a'] = i; // 每个字母最后出现的下标
        }

        List<Integer> ans = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            end = Math.max(end, last[s[i] - 'a']); // 更新当前区间右端点的最大值
            if (end == i) { // 当前区间合并完毕
                ans.add(end - start + 1); // 区间长度加入答案
                start = end + 1; // 下一个区间的左端点
            }
        }
        return ans;
    }
}

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

1
2
3
输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int[][] merge(int[][] intervals) {
        // 传达信息，"这是一个空的区间列表，但如果有区间的话，每个区间都应该是长度为2的数组。"
        if (intervals.length == 0) return new int[0][2];
        
        // 1. 按左端点排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // 2. 使用List存储合并后的区间
        List<int[]> ans = new ArrayList<>();
        ans.add(intervals[0]);
        
        for (int i = 1; i < intervals.length; i++) {
            int[] last = ans.get(ans.size() - 1);
            int[] curr = intervals[i];
            
            // 如果当前区间的左端点 <= 上一个区间的右端点，说明重叠
            if (curr[0] <= last[1]) {
                // 合并：更新右端点为两者较大值
                last[1] = Math.max(last[1], curr[1]);
            } else {
                // 不重叠，直接添加
                ans.add(curr);
            }
        }
        
        // 3. List转数组
        return ans.toArray(new int[ans.size()][]);
    }
}

难题暂缓

135. 分发糖果

406. 根据身高重建队列

738. 单调递增的数字

968. 监控二叉树