1.两数之和（哈希 简单）

img

注意点：

  • 你不能使用两次相同的元素
  • 每次输出只会存在一个有效答案

思路：

  • 为什么会想到用哈希法：每当我们遇到要判断这个元素是否在这个集合里出现过的时候，可以联想到哈希法
  • 为什么要用map：map可以在最快时间内查到元素是否出现过，把元素作为key，元素对应的下标作为value，这里用map存放我们遍历过的元素

img

img

img

img

初始代码

1
2
3
4
5
class Solution {
    public int[] twoSum(int[] nums, int target) {
        
    }
}

完整代码实现

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[] twoSum(int[] nums, int target) {
        Map<Integer,Integer>map=new HashMap<>();
        //1.遍历数组
        for (int i = 0; i < nums.length; i++) {
            //1.计算补数
            int complement = target - nums[i];
            //2.判断补数是否在map中
            if(map.containsKey(complement)){
                //3.返回结果
                return new int[]{map.get(complement),i};
            }
            //4.若当前元素不在map中，则将其加入到map
            map.put(nums[i],i);
        }
//        //5.如果最终遍历完了还没有找到，抛出一个异常
//        throw new IllegalArgumentException("No two sum solution");
        //5.如果最终遍历完了还没有找到，返回一个空数组
        return new int[0];
    }
}

补充：暴力枚举法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 //第二种写法:暴力枚举法
    public int[] twoSum1(int[] nums, int target) {
        //1.遍历数组
        for (int i = 0; i < nums.length; i++) {
            //2.遍历数组判断是否有补数
            for (int j = i + 1; j < nums.length; j++) {
                //3.判断是否有补数，如果有，返回结果
                if (nums[j] == target - nums[i]) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

2.移动零（双指针 - 简单）

img

思路：1.分两个数组，一个数组保存非零的数字，一个数组保存零的数字，分别遍历完后，再将这两个数组一合并 但这违反了题目中复杂度为O（1）

2.定义两个指针，让它们同时指向数组的第一个元素，当右指针指向的元素为0，我们就往右移动右指针，一直到右指针指向的元素不为0，这个时候我们就交换左右指针指向的元素，交换完左右指针指向的元素，左指针需要向右移一位，然后我们继续向右移动右指针，一直到指向的元素不为0，这个时候我们就交换左右指针指向的元素，继续之前的过程，直到右指针遍历完了整个数组

基于思路二实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void moveZeroes(int[] nums) {
//定义两个指针，让它们同时指向数组的第一个元素
    int left = 0;
    for (int right = 0; right < nums.length; right++) {
   //当右指针指向的元素为0，我们就往右移动右指针，一直到右指针指向的元素不为0，这个时候我们就交换左右指针指向的元素
        if (nums[right] != 0) {
            // 交换
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
        }
    }
}

或者这样优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public void moveZeroes(int[] nums) {
        // 使用双指针法
        int left = 0; // 记录非零元素的位置

        // 第一次遍历：将所有非零元素移到前面
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                nums[left] = nums[right];
                left++;
            }
        }

        // 第二次遍历：将剩余位置填充为0
        for (; left < nums.length; left++) {
            nums[left] = 0;
        }
    }
}

✅ 使用双指针；

✅ 不用额外数组；

✅ 时间复杂度 O(n)，空间复杂度 O(1)；

✅ 但没有“交换元素”，而是“覆盖非零 → 后补零”；

✅ 操作次数更少，效率更高（尤其当非零元素很多时）。

nums = [0, 1, 0, 3, 12]

一开始：nums = [0, 1, 0, 3, 12]
left = 0

遍历右指针过程：

right nums[right] 是否非零？ 操作 nums（当前状态） left
0 0 否 跳过 [0, 1, 0, 3, 12] 0
1 1 是 nums[0] = 1，left++ [1, 1, 0, 3, 12] 1
2 0 否 跳过 [1, 1, 0, 3, 12] 1
3 3 是 nums[1] = 3，left++ [1, 3, 0, 3, 12] 2
4 12 是 nums[2] = 12，left++ [1, 3, 12, 3, 12] 3

第二步：从 left 开始到末尾，全填 0

此时：

left = 3
nums = [1, 3, 12, 3, 12]

填 0：

left 操作 nums（当前状态）
3 nums[3] = 0 [1, 3, 12, 0, 12]
4 nums[4] = 0 [1, 3, 12, 0, 0]

3.两数相加（链表-中等）

img

思路：

img

  • 这里有两个链表L1和L2，还需要一个进位值carry来保存进位的符号
  • 例如上图的4+6，此时carry等于1（4+6+0），此时的carry就赋给下一次运算
  • 得到新链表的每一个值都是(L1.val+L2.val+carry)%10+ 例如例二7+9 =( 7+9+0)%10=6，因为初始的carry为0
  • 递归条件：只要 l1、l2、carry 还有一个没用完，就一直循环，递归结束条件：l1，l2，carry都为null的时候

代码实现：

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
public class Solution1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 初始化一个哑节点，方便处理头结点为空的情况
        ListNode dummyHead = new ListNode(-1);
        // 初始化一个指针，用于遍历链表
        ListNode cur = dummyHead;
        // 初始化进位
        int carry = 0;
        // 只要 l1、l2、carry 还有一个没用完，就一直循环：
        while (l1!=null||l2!=null||carry!=0){
            // 初始化两个链表的当前节点的值，如果为空则初始化为0
            int val1 = l1!=null?l1.val:0;
            int val2 = l2!=null?l2.val:0;
            // 计算当前节点的值
            int num = (val1+val2+carry)%10;
            // 计算进位
            carry = (val1+val2+carry)/10;
            // 创建新的节点，并将其加入到链表中
            cur.next = new ListNode(num);
            // 移动指针，l1和l2的指针向后移动一位
            cur = cur.next;

            // 移动两个链表的指针
            if(l1!=null) l1=l1.next;
            if(l2!=null) l2=l2.next;
        }
        // 返回哑节点的下一个节点，即链表的头结点
        return dummyHead.next;
    }
}

思考：

1.为什么要创建 dummyHead？为什么是 -1？

  • 这个 dummyHead 是一个哑节点（虚拟头节点），它的作用是： 简化链表操作，避免处理头节点为空或首个节点需要特殊处理的问题。
  • 它的 val 填什么其实无所谓，因为： 你最后只会返回 dummyHead.next，真正的结果链表从它“后面”开始。

2.cur.next = new ListNode(num);cur = cur.next;怎么理解

如果dummyHead → 7 → 0
cur 指向 0

你执行这一句：cur.next = new ListNode(8);

就会变成：dummyHead → 7 → 0 → 8
cur.next → 新的 8 节点

之后：cur = cur.next; // 把 cur 往后移到 8，准备连接下一个节点

为什么返回 dummyHead.next？

  • 回顾一下：dummyHead 是我们人为加的“虚拟头节点”，不属于最终结果；
  • 真正的加法结果是从 dummyHead.next 开始的。

dummyHead: -1 → 7 → 0 → 8

你真正的返回应该是：7 → 0 → 8 也就是从 dummyHead.next 开始的部分。

另一种递归写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addTwo(l1, l2, 0);
    }
    //L1,L2为当前遍历的节点，carry为进位
    private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
           //递归结束条件
        if (l1 == null && l2 == null && carry == 0) {
            return null;
        }
        if(l1!=null){
            carry+=l1.val;
            l1=l1.next;
        }
        if(l2!=null){
            carry+=l2.val;
            l2=l2.next;
        }
    return new ListNode(carry%10,addTwo(l1,l2,carry/10));
        }
    }
  • carry 不是单纯表示“上一次的进位”，它同时承担当前的“累加和”；
  • 每次把当前 l1 和 l2 的值加进去；
  • 然后将 l1、l2 指向下一个节点，为下一层递归准备。

  • 返回的是 ListNode(当前位, 下一位递归结果)，构建整条链表。

  • carry % 10：当前位的值（个位数）；

  • carry / 10：进位值，传递给下一层递归；
  • addTwo(...)：下一位的节点，递归返回值；
  • new ListNode(值, 下一节点)：创建当前节点并链接下一个。

4.二叉树的中序遍历（二叉树-简单）

img

中序遍历：左子树->根节点->右子树

从题中的例图可以看出来，1没有左子树，先返回根节点1，再返回右子树2和3,2为右子树的根节点2和3中，先返回左子树3，再返回根节点2，没有右子树，综上即[1,3,2]

思路：知道了中序遍历的规律，我们可以用递归的方法去做，方式一

方式二，还可以用栈来做，递归的调用过程是不断往左边走，当左边走不下去了，就打印节点，并转向右边，然后右边继续这个过程。我们在迭代实现时，就可以用栈来模拟上面的调用过程。

img

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
方式一，递归做法
public List<Integer> inorderTraversal(TreeNode root) {
        // 初始化结果列表
            List<Integer> res = new ArrayList<>();
            // 递归遍历二叉树
            dfs(res,root);
            return res;
    }
    void dfs(List<Integer> res,TreeNode root) {
        if (root == null) return;
        // 先遍历左子树
        dfs(res, root.left);
        // 再遍历根节点
        res.add(root.val);
        // 最后遍历右子树
        dfs(res, root.right);
    }
方式二,栈的方式
 public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer>res = new ArrayList<>();
            //创建一个栈，用来存放遍历的节点
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while(root!=null || !stack.isEmpty()){
                //如果当前节点不为空，就将该节点入栈，并遍历其左子树
                while(root!=null){
                    stack.push(root);
                    root = root.left;
                }
                //如果当前节点为空，说明左边走到投了，从栈中弹出节点并保存
                //然后遍历当前节点的右子树，并重复上述过程
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
            return res;
    }

5.搜索插入位置（二分查找-简单）

img

标准的二分查找题目

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

6.有效的括号（栈-简单）

img

用栈的方式来写

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
public boolean isValid(String s) {
    //定义一个栈用于存入当前的括号
    Stack<Character> stack = new Stack<>();
    //遍历字符串里的每一个字符
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        //如果是(，[，{则直接入栈
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            //如果不是(，[，{，则需要判断栈是否为空
            if (stack.isEmpty()) {
                return false;
            }
            // 检查栈顶元素是否是对应的开括号
            char top = stack.pop();
            if (c == ')' && top != '(' || c == ']' && top!= '[' || c == '}' && top != '{') {
                return false;
            } else {
                //不是对应的开括号，返回false
                return false;
            }
        }

    }
    //遍历完字符串后，如果栈为空，则说明括号匹配成功
    return stack.isEmpty();

优化一下：

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
public boolean isValid(String s) {
    // 创建一个栈来存放开括号
    Stack<Character> stack = new Stack<>();

    // 遍历字符串中的每个字符
    for (char c : s.toCharArray()) {
        //是开括号，压入栈中
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            // 如果是闭括号且栈为空，说明没有对应的开括号
            if (stack.isEmpty()) {
                return false;
            }
            // 检查栈顶元素是否是对应的开括号
            char top = stack.peek();
            if ((c == ')' && top == '(') || (c == '}' && top == '{') || (c == ']' && top == '[')) {
                // 是对应的开括号，弹出栈顶元素
                stack.pop();
            } else {
                // 不是对应的开括号，字符串无效
                return false;
 }
        }
    }
    //栈为空，说明所有的开括号都找到了对应的闭括号
    return stack.isEmpty();
}

2.用 Map<Character, Character> 的方式重写，使代码更优雅、结构更清晰。

使用 Map 来存储「括号的对应关系」可以让我们：

  • 不用写一大堆 if 或 switch
  • 在遇到右括号时，快速查到它对应的左括号
  • 逻辑更清晰、便于扩展（比如未来加 < > 等新括号）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean isValid(String s) {
       //对map保存每个右括号对应的左括号
       Map<Character, Character> map = new HashMap<>();
       map.put(')', '(');
       map.put(']', '[');
       map.put('}', '{');

       //用一个栈来保存尚未匹配的左括号
       Stack<Character> stack = new Stack<>();
       //遍历当前字符串并转为字符数组
       for (char c : s.toCharArray()) {
           if (map.containsKey(c)) {
               //如果当前字符是右括号，则判断栈顶元素是否与之匹配
               if (stack.isEmpty() || stack.pop() != map.get(c)) return false;
           } else {
               //如果当前字符是左括号，则将其压入栈中
               stack.push(c);
           }
       }
       //遍历完成后如果栈为空，则说明所有括号都匹配成功
       return stack.isEmpty();
   }

7.杨辉三角（动态规划-简单）

img

img

img

思路：

首先得先知道什么是杨辉三角，即第一行只有一个元素1，后续每行的首尾元素都为1，中间元素等于上一行相邻元素两个元素之和。此外，第i行有i个元素，元素个数和当前行数相同。下面来用动态规划五部曲进行分析。

  • 确定dp数组以及下标的含义：

dp[i] 表示杨辉三角中第i+1行的元素列表（从0开始计数），每个元素dp[i][j]表示该行的第j个位置上的数值

  • 确定递推公式：

dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 这个公式表示当前行的元素等于上一行相邻两个元素之和，如下图中的2的等于它的左上角和头顶之和

img

  • dp数组如何初始化：

初始化第一行只有一个元素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
public List<List<Integer>> generate(int numRows) {
        //1.定义一个集合来保存杨辉三角
        List<List<Integer>>dp = new ArrayList<>();
        //2.初始化，第一行只有一个元素
        if(numRows == 0){
            return dp;
        }
        //3.初始化第一行
        dp.add(new ArrayList<Integer>(){{
            add(1);
        }});
        //4.从第二行开始，每一行的元素个数为i+1个
        for(int i = 1;i < numRows;i++){
            List<Integer>row = new ArrayList<>();
            //5.初始化当前行的第一个和最后一个元素都为1
            //首元素为1
            row.add(1);
            //计算中间元素
            for(int j = 1;j < i;j++){
                //6.递推公式：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                row.add(dp.get(i-1).get(j-1) + dp.get(i-1).get(j));

            }
            //尾元素也为1
            row.add(1);
            //7.将当前行添加到二维数组中
            dp.add(row);

        }
        return dp;
    }

直接利用上一行（单数组滚动法）

思路：只保留上一行，用一个新列表构建当前行，完成后再赋值给上一行。节省空间到 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> prev = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> curr = new ArrayList<>();
        curr.add(1);                    // 首 1
        for (int j = 1; j < i; j++) {   // 中间
            curr.add(prev.get(j - 1) + prev.get(j));
        }
        if (i > 0) curr.add(1);         // 尾 1（首行除外）
        res.add(curr);
        prev = curr;                    // 更新上一行
    }
    return res;
}

二维数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<List<Integer>> generate(int numRows) {
    int[][] tri = new int[numRows][numRows];
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        tri[i][0] = tri[i][i] = 1;
        for (int j = 1; j < i; j++) {
            tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
        }
        // 复制有效部分到 List
        List<Integer> row = new ArrayList<>();
        for (int j = 0; j <= i; j++) row.add(tri[i][j]);
        res.add(row);
    }
    return res;
}

8.只出现一次的数字（位运算-简单）

img

位运算中的异或运算 XOR，主要因为异或运算有以下几个特点：

  • x ^ x = 0 （任何数与自己异或结果为0）
  • x ^ 0 = x （任何数与0异或结果为该数本身）
  • XOR是交换的和结合的。
  • 故而在以上的基础条件上，将所有数字按照顺序做异或运算，最后剩下的结果即为唯一的数字

img

异或位运算：

1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
        int ans = 0;
       for(int num: nums) {
           ans ^= num;
       }
       return ans;
     }

img

9.相交链表（链表-简单）

img

img

img

要求：两个单链表，如果有交点，返回这个交点；否则返回 null。

思路：

两个指针 P 和 Q 的奇妙走法

我们设置两个指针：

  • p 从 headA 出发
  • q 从 headB 出发

如果 p 到达了链表末尾，就从 headB 开始走；
如果 q 到达了链表末尾，就从 headA 开始走。
直到它们相遇为止（或者都为 null）。

假设如下：

  • A 链表为：a + c，a 是独有部分，c 是公共部分
  • B 链表为：b + c，b 是独有部分，c 是公共部分
  • 公共部分长度为 c
  • 则：
    • p 总共走：a + c + b
    • q 总共走：b + c + a

也就是说，两个指针最终都走了 a + b + c 的长度！
如果两个链表有交点，它们一定在 c 的起点相遇。
如果没有交点，p 和 q 会最终都走到 null，然后一起退出循环。

img

（leetcode网友热评）

走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。

走过彼此的路，我们终会相遇❤️❤️❤️

代码如下：

1
2
3
4
5
6
7
8
9
10
11
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        //循环停止的条件是p的长度和q的长度一样时
        while(q!= p){
            //当某个指针走完自己链表时，换去走对方的整条链表
            p = (p!= null) ? p.next : headB;
            q = (q!= null) ? q.next : headA;
        }
        return p;
    }

暴力法

简单的一个想法，对链表 A 中的每一个结点，我们都遍历一次链表 B 查找是否存在重复结点，第一个查找到的即第一个公共结点

1
2
3
4
5
6
7
8
9
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       for (ListNode p = headA; p != null; p = p.next) {
           for (ListNode q = headB; q != null; q = q.next) {
               if (p == q)
                   return p;
           }
       }
       return null;
   }

哈希表法

基本思路：用 HashSet 存一个链表的所有节点

  1. 先遍历链表 A，把它所有的节点放进一个 HashSet 中（注意是节点本身，不是值）。
  2. 然后遍历链表 B，每走一个节点，就判断是否存在于这个 HashSet 中。
  3. 如果存在，说明从该节点开始就是交点。
  4. 如果 B 走完都没有命中，返回 null。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       HashSet<ListNode>set = new HashSet<>();
       //将链表A的所有节点放入哈希表中
       for(ListNode p = headA;p!=null;p=p.next){
           set.add(p);
       }
       //遍历链表B，查找第一个在set里的节点
       for(ListNode q = headB;q!=null;q=q.next){
           if(set.contains(q)){
               return q;
           }
       }
       return null;
   }

栈的做法

两个链表如果在某个节点相交，那么从相交点开始到链表末尾的所有节点是完全一样的（引用相同）。

因此，我们可以：

  1. 把两个链表的节点分别存入两个栈/双端队列中；
  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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 创建两个栈（使用Deque实现）
    Deque<ListNode> s1 = new ArrayDeque<>();
    Deque<ListNode> s2 = new ArrayDeque<>();

    // 把链表A的所有节点依次加入栈中（从头到尾）
    for (ListNode p = headA; p != null; p = p.next) {
        s1.addLast(p); // 相当于 s1.push(p)
    }

    // 把链表B的所有节点依次加入另一个栈中
    for (ListNode p = headB; p != null; p = p.next) {
        s2.addLast(p);
    }

    // 从尾部开始逐个比较两个栈的节点
    ListNode ans = null;
    while (!s1.isEmpty() && !s2.isEmpty() && s1.peekLast() == s2.peekLast()) {
        s1.pollLast();       // 弹出一个节点
        ans = s2.pollLast(); // 弹出并记录最新相同节点
    }

    return ans; // 最后一个相同的节点就是交点（或 null）
}

10.二叉树的最大深度（二叉树-简单）

img

1.后序遍历（DFS）

树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现，这里使用递归实现。

关键点： 此树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度中的 最大值 +1 。

  • 终止条件： 当 root 为空，说明已越过叶节点，因此返回 深度 0 。
  • 递推工作： 本质上是对树做后序遍历。
  • 计算节点 root 的 左子树的深度 ，即调用 maxDepth(root.left)。
  • 计算节点 root 的 右子树的深度 ，即调用 maxDepth(root.right)。
  • 返回值： 返回 此树的深度 ，即 max(maxDepth(root.left), maxDepth(root.right)) + 1

img

1
2
3
4
5
6
7
8
9
10
11
12
public int maxDepth(TreeNode root) {
         //如果root为空，则深度为0
        if(root==null){
            return 0;
        }
        //递归求左子树和右子树的深度
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        //返回左右子树深度的最大值+1（加上当前节点）
        return Math.max(leftDepth,rightDepth)+1;
    }
}

2.层序遍历（BFS）

树的层序遍历 / 广度优先搜索往往利用 队列 实现。

关键点： 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。

  • 特例处理： 当 root 为空，直接返回 深度 0 。
  • 初始化： 队列 queue （加入根节点 root ），计数器 res = 0。
  • 循环遍历： 当 queue 为空时跳出。
  • 初始化一个空列表 tmp ，用于临时存储下一层节点。
  • 遍历队列： 遍历 queue 中的各节点 node ，并将其左子节点和右子节点加入 tmp。
  • 更新队列： 执行 queue = tmp ，将下一层节点赋值给 queue。
  • 统计层数： 执行 res += 1 ，代表层数加 1。
  • 返回值： 返回 res 即可。

img

img

img

img

img

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int max = 0;
        List<TreeNode>queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            //用来临时保存下一层的节点
            List<TreeNode>temp = new LinkedList<>();
            //遍历当前层
            for (TreeNode node : queue) {
                if (node.left != null) temp.add(node.left);
                if (node.right != null) temp.add(node.right);
            }
            //下一层赋值给队列
            queue = temp;
            max++;//每遍历一层深度加1
        }
        return max;
    }

11.翻转二叉树（简单-二叉树）

img

递归法

思路：交换每个节点的左子树和右子树

根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。

递归解析：
终止条件： 当节点 root 为空时（即越过叶节点），则返回 null 。
递推工作：
初始化节点 tmp ，用于暂存 root 的左子节点。
开启递归 右子节点 invertTree(root.right) ，并将返回值作为 root 的 左子节点 。
开启递归 左子节点 invertTree(tmp) ，并将返回值作为 root 的 右子节点 。
返回值： 返回当前节点 root 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public TreeNode invertTree(TreeNode root) {
    // 1. 基础情况：如果根节点为空，则直接返回空节点
    if (root == null) {
        return root;
    }
    
    // 2. 保存左子树
    TreeNode temp = root.left;

    // 3. 递归翻转右子树，并将结果赋给当前节点的左子树
    root.left = invertTree(root.right);

    // 4. 递归翻转左子树，并将结果赋给当前节点的右子树
    root.right = invertTree(temp);

    // 5. 返回根节点
    return root;
}

方法2：辅助栈（或队列）
利用栈（或队列）遍历树的所有节点 node ，并交换每个 node 的左 / 右子节点。

算法流程：
特例处理： 当 root 为空时，直接返回 null 。
初始化： 栈（或队列），本文用栈，并加入根节点 root 。
循环交换： 当栈 stack 为空时跳出。
出栈： 记为 node 。
添加子节点： 将 node 左和右子节点入栈。
交换： 交换 node 的左 / 右子节点。
返回值： 返回根节点 root 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public TreeNode invertTree(TreeNode root) {
       if (root == null) {
           return root;
       }
       //创建一个栈，并将根节点入栈
       Stack<TreeNode>stack = new Stack<>();
       stack.push(root);
       while (!stack.isEmpty()) {
           TreeNode node = stack.pop();
           //交换左右子树
           TreeNode temp = node.left;
           node.left = node.right;
           node.right = temp;
           //交换完成后，检查当前节点的左右子树。如果它们不为空，分别将左右子节点入栈，以便在后续遍历时处理这些子节点。
           if (node.left != null) {
               stack.push(node.left);
           }
           if (node.right != null) {
               stack.push(node.right);
           }
       }
       return root;
   }

12.岛屿数量（BFS/DFS 中等）

img

img

img

岛屿由水平方向或竖直方向上相邻的陆地连接形成

思路：

1.广度优先搜索（BFS）

只需搜索该元素水平和垂直方向的元素，之后再遍历每行没被搜索的元素，值为1时继续开始广度优先搜索

img

  • 初始化岛屿计数器 res 为 0。
  • 遍历网格：
  • 每次遇到值为 '1' 的格子时，启动 BFS 并将其与其他相连的 '1' 都标记为 '0'，每次启动 BFS 都将岛屿计数器 res 加 1。
  • BFS 搜索：
  • 使用队列来进行 BFS，遍历该岛屿的每个格子，并将相邻的格子（上下左右）也加入队列，继续标记已访问的格子。
  • 返回结果：
  • 最终返回 res，即岛屿的总数。
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 numIslands(char[][] grid) {
        //定义一个表示岛屿数量的变量
        int count = 0;
        //这个两层for循环是用来遍历整张二维表格中所有的陆地
        //其中 i 表示行，j 表示列
        for(int i = 0; i<grid.length;i++){
            for(int j =0;j<grid[0].length;j++){
                //取出所有的陆地
                if(grid[i][j] == '1'){
                    //深度递归，遍历所有的陆地
                    dfs(grid,i,j);
                    //用来统计有多少岛屿，岛屿是由多个陆地组成的，概念不一样
                    count++;
                }
            }
        }
        //返回岛屿的数量
        return count;
    }
    public void dfs(char[][] grid,int i, int j){
        //防止 i 和 j 越界，也就是防止超出岛屿（上下左右）的范围。特别注意当遍历到海洋的时候也退出循环
        if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]=='0') return;
        //将遍历过的陆地改为海洋，防止重复遍历
        grid[i][j]='0';
        //上，
        dfs(grid,i+1,j);
        //下
        dfs(grid,i-1,j);
        //右
        dfs(grid,i,j+1);
        //左
        dfs(grid,i,j-1);
    }
}

2.深度优先搜索（DFS）

DFS就是沿着一条路径一直走下去，每个位置只要是1，先要把它置为0，然后沿着他的上下左右4个方向继续遍历，执行同样的操作，要注意边界条件的判断。

img

初始化：岛屿数量 res 设为 0，开始遍历 grid 中的每一个元素。

发现岛屿：当遇到岛屿（1）时，启动 DFS，标记该岛屿及其相邻部分。

递归过程：每次调用 dfs 会将当前岛屿的一个部分标记为已访问（2），并递归地访问该岛屿的上下左右四个相邻格子，直到该岛屿的所有部分都被访问。

岛屿计数：每次从未访问的岛屿（1）开始 DFS，岛屿数量 res 增加 1。

返回结果：遍历完网格后，返回岛屿总数 res。

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 int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {// 遍历每一行
            for (int j = 0; j < grid[0].length; j++) {// 遍历每一列
                if (grid[i][j] == '1') {// 如果是陆地（岛屿）
                    dfs(grid, i, j);  //从当前点开始进行DFS，标记整个岛屿
                    res++;// 每次DFS执行完，说明发现了一个岛屿
                }
            }
        }
        return res; // 返回岛屿的总数
    }

    public void dfs(char[][] grid, int r, int d) {
        // base case: 边界检查和是否是岛屿（值为1）
        if (r < 0 || d < 0 || r >= grid.length || d >= grid[0].length || grid[r][d] != '1') {   //越界或不是岛屿了，则返回
            return;
        }
         // 标记为已访问
        grid[r][d] = '2'; // 标记该格子为已访问（'2'）
         // 递归地访问岛屿的四个方向（上下左右）
        dfs(grid, r - 1, d); //上
        dfs(grid, r + 1, d); //下
        dfs(grid, r, d - 1); //左
        dfs(grid, r, d + 1); //右
    }

}

13.反转链表（链表-简单）

img

方法1递归

思路：使用递归法遍历链表，当越过尾节点后终止递归，在回溯时修改各节点的 next 引用指向。

img

img

img

img

img

img

recur(cur, pre) 递归函数：

  • 终止条件：当 cur 为空，则返回尾节点 pre （即反转链表的头节点）；
  • 递归后继节点，记录返回值（即反转链表的头节点）为 res ；
  • 修改当前节点 cur 引用指向前驱节点 pre ；
  • 返回反转链表的头节点 res ；

reverseList(head) 函数：

调用并返回 recur(head, null) 。传入 null 是因为反转链表后， head 节点指向 null ；

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head, null);    // 调用递归并返回
    }
    private ListNode recur(ListNode cur, ListNode pre) {
        if (cur == null) return pre; // 终止条件
        ListNode res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }
}

方法2迭代（双指针）

考虑遍历链表，并在访问各节点时修改 next 引用指向

img

img

img

img

img

img

img

img

img

img

img

img

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;
        while(cur != null) {
            ListNode tmp = cur.next; // 暂存后继节点 cur.next
            cur.next = pre;          // 修改 next 引用指向
            pre = cur;               // pre 暂存 cur
            cur = tmp;               // cur 访问下一节点
        }
        return pre;
    }
}

14.对称二叉树（二叉树-简单）

img

思路：

对称二叉树定义： 对于树中 任意两个对称节点 L 和 R ，一定有：

L.val = R.val ：即此两对称节点值相等。
L.left.val = R.right.val ：即 L 的 左子节点 和 R 的 右子节点 对称。
L.right.val = R.left.val ：即 L 的 右子节点 和 R 的 左子节点 对称。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isSymmetric(TreeNode root) {
       return root ==null || isMirror(root.left, root.right);
   }
   public boolean isMirror(TreeNode L, TreeNode R) {
       // 如果两个节点都为空，则对称
       if (L == null && R == null) return true;
       // 如果两个节点只有一个为空，则不对称
       if (L == null || R == null) return false;
       // 如果两个节点的值不相同，则不对称
       if (L.val != R.val) return false;
       // 递归判断左子树的右节点和右子树的左节点是否对称，以及左子树的左节点和右子树的右节点是否对称
       return isMirror(L.left, R.right) && isMirror(L.right, R.left);
   }

15.二叉树的直径（二叉树-简单）

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int diameter = 0;
   public int diameterOfBinaryTree(TreeNode root) {
      
       //二叉树直径的定义：任意两个节点路径中，最长的一条边的长度
       getDepth(root);
       return diameter;
   } 
       public int getDepth(TreeNode root) {
       //二叉树为空时，直径为0
       if (root == null) {
           return 0;
       }
       //递归计算左右子树的深度
       int leftDepth = getDepth(root.left);
       int rightDepth = getDepth(root.right);
       //更新直径的长度
       diameter = Math.max(diameter, leftDepth + rightDepth);
       return 1 + Math.max(leftDepth, rightDepth);
       
   }

img

img

16.二叉树的层序遍历（二叉树-中等）

img

思路：

1.BFS(广度优先遍历)

广度优先遍历是按层层推进的方式，遍历每一层的节点。题目要求的是返回每一层的节点值，所以这题用广度优先来做非常合适。广度优先需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列。

img

首先拿出根节点，如果左子树/右子树不为空，就将他们放入队列中。第一遍处理完后，根节点已经从队列中拿走了，而根节点的两个孩子已放入队列中了，现在队列中就有两个节点 2 和 5。

img

第二次处理，会将 2 和 5 这两个节点从队列中拿走，然后再将 2 和 5 的子节点放入队列中，现在队列中就有三个节点 3，4，6。

img

我们把每层遍历到的节点都放入到一个结果集中，最后返回这个结果集就可以了。

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
public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        ArrayList<TreeNode> queue = new ArrayList<>();
        //先将根节点放入队列
        queue.add(root);
        while (!queue.isEmpty()) {
            //获取当前队列的长度，这个长度就是这一层节点的个数
            int size = queue.size();
            //存放当前层的节点
            List<Integer> curLevel = new ArrayList<>();
            //遍历当前层的节点，并将其子节点放入队列中
            for (int i = 0; i < size; i++) {
                //取出队列的第一个节点
                TreeNode node = queue.remove(0);
                //将节点的值放入当前层的集合中
                curLevel.add(node.val);
                //将节点的子节点放入队列中
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            //将当前层的节点放入结果集
            res.add(curLevel);
        }
        return res;
    }

2.DFS(深度优先搜索)

img

img

img

按照深度优先的处理顺序，会先访问节点 1，再访问节点 2，接着是节点 3。
之后是第二列的 4 和 5，最后是第三列的 6。

每次递归的时候都需要带一个 index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的 list 不存在，就加入一个空 list 进去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) {
            return new ArrayList<>();
        }
        //用来存放最终的结果
        List<List<Integer>> res= new ArrayList<>();
        dfs(1,root,res);// 从第 1 层开始递归
        return res;
    }
    void dfs(int index,TreeNode root,List<List<Integer>> res){

        if(res.size() < index){
            res.add(new ArrayList<Integer>());// 确保每一层有一个 list
        }
        res.get(index - 1).add(root.val); // 将当前节点的值加入该层 list
        if(root.left != null) dfs(index + 1, root.left, res); // 递归处理左子树
        if(root.right != null) dfs(index + 1, root.right, res);// 递归处理右子树
    }

img

17.盛最多水的容器（双指针-中等）

img

给定一个长度为 n 的整数数组 height，其中每个元素代表柱子的高度。在坐标轴上画出这些柱子，选择其中两根柱子与 x 轴共同构成一个容器，求这个容器可以容纳的最多水量。

思路：

缩减搜索空间

要解决的核心问题是：

为什么移动较短边是对的？会不会错过最大面积的可能性？

举例

假设当前两根柱子 i 和 j，height[i] < height[j]：

  1. 由于面积受限于较短的柱子（即 height[i]），
  2. 并且我们要缩短宽度了（因为下一步是往中间靠），
  3. 那么为了可能增加面积，唯一的机会是找到更高的柱子来提升高度（否则面积一定变小）

所以：
移动较短的柱子才有可能找到更优解；移动较长边肯定是浪费计算。

img

img

这个逻辑保证了不会遗漏最大面积。

从搜索空间来看，一开始我们有完整的二维搜索空间（i < j 的所有组合），双指针的过程就像在这个空间中不断缩小边界：

img

由于 i、j 的约束条件的限制，搜索空间是白色的倒三角部分。可以看到，搜索空间的大小是 O(n2) 数量级的。如果用暴力解法求解，一次只检查一个单元格，那么时间复杂度一定是 O(n2)。要想得到 O(n) 的解法，我们就需要能够一次排除多个单元格。那么我们来看看，本题的双指针解法是如何削减搜索空间的：

一开始，我们检查右上方单元格 (0,7)，即考虑最左边的 0 号柱子和最右边的 7 号柱子，计算它们之间容纳水的面积。然后我们比较一下两根柱子的高度，关注其中较短的一根。

img

假设左边的 0 号柱子较短。根据刚才的推理，0 号柱子目前的水面高度已经到了上限。由于 7 号柱子已经是离 0 号柱子最远的了，水的宽度也最大，如果换其他的柱子和 0 号柱子配对，水的宽度只会更小，高度也不会增加，容纳水的面积只会更小。也就是说，0 号柱子和 6,5,…,1 号柱子的配对都可以排除掉了。记录了 (0,7) 这组柱子的结果之后，就可以排除 0 号柱子了。这相当于 i=0 的情况全部被排除。对应于双指针解法的代码，就是 i++；对应于搜索空间，就是削减了一行的搜索空间，如下图所示。

img

排除掉了搜索空间中的一行之后，我们再看剩余的搜索空间，仍然是倒三角形状。我们检查右上方的单元格 (1,7)，即考虑 1 号柱子和 7 号柱子，计算它们之间容纳水的面积。然后，比较两根柱子的高度。

img

假设此时 7 号柱子较短。同理， 7 号柱子已经是离 1 号柱子最远的了，如果换其他的柱子和 1 号柱子配对，水的宽度变小，高度也不会增加，容纳水的面积只会更小。也就是说，7 号柱子和 2,3,…,6 号柱子的配对都可以排除掉了。记录了 (1,7) 这组柱子的结果之后，就可以排除 7 号柱子了。这相当于 j=7 的情况全部被排除。对应于双指针解法的代码，就是 j—；对应于搜索空间，就是削减了一列的搜索空间，如下图所示。

img

可以看到，无论柱子 i 和 j 哪根更长，我们都可以排除掉一行或者一列的搜索空间。经过 n 步以后，就能排除所有的搜索空间，检查完所有的可能性。搜索空间的减小过程如下面动图所示：

img

双指针解法的本质是：在每一步都通过移动较短的柱子，来尝试在缩小宽度的同时，提升高度，从而寻找可能的更大面积 —— 同时还能有效剪枝搜索空间，避免 O(n²) 的暴力搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxArea(int[] height) {
        int maxArea = 0;
        int i = 0;
        int j = height.length - 1;
        while(i<j){
            //计算当前容器的面积
            int area = (j-i)*Math.min(height[i],height[j]);
            //更新最大面积
            maxArea = Math.max(maxArea,area);
            //移动短的那一边，因为移动长的一边并不能增加面积
            if(height[i]<height[j]){
                i++;
            }else{
                j--;
            }
        }
        return maxArea;
    }

双指针指向数组两端：

  • i：左指针，从头开始
  • j：右指针，从尾开始

每一步：

  • 计算当前两根柱子组成的面积 (j - i) * min(height[i], height[j])
  • 尝试移动较短的那根柱子，期待找到更高的柱子，从而有可能增大面积
  • 一旦 i == j，遍历完成

用时最短的答案，思路是一样的：

18.字母异位词分组（哈希 中等）

img

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

方法一：排序
字母相同，但排列不同的字符串，排序后都一定是相同的。因为每种字母的个数都是相同的，那么排序后的字符串就一定是相同的。

把“排序后的串”当作 键 key，把原始单词丢进以该 key 为索引的列表里。最后把这些列表作为结果返回。

  • 遍历每个字符串，将它转成字符数组并排序。
  • 排序后的字符串作为键（key），把它存到一个 HashMap<String, List<String>> 中。
  • 相同 key 的单词放到同一个 list 里，最后把 map 中的所有 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
import java.util.*;

public class Solution {
    // 入参是字符串数组，返回若干分组（每组是一个 List）
    public List<List<String>> groupAnagrams(String[] strs) {
        // key: 排序后的字符串；value: 具有相同 key 的原始字符串列表
        Map<String, List<String>> map = new HashMap<>();
        
        for (String str : strs) {
            // 1) 字符串 → 字符数组
            char[] chars = str.toCharArray();
            // 2) 对字符数组排序（O(L log L)，L 为该单词长度）
            Arrays.sort(chars);
            // 3) 排序后的字符数组还原成字符串，作为“签名/键”
            String key = new String(chars);
            // 4) 把原串放入该 key 对应的桶里
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }
        
        // map.values() 是一个“视图”集合，这里拷贝成新的 ArrayList 作为返回值
        return new ArrayList<>(map.values());
    }
}

img

img

方法二，计数法

计数法”版本的核心思想是：

  • 不再对字符串进行排序（O(L log L)），而是统计 26 个字母的出现次数（O(L)）。
  • 用字母计数结果作为 签名 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
import java.util.*;

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            int[] count = new int[26]; // 小写字母频次数组
            for (char c : str.toCharArray()) {
                count[c - 'a']++;
            }

            // 把频次数组转成字符串 key，例如 aab -> "2#1#0#0#..."
            // 用 '#' 分隔避免 "11" 和 "1"+"1" 混淆
            StringBuilder sb = new StringBuilder();
            for (int freq : count) {
                sb.append(freq).append('#');
            }
            String key = sb.toString();

            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }

        return new ArrayList<>(map.values());
    }
}

img

19.和为K的子数组（子串 中等）

img

  • 子数组必须是连续的；
  • 要找出所有子数组之和 = k 的个数；
  • 暴力做法是用两层循环计算所有可能的子数组和，时间复杂度是 O(n²)，会超时；
  • 优化做法用 前缀和 + 哈希表 实现 O(n) 的时间复杂度。

什么是前缀和？

前缀和 preSum[i] 表示从第 0 个数到第 i-1 个数的总和。
比如数组 nums = [1,2,3]，前缀和数组是：

1
preSum = [0, 1, 3, 6]

因为：

  • preSum[0] = 0
  • preSum[1] = 1
  • preSum[2] = 1+2 = 3
  • preSum[3] = 1+2+3 = 6

核心思想：

子数组之和 = k，等价于：

对于两个下标 i 和 j（j > i）来说：

1
preSum[j] - preSum[i] == k

如上例子的preSum = [0, 1, 3, 6]，nums = [1,2,3]中1=preSum[1] -preSum[0]

2=preSum[2] -preSum[1] ，3=preSum[3] -preSum[2]

也就是说，从 i 到 j-1 的子数组和是 k！

那么就可以反过来思考：

1
preSum[j] - k == preSum[i]

具体做法：

  1. 初始化：

    • 创建一个哈希表 preCnt 来记录每个前缀和出现的次数；
    • 放入初始值：preCnt[0] = 1，表示和为 0 的前缀和出现了一次。

  2. 遍历数组 

    1
    nums

    ：

    • 每一步累加当前值，得到新的 preSum；

    • 检查：有没有之前的某个前缀和 

      1
      preSum - k

      ？

      • 有的话，就说明存在一个子数组的和是 k，累计结果；

    • 把当前的 preSum 存入哈希表中，出现次数 +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
public int subarraySum(int[] nums, int k) {
        //初始化数组
        int len =nums.length;
        int[]preSum = new int[len+1];
        preSum[0]=0;
        //计算每一个前缀
        for(int i =0;i<nums.length;i++)
        {
            preSum[i+1]=preSum[i]+nums[i];
        }
        //eg：nums = [1, 2, 3] ，preSum = [0, 1, 3, 6]
        int res=0;//记录 统计最终的子数组个数。
        //创建一个哈希表preCnt来记录每个前缀和出现的次数
        HashMap<Integer,Integer> preCnt = new HashMap<>();

        //遍历每一个前缀和，查找是否存在满足条件的区间
        for(int sj:preSum){

            int si = sj-k;//eg：nums = [1, 2, 3] ，preSum = [0, 1, 3, 6]其中1=preSum【1】-preSum【0】
            if(preCnt.containsKey(si)){
                 res += preCnt.get(si);// 有几个 si，就加几个答案
            }
            //然后记得更新当前 sj 的出现次数（给后面用）：
            preCnt.put(sj,preCnt.getOrDefault(sj,0)+1);//更新当前前缀和sj出现次数
        }
            return res;
    }

img

img

20.最大子数组和（动态规划 中等）

img

思路：看描述就知道应该是一个经典的动态规划题目

img

定义两个变量：一个是截至目前的累加量，current_sum,一个是截止目前见过的最大的量，如果current_sum没有当前元素大，我们不妨放弃current_sum，从当前数组元素重新开始，遍历完整个数组后，max_sum就记录了最大子数组和

img

例如从第一个数-2开始，current_sum和max_sum都为-2，当遍历到了1，让current_sum+1和1对比，发现-1<1所以我们选择重新开始

current_sum和max_sum更新为1

img

接下来是-3，我们选择继续累加，更新current_sum

img

接下来是4选择继续累加为2小于当前元素4，因为我们选择重新开始，并更新最大数组和

img

同理一直累加直到数组完全遍历完，拿出最后的max_sum，这就是最终的最大子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
        //定义累加和
        int currentSum = nums[0];
        //定义最大子数组和
        int maxSum = nums[0];
        for(int i = 1;i<nums.length;i++){
            //要么把nums【i】加到current_sum中，要不就从nums【i】重新开始
            currentSum = Math.max(currentSum+nums[i],nums[i]);
            //从当前累加和与之前最大的子数组和对比，较大的值就是新的最大子数组和
            maxSum = Math.max(maxSum,currentSum);
        }
        return maxSum;
    }

以下是Kadane 算法 的另一种写法，来自leetcode画手大鹏

题目：最大子数组和
我们要找一个连续子数组，它的和最大。

关键观察：

  • 如果之前累积的和 sum 是 正的，它对后面的子数组有帮助（加上它会更大），所以可以继续加。
  • 如果之前累积的和 sum 是 负的 或 0，它对后面的子数组是负担（加上它会更小），所以应该丢掉，从当前这个数重新开始。

遍历数组时，如果当前累积和是正数，就延续下去；如果是负数，就丢掉重新开始，同时更新全局最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maxSubArray(int[] nums) {
     //定义当前子数组累加和
     int currentSum = 0;
     //定义目前的最大子数组和
     int maxSum = nums[0];
     for(int num : nums){
         if(currentSum>0){
         //当前子数组的和是正的，就继续加
           currentSum+=num;
         }else{
             //否则重新从当前num开始
             currentSum = num;
         }
           //从当前累加和与之前最大的子数组和对比，较大的值就是新的最大子数组和
        maxSum= Math.max(maxSum,currentSum);
     }
     //从当前累加和与之前最大的子数组和对比，较大的值就是新的最大子数组和
     return maxSum;
 }

21.回文链表（链表 简单）

img

解题思路：

  1. 快慢指针：使用快慢指针找到链表的中间节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末尾时，慢指针刚好到达链表的中间。
  2. 反转后半部分链表：从慢指针开始，将链表的后半部分反转。
  3. 比较前半部分与后半部分：将链表的前半部分和反转后的后半部分逐个节点进行比较，如果每个节点都相等，说明是回文链表。

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

  • 快慢指针找到中点：2
  • 反转后半部分：1 <- 2
  • 比较前半部分和反转后的后半部分：[1, 2] 和 [1, 2] 相同，返回 true。

输入：head = [1, 2]

  • 快慢指针找到中点：2
  • 反转后半部分：2
  • 比较前半部分和反转后的后半部分：[1] 和 [2] 不相同，返回 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
38
39
public boolean isPalindrome(ListNode head) {
       if (head == null || head.next == null) {
           return true;
       }

       // 步骤1：找到链表中间节点（快慢指针）
       ListNode slow = head, fast = head;
       while (fast != null && fast.next != null) {
           slow = slow.next;
           fast = fast.next.next;
       }

       // 步骤2：反转链表的后半部分
       ListNode secondHalf = reverse(slow);
       ListNode firstHalf = head;

       // 步骤3：比较前半部分和反转后的后半部分
       while (secondHalf != null) {
           if (firstHalf.val != secondHalf.val) {
               return false;
           }
           firstHalf = firstHalf.next;
           secondHalf = secondHalf.next;
       }

       return true;
   }

   // 反转链表
   private ListNode reverse(ListNode head) {
       ListNode prev = null, curr = head;
       while (curr != null) {
           ListNode nextNode = curr.next;
           curr.next = prev;
           prev = curr;
           curr = nextNode;
       }
       return prev;
   }

法2：将链表的值存入一个数组，然后通过双指针的方式（从头和尾同时比较）判断数组是否是回文的。

  • 将链表元素存入数组：遍历链表，将链表中的每个节点的值存入一个数组中。这样，链表的元素就转化成了一个一维数组，方便后续处理。
  • 双指针比较：通过两个指针，一个从数组的开始位置，一个从数组的结束位置，逐个比较它们的值。如果有任何一对不相等，说明链表不是回文链表，直接返回 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
class Solution { 
    private static int[] a = new int[100000]; // 定义一个数组用来存储链表节点的值，假设链表长度不超过 10^5

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;  // 如果链表为空或只有一个节点，直接返回 true

        final int[] arr = a;  // 引用数组 a（可以直接使用类级别的数组 a）
        int size = 0;  // 用于记录链表的长度
        
        // 遍历链表，将节点的值存入数组
        while (head != null) {
            arr[size++] = head.val;  // 将节点值放入数组 arr 中，size 自增
            head = head.next;  // 移动到下一个节点
        }

        int m = size / 2;  // 找到数组的中间位置（回文对称的中间）
        
        // 双指针法，比较前后两部分是否相等
        for (int i = 0; i < m; i++) {
            if (arr[i] != arr[--size])  // arr[i] 是从前往后的第 i 个元素，arr[--size] 是从后往前的第 i 个元素
                return false;  // 如果有不相等的，返回 false
        }
        
        return true;  // 如果前后两部分都相等，说明链表是回文链表
    }
}

img

22.多数元素（简单）

img

1.排序法：

排序数组：
Arrays.sort(nums); 会对数组进行排序。排序后，数组中的元素会按从小到大的顺序排列。由于“多数元素”（出现次数大于 n/2）的数量比较大，它一定会出现在排序后数组的中间位置。

找出多数元素：
排序完成后，数组中间的元素（即索引为 n/2 的元素）就是多数元素。因为多数元素出现次数超过数组长度的一半，所以排序后的数组中，它必定会位于数组的中间位置。

例如：

  • 假设 nums = [3, 3, 3, 2, 2]，排序后为 [2, 2, 3, 3, 3]，可以看到 3 就是多数元素，因为它的出现次数大于 n/2。

使用位运算来获取数组的中间元素。位运算中的 >> 1 相当于对数组长度进行除以 2 的操作，并且结果会向下取整

高效访问：
nums[nums.length >> 1] 用位移操作代替了除法，计算出数组中间位置的元素，效率较高。这个操作等同于 nums.length / 2。

1
2
3
4
5
6
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length >> 1];
    }
}

2.摩尔投票法思路
摩尔投票法（Boyer-Moore Voting Algorithm）是一种用于在数组中寻找多数元素的高效算法。多数元素是指在数组中出现次数超过 ⌊n/2⌋ 次的元素。摩尔投票法的思路非常巧妙，下面我会详细讲解为什么这个算法能够正确地找出多数元素。

思路解释：

  1. 初始化候选人和票数：
    • cand_num：当前的候选人，初始化为数组的第一个元素 nums[0]。
    • count：票数，初始化为 1，表示当前候选人 cand_num 得到了 1 票。
  2. 遍历数组：
    • 对于数组中的每个元素 nums[i]，如果它和当前候选人 cand_num 相同，则为候选人增加一票，即 count++。
    • 如果它和候选人不同，则减去一票，即 count--。
  3. 调整候选人：
    • 如果 count 变为 0，表示当前候选人失去了对多数的支持，此时更换候选人，将新的候选人设置为 nums[i]，并且将 count 重置为 1。
  4. 最终答案：
    • 遍历结束后，cand_num 就是最终的多数元素。

img

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int majorityElement(int[] nums) {
        int cand_num = nums[0], count = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (cand_num == nums[i])
                ++count;
            else if (--count == 0) {
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;
    }
}

摩尔投票法通过票数的增减和候选人更换机制，确保在最后得到的候选人就是数组中的多数元素。这种方法非常高效，适用于找到一个在数组中出现次数超过 ⌊n/2⌋ 的元素，且其时间复杂度为 O(n)，空间复杂度为 O(1)。

23.环形链表（双向链表-简单）

img

快慢指针

想象兔子和乌龟在同一跑道上，一个速度快、另一个速度慢。如果跑道有环，兔子必然在一段时间后追上乌龟。对于链表来说，如果在链表中引入两个以不同速度（一个比另一个快一倍）前进的指针，在链表存在环的情况下，这两个指针必定会相遇。

注意：代码比较两个节点的时候，比较的是内存地址是否一致，并没有比较节点的 val。

问：兔子会不会「跳过」乌龟，从来不会和乌龟相遇呢？

答：这是不可能的。如果有环的话，那么兔子和乌龟都会进入环中。这时用「相对速度」思考，乌龟不动，兔子相对乌龟每次只走一步，这样就可以看出兔子一定会和乌龟相遇了。

问：为什么代码的 while 循环没有判断 slow 是否为空？

答：slow 在 fast 后面，如果 fast 不是空，那么 slow 也肯定不是空。好比快人先去探路，慢人走的都是快人走过的路。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head; // 乌龟和兔子同时从起点出发
        while (fast != null && fast.next != null) {
            slow = slow.next; // 乌龟走一步
            fast = fast.next.next; // 兔子走两步
            if (fast == slow) { // 兔子追上乌龟（套圈），说明有环
                return true;
            }
        }
        return false; // 访问到了链表末尾，无环
    }
}

24.将有序数组转换为二叉搜索树（二叉树-简单）

img

img

img

img

排序法

分析：BST 的中序遍历是升序的，因此本题等同于根据中序遍历的序列恢复二叉搜索树。因此我们可以以升序序列中的任一个元素作为根节点，以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树，这样得到的树就是一棵二叉搜索树啦～ 又因为本题要求高度平衡，因此我们需要选择升序序列的中间元素作为根节点

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }

    private TreeNode dfs(int[] nums, int lo, int hi) {
        if (lo > hi) return null;      // 空区间 ⇒ 空节点

        int mid = lo + (hi - lo) / 2;  // 取中点，避免 (lo+hi) 溢出
        TreeNode root = new TreeNode(nums[mid]);

        // 递归构建左右子树：左半段、右半段
        root.left  = dfs(nums, lo, mid - 1);
        root.right = dfs(nums, mid + 1, hi);
        return root;
    }
}

逐行说明

  • sortedArrayToBST：从整段 [0, n-1] 开始递归。
  • dfs(nums, lo, hi)：把 nums[lo..hi] 这段区间转成一棵 BST 并返回根节点。
  • 结束条件：lo > hi 代表子区间为空，返回 null。
  • 选根：mid 为中点，nums[mid] 做根。
  • 递归：左子树来自左半区间 [lo, mid-1]，右子树来自右半区间 [mid+1, hi]。

img

25.合并两个有序链表（简单-链表）

img

img

思路：每次在两个链表的头结点里选更小的那个作为新链表的头，然后把它的next指向“剩下部分的合并结果”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // 1) 递归终止：有一个链表空了，另一个就是结果
    if (list1 == null) return list2;
    if (list2 == null) return list1;

    // 2) 递归步骤：比较两个头结点
    if (list1.val < list2.val) {
        // 选list1的头当新头，把它的next接上“list1剩余部分 和 list2”的合并结果
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        // 否则选list2的头当新头
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

img

复杂度与特性

  • 时间复杂度：O(m+n)（每个节点访问一次）。
  • 空间复杂度：O(m+n)（递归调用栈的最大深度，最坏相当于两个表总长度）。
  • 代码不创建新节点，直接重用原链表节点，指针重排完成合并。

总结：取两条链表当前更小的头结点当“新头”，然后把它的尾巴和另一条链表继续递归（或迭代）合并。

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode mergeTwoListsIter(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0); // 哨兵头结点
    ListNode tail = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    // 拼上剩余的一条
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

img

循环结束时，肯定有一条链表先到头，另一条还有剩余（因为它们是升序，所以剩余部分直接接到新链表尾就行）。

用三元运算符简化了：

  • 如果 l1 不为空，接上 l1；
  • 否则接上 l2。

img

img

26.买卖股票的最佳时机（贪心-简单）

img

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int maxProfit(int[] prices) {
    //本题中需要3个变量
    //最低价格min price 当日价格 prices  最高利润 max profit
    //初始化最低价格为当日价格
    int minPrice = prices[0];
    //初始化最高利润为0
    int maxProfit = 0;
    //遍历价格列表prices
    for (int i = 0; i < prices.length; i++) {
        //如果当日价格小于最低价格，则更新最低价格为当日价格
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            //否则计算利润并更新最高利润
            int profit = prices[i] - minPrice;
            maxProfit = Math.max(profit, maxProfit);
        }
    }
    return maxProfit;
}

27.跳跃游戏（贪心-中等）

img

img

img

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
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canJump(int[] nums) {
        // if (nums.length == 1) return true;
        // if (nums[0] == 0) return false;
        int index = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--){
            if (i + nums[i] >= index) {
                index = i;
            }
        }
        return index == 0;
    }

这段代码是通过从后往前遍历的方式来判断是否能跳到数组的最后一个位置。它的核心思想是贪心算法，具体来说是通过追踪能跳到当前元素的最远位置，判断是否能够从初始位置跳到最后一个位置。

代码解读：

  1. 初始化

    ：

    • index 用来表示从最后一个位置开始，当前位置能跳到的最远位置。初始时，index = nums.length - 1，即从最后一个位置开始。

  2. 倒序遍历

    ：

    • 从倒数第二个位置（nums.length - 2）开始，依次向前遍历整个数组。
    • 对于每个位置 i，判断能否通过 i + nums[i]（当前位置 i 能跳到的最大位置）到达 index。
    • 如果可以到达，说明可以从这个位置跳到当前位置 index，因此更新 index 为当前位置 i。

  3. 判断是否能从起始位置跳到最后

    ：

    • 如果遍历结束后，index 变回了起始位置（index == 0），说明从头到尾能跳到最后一个位置，返回 true。
    • 否则，返回 false。

img

28.爬楼梯（动态规划-简单）

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int climbStairs(int n) {
        // 动态规划
        // 如果只有一级台阶，只有一种方法
        if(n == 1){
            return 1;
        }
        // 创建一个长度为n+1的数组dp，用于存储到达每级台阶的方法数
        int[] dp = new int[n+1];
        // 初始化第一级台阶的方法数为1
        dp[1] = 1;
        // 初始化第二级台阶的方法数为2
        dp[2] = 2;
        // 从第三级台阶开始，通过动态规划计算到达每级台阶的方法数
        for (int i = 3; i <= n ; i++) {
            // 到达第i级台阶的方法数等于到达第i-1级台阶的方法数加上到达第i-2级台阶的方法数
            dp[i] = dp[i-1]+dp[i-2];
        }
        // 返回到达第n级台阶的方法数
        return dp[n];
    }

29.合并区间（数组-中等）

img

给定若干个区间 [start, end]，要求合并所有有交集的区间，返回一个不重叠的新区间数组。

例子：
输入：[[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
因为 [1,3] 和 [2,6] 有交集，合并成 [1,6]。

代码核心思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (p, q) -> p[0] - q[0]); // 1. 按左端点排序
        List<int[]> ans = new ArrayList<>();
        for (int[] p : intervals) {
            int m = ans.size();
            if (m > 0 && p[0] <= ans.get(m - 1)[1]) { // 2. 能合并：有重叠
                ans.get(m - 1)[1] = Math.max(ans.get(m - 1)[1], p[1]); // 更新右端点
            } else { // 3. 不能合并：没有重叠
                ans.add(p); // 新建一个区间
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

img

示例运行过程

输入：[[1,3],[2,6],[8,10],[15,18]]

  1. 排序后：[[1,3],[2,6],[8,10],[15,18]]

  2. 初始：ans = [[1,3]]

  3. 遍历 

    1
    [2,6]

    ：

    • 2 <= 3 → 可以合并，更新右端点：ans = [[1,6]]

  4. 遍历 

    1
    [8,10]

    ：

    • 8 > 6 → 无法合并，新建区间：ans = [[1,6],[8,10]]

  5. 遍历 

    1
    [15,18]

    ：

    • 15 > 10 → 无法合并，新建区间：ans = [[1,6],[8,10],[15,18]]

最终结果：[[1,6],[8,10],[15,18]]

总结：
这段代码的思路就是 “先排序，再贪心合并”。

  • 排序确保区间的合并只可能发生在相邻区间；
  • 遍历时用条件判断是否重叠，能合并就更新右端点，否则就新建一个区间。

30.三数之和（双指针 中等）

img

思路:数组遍历核心想法：
先固定一个数 nums[i]，把问题变成在它右侧找一对数，使得两数和等于 -nums[i]。因为排过序，用左右指针就能在线性时间里完成这一对数的查找；再配合去重，就能得到不重复的三元组。

如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
时间复杂度：O(n2)，n 为数组长度

img

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
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;// ④ 在 (i, len-1] 区间找两数和 = -nums[i]
            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++; // ⑧ 和太小：右移L让和变大（数组有序）
                else if (sum > 0) R--;// ⑨ 和太大：左移R让和变小
            }
        }        
        return ans;
    }

img

img

为什么这些去重是充分且必要的？

  • 外层去重：同一个基准 nums[i] 会引出完全相同的一批三元组（因为右侧的候选区间和数值都一样），必须跳过。
  • 内层去重（L、R）：在固定 i 的情况下，如果 nums[L] 与下一个相等，或者 nums[R] 与前一个相等，继续用它们会得到完全相同的三元组，所以要把这些重复值一次性跨过去。

小例子走一遍

1
2
nums = [-1, 0, 1, 2, -1, -4]`
排序：`[-4, -1, -1, 0, 1, 2]

  • i=0(-4): 目标两数和 +4，双指针找不到，结束。

  • i=1(-1)

    • L=2(-1), R=5(2) → sum=0，收录 [-1,-1,2]，跳过重复，L→3, R→4
    • L=3(0), R=4(1) → sum=0，收录 [-1,0,1]，L→4, R→3 结束本轮

  • i=2(-1)：等于前一个，外层去重跳过。

  • 后续最小值 ≥ 0，外层终止。
    结果：[[-1,-1,2], [-1,0,1]]

31.最长连续序列（哈希 中等）

img

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
public int longestConsecutive(int[] nums) {
        // 使用HashSet存储数组中的所有元素
        HashSet<Integer>nums_set = new HashSet<>();
        for (int num : nums) {
            nums_set.add(num);
        }
        // 初始化最长连续序列的长度为0
        int  longestStreak = 0;
        for (int num : nums_set) {
            // 如果当前数字的前一个数字不在HashSet中，则开始计算以当前数字为首的最长连续序列长度
            if (!nums_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                while (nums_set.contains(currentNum + 1)) {
                    // 当前数字的后一个数字在HashSet中
                    currentNum += 1;
                    // 最长连续序列长度加一
                    currentStreak += 1;
                }
                // 更新最长连续序列的长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }
        return longestStreak;
    }

排序法

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
public int longestConsecutive(int[] nums) {
      //如果数组为空，则返回0
      if (nums.length == 0) {
          return 0;
      }
      //对数组进行排序
      Arrays.sort(nums);
      //初始化条件，max为最终求的最长连续序列的长度，curr_len为当前连续序列的长度,last_num为上一个数
      int max = 1;
      int curr_len = 1;
      int last_num = nums[0];
      //遍历数组
      for (int i = 1; i < nums.length; i++) {
          //如果当前数与上一个数相等，则不做处理
          if (nums[i] == last_num) {
              continue;
          }
          //如果当前数与上一个数相差1，则说明是连续的
          if (nums[i] - last_num == 1) {
              curr_len++;
          }
          //如果当前数与上一个数相差大于1，则说明不是连续的
          else {
              //更新最长连续序列的长度
              max = Math.max(curr_len, max);
              //重置当前连续序列的长度
              curr_len = 1;

          }
          //更新上一个数
          last_num = nums[i];
      }
      return Math.max(curr_len, max);
  }

32.验证二叉搜索树(二叉树-中等)

img

二叉搜索树（BST）的性质：

  1. 左子树的所有节点都必须小于当前节点的值。
  2. 右子树的所有节点都必须大于当前节点的值。
  3. 左右子树分别也是二叉搜索树。

思路：

通过递归遍历树的每个节点，检查该节点是否满足 BST 的条件，具体做法是使用一个递归方法，带有两个参数 minVal 和 maxVal 来限制当前节点的有效值范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 public boolean isValidBST(TreeNode root) {
                //这是入口方法，直接调用递归函数 isValidBST。在调用时，我们传递了整个树的根节点 root，并将它的有效值范围设为 Long.MIN_VALUE 到 Long.MAX_VALUE，表示初始时没有任何限制。
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

    }
    private boolean isValidBST(TreeNode node, long minVal, long maxVal) {
        if (node == null) {
//递归基础条件：如果当前节点是 null，就返回 true，因为空节点没有违反 BST 的性质。
            return true;
        }
        //当节点小于最小值或者大于最大值时，不是二叉搜索树
       //左子树节点必须小于当前节点的值。右子树节点必须大于当前节点的值。
        if (node.val <= minVal || node.val >= maxVal) {
            return false;
        }
 
        return isValidBST(node.left, minVal, node.val) && isValidBST(node.right, node.val, maxVal);
    }
  return isValidBST(node.left, minVal, node.val) && isValidBST(node.right, node.val, maxVal);

递归调用：递归地检查左子树和右子树：

  • 对左子树：node.val 作为新的最大值，minVal 保持不变。
  • 对右子树：node.val 作为新的最小值，maxVal 保持不变。

左右子树的每个节点都需要满足其父节点的上下界条件，因此通过递归传递上下界进行逐个验证。

img

法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
class Solution {
    private long pre = Long.MIN_VALUE; // ① 预存当前节点值，用于比较

    public boolean isValidBST(TreeNode root) {
        if (root == null) {  // ② 递归结束条件：空节点
            return true;
        }

        // 递归遍历左子树
        if (!isValidBST(root.left)) {  
            return false;  // 左子树验证失败，返回 false
        }

        // 检查当前节点值是否大于上一个访问节点的值
        if (root.val <= pre) {  // ③ 中序遍历顺序保证当前节点值应该大于上一个节点
            return false;  // 当前节点不符合 BST 的要求
        }
        
        pre = root.val;  // 更新上一个访问的节点值为当前节点

        // 递归遍历右子树
        return isValidBST(root.right);
    }
}

img

定义一个 pre 变量：

  • 变量 pre 用来存储上一个访问的节点的值。我们将它初始化为 Long.MIN_VALUE，这是为了保证第一个节点值可以通过第一个比较。

递归遍历树：

  • 通过递归先遍历左子树，然后检查当前节点值是否大于上一个访问节点的值（即 pre），最后遍历右子树。

左子树的递归：

  • 调用 isValidBST(root.left)，如果左子树不符合条件，直接返回 false，不再继续检查。

中序遍历验证：

  • 对每个节点来说，若当前节点值 root.val 不大于前一个节点值 pre，则说明它违反了二叉搜索树的定义，返回 false。

更新 pre：

  • 每次访问一个节点之后，将 pre 更新为当前节点的值，为下一个节点做准备。

右子树的递归：

  • 在检查完当前节点之后，递归检查右子树。

为什么这样做有效？

  • 在二叉搜索树中，所有左子树节点的值应该小于父节点的值，所有右子树节点的值应该大于父节点的值。
  • 使用中序遍历时，节点值应该按升序排列，因此如果遍历过程中发现当前节点值不大于 pre（即之前访问的节点的值），就说明违反了 BST 的性质。

img

33.轮转数组（数组 中等）

img

思路：

img

  1. 一般化

如果 k >= n（n 是数组长度），实际上向右轮转 k 步等价于轮转 k % n 步。
比如数组长度 7，向右轮转 10 步，等价于轮转 10 % 7 = 3 步。

  1. 分块思想（把数组拆成 A+B）

设数组 nums = A + B：

  • A = nums[0..n-k-1]（前 n−k 个数）
  • B = nums[n-k..n-1]（后 k 个数）

目标：把数组从 A+B 变成 B+A。

例如：
nums = [1,2,3,4,5,6,7], k=3

  • A = [1,2,3,4]
  • B = [5,6,7]
    目标：[5,6,7,1,2,3,4]
  • 三次反转法（核心技巧）

利用数组反转操作，可以把 A+B 变成 B+A：

  1. 整体反转：得到 

    1
    rev(B) + rev(A)
    • [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]

  2. 反转前 k 个（rev(B))：得到 

    1
    B + rev(A)
    • [7,6,5,4,3,2,1] → [5,6,7,4,3,2,1]

  3. 反转后 n−k 个（rev(A))：得到 

    1
    B + A
    • [5,6,7,4,3,2,1] → [5,6,7,1,2,3,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
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; // 避免 k >= n 的情况

        // 1. 反转整个数组
        reverse(nums, 0, n - 1);

        // 2. 反转前 k 个元素
        reverse(nums, 0, k - 1);

        // 3. 反转后 n-k 个元素
        reverse(nums, k, n - 1);
    }

    // 工具函数：反转数组的一部分
    private void reverse(int[] nums, int start, int end) {
        while (i < j) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            i++;
            j--;
        }
    }
}

34.除自身以外数组的乘积（数组 中等）

img

思路

对每个位置 i，答案是：

answer[i] = (i 左边所有数的乘积) * (i 右边所有数的乘积)

  • 先从左到右一趟：用累乘 left 记录“到当前为止左边所有数的乘积”，把它写进 answer[i]，再把 nums[i] 乘进 left。
  • 再从右到左一趟：用累乘 right 记录“到当前为止右边所有数的乘积”，让 answer[i] *= right，再把 nums[i] 乘进 right。

这样 answer[i] 最终就是“左乘积 × 右乘积”。
这个做法自然处理 0 的情况，不需要特判。

例子（[1,2,3,4]）

  • 左扫写入：answer = [1,1*1,1*2,1*2*3] = [1,1,2,6]
  • 右扫乘上：从右到左，right 依次为 1,4,12,24
    得到 answer = [24,12,8,6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[]answer = new int[n];
        //answer[i] = (i 左边所有数的乘积) * (i 右边所有数的乘积)
        //左侧乘积
        int left = 1;
        for(int i = 0;i<n;i++){
            answer[i]=left;//先把当前左乘积存到结果数组中
            left=nums[i]*left;
        }
        //右侧乘积
        int right = 1;
        for(int i =n-1;i>=0;i--){
            answer[i]=answer[i]*right;//在已有的L[i]R[i]
            right=right*nums[i];//把nums[i]累进right，供左边那个位置用
        }
        return answer;
    }

img

img

img

35.删除链表的倒数第N个结点（中等 链表）

img

思路

  • 建一个 dummy 指向头结点，方便删除头结点这种边界。
  • 让 fast 先走 n 步，然后 fast 和 slow 一起走，直到 fast 到尾部（null）。
  • 此时 slow 正好停在“待删节点的前一个”位置，执行 slow.next = slow.next.next 即可。
  • 返回 dummy.next。
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
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 1) 哑结点：统一边界（尤其删除头结点时）
        ListNode dummy = new ListNode(0, head);

        // 2) 两个指针都从 dummy 出发
        ListNode fast = dummy, slow = dummy;

        //     // 3) fast 先走 n+1 步，保证 fast 与 slow 相隔 n+1 个“结点距离”
        //    这样当 fast 走到 null 时，slow 正好停在“待删结点的前一个”

              for (int i = 0; i < n + 1; i++) {
            fast = fast.next;
        }

        // 4) fast、slow 同步前进，直到 fast 走到链表末尾(null)
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 5) 删除 slow 后面的那个结点（即倒数第 n 个）
        slow.next = slow.next.next;

        // 6) 返回新头结点（可能头结点被删了，所以不能直接返回 head）
        return dummy.next;
    }
}

img

img

img

36.环形链表II（中等 链表）

img

思路：

题核心：快慢指针 (Floyd 判圈算法)

这题用的就是“快慢指针 + 数学推导”。

第一步：判断是否有环（快慢指针第一次相遇）

  • 用两个指针：
    • slow 每次走 1 步
    • fast 每次走 2 步

情况：

  1. 如果 fast 或 fast.next 先变成 null，说明链表走到头了 → 无环，直接返回 null。
  2. 如果链表有环，fast 一定会追上 slow，两者会在环中第一次相遇。

第二步：推导数学关系

设：

  • a = 从链表头到环入口的长度
  • b = 环的长度
  • s = 慢指针走的步数
  • f = 快指针走的步数

相遇时：

  1. f = 2s （快指针走的步数是慢指针的 2 倍）
  2. f = s + nb （快指针比慢指针多走了 n 圈环）

联立可得：

1
2
2s = s + nb
=> s = nb

也就是说：慢指针走的步数 刚好是 n 圈环的长度。

第三步：如何找到环入口？

  • 从链表头到入口需要走 a + nb 步（先走 a 步到入口，再绕 n 圈）。
  • 而此时 slow 已经走了 nb 步，只差 a 步就到入口。

所以：

  • 让一个新指针 fast 从头开始走（0 步开始）。
  • 同时让 slow 继续走。
  • 他们每次都走 1 步。
  • 走了 a 步时，两者会相遇在入口节点。

概括一下：

根据：

  1. f=2s （快指针每次2步，路程刚好2倍）
  2. f = s + nb (相遇时，刚好多走了n圈）

推出：s = nb

从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。

如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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; // fast回到头
    while (slow != fast) {
        slow = slow.next; // 两者一起走
        fast = fast.next;
    }
    return fast; // 相遇点就是入口
}

img

img

37.最小栈（中等 栈）

img

常规做法辅助栈

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
//两个栈，一个普通栈存储所有元素，另一个辅助栈存储最小值
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack() {
        //初始化
        minStack = new Stack<>();
        stack = new Stack<>();
    }
    //入栈操作，同时更新辅助栈的最小值
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    //出栈操作，同时更新辅助栈的最小值
    public void pop() {
        //如果栈顶元素是最小值，则辅助栈也出栈
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }
    //获取栈顶元素
    public int top() {
        return stack.peek();
    }
    //获取栈中的最小值
    public int getMin() {
        return minStack.peek();
    }

38.二叉树搜索树中第K小的元素（中等 二叉树）

img

思路：中序遍历->保证得到的是有序数组，直接返回的第k个元素即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int kthSmallest(TreeNode root, int k) {
        // 中序遍历二叉搜索树，得到有序数组->中序遍历后可以得到有序数组，直接返回第 k 个元素即可
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        // 返回第 k 个元素
        return list.get(k - 1);
    }
    // 中序遍历二叉搜索树
    private void inorder(TreeNode root, List<Integer> list) {
        // 递归终止条件
        if (root == null) return;
        // 中序遍历二叉搜索树左子树
        inorder(root.left, list);
        // 将根节点的值加入到列表中
        list.add(root.val);
        // 中序遍历二叉搜索树右子树
        inorder(root.right, list);
    }

优化代码

为求第 k 个节点，需要实现以下三项工作：

递归遍历时计数，统计当前节点的序号。
递归到第 k 个节点时，应记录结果 res 。
记录结果后，后续的遍历即失去意义，应提前返回。

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 {
    int res, k;

    void dfs(TreeNode root) {
        if (root == null) return;

        // 1) 递归左子树
        dfs(root.left);

        // 2) 访问当前节点
        if (k == 0) return;        // 已找到结果，后面不用再遍历
        if (--k == 0) res = root.val; // 第 k 次访问到结点时，记录答案

        // 3) 递归右子树
        dfs(root.right);
    }

    public int kthSmallest(TreeNode root, int k) {
        this.k = k;   // 把目标 k 存为类变量
        dfs(root);
        return res;
    }
}

img

img

2版代码效率的对比

img

39.字符串解码（中等 栈）

img

题目给的字符串是编码过的，像 "3[a2[c]]"，规则是 数字 + [字符串] 表示重复。例如：

  • 3[a] → aaa
  • 2[bc] → bcbc
  • "3[a2[c]]" → accaccacc

而这个嵌套是递归/栈结构的，非常适合用 栈 来解析。

算法流程：

  • 构建辅助栈 stack， 遍历字符串 s 中每个字符 c；
    • 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
    • 当 c 为字母时，在 res 尾部添加 c；
    • 当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 0：
      • 记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作；
      • 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × […] 字符串。
      • 进入到新 [ 后，res 和 multi 重新记录。
    • 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中:
      • last_res是上个 [ 到当前 [ 的字符串，例如 “3[a2[c]]” 中的 a；
      • cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 “3[a2[c]]” 中的 2。
  • 返回字符串 res。

img

img

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 String decodeString(String s) {
        StringBuilder res = new StringBuilder();       // 当前的临时结果
        int multi = 0;                                 // 当前的倍数
        LinkedList<Integer> stack_multi = new LinkedList<>(); // 倍数栈
        LinkedList<String> stack_res = new LinkedList<>();    // 结果栈

        for (char c : s.toCharArray()) {
            if (c == '[') {
                // 保存现场
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                // 重置
                multi = 0;
                res = new StringBuilder();
            }
            else if (c == ']') {
                // 取出倍数和上一个结果
                int cur_multi = stack_multi.removeLast();
                StringBuilder tmp = new StringBuilder();
                for (int i = 0; i < cur_multi; i++) tmp.append(res);
                // 拼接结果
                res = new StringBuilder(stack_res.removeLast() + tmp);
            }
            else if (Character.isDigit(c)) {
                // 累计 multi，考虑多位数
                multi = multi * 10 + (c - '0');
            }
            else {
                // 普通字母，加入结果
                res.append(c);
            }
        }
        return res.toString();
    }
}

img

初始 → multi=3 → 入栈(3,””) → res=”a” → multi=2
→ 入栈(2,”a”) → res=”c” → 出栈生成 “acc”
→ 出栈生成 “accaccacc” → 完成

这道题的核心是 栈保存现场，遇到 [ 压栈，遇到 ] 出栈并拼接。
代码里 stack_multi 管数字，stack_res 管字符串；而 multi 和 res 都会在进入新括号时被重置。

40.排序链表（中等 链表）

img

思路：

链表排序不能像数组一样直接用下标访问，因此常用 归并排序 (Merge Sort)，它既能保证 O(n log n) 的时间复杂度，又能很好地在链表上实现。

为什么不用快排？

快排在数组中更高效，因为数组可以随机访问。但链表没有随机访问能力，快排需要频繁“跳来跳去”，会让效率大幅下降。而归并排序只依赖 顺序访问，非常适合链表。

算法流程

归并排序有两步：

  1. 分割链表（Divide）用 快慢指针找链表中点，把链表一分为二。

    • 快指针每次走两步，慢指针每次走一步。
  • 当快指针到达末尾，慢指针正好在中点。
    • 断开链表，得到两个子链表。

  1. 合并链表（Merge）对左右两个子链表递归排序，然后合并成有序链表。

    • 合并操作类似 归并两个有序数组。
  • 每次取两个链表头中较小的节点接入新链表

关键点

  • 递归终止条件：当链表为空或只有一个节点时，直接返回。
  • 时间复杂度：分割需要 O(log n)，合并需要 O(n)，整体是 O(n log n)。
  • 空间复杂度：由于递归栈，严格来说是 O(log n)，但题目要求的“常数空间”一般是指不允许额外开辟数组，链表归并是被接受的。

img

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
class Solution {
public ListNode sortList(ListNode head) {
// 1) 递归终止：空或单节点天然有序
if (head == null || head.next == null) return head;    
// 2) 快慢指针找中点（fast 从 head.next 起步）
    ListNode fast = head.next, slow = head, prev = null;
    while (fast != null && fast.next != null) {
        slow = slow.next;         // 慢走一步
        fast = fast.next.next;    // 快走两步
    }

    // 3) 断开成两段 [head..slow] 和 [slow.next..]
    ListNode mid = slow.next;
    slow.next = null;

    // 4) 分治：分别对左右两段排序
    ListNode left  = sortList(head);
    ListNode right = sortList(mid);

    // 5) 归并：合并两个有序链表
    ListNode dummy = new ListNode(0), cur = dummy;
    while (left != null && right != null) {
        if (left.val < right.val) {      // 注意：这里“严格小于”
            cur.next = left;  left = left.next;
        } else {
            cur.next = right; right = right.next;
        }
        cur = cur.next;
    }
    cur.next = (left != null) ? left : right;  // 拼上剩余
    return dummy.next;
 }
}

1) 递归终止

  • head == null || head.next == null：0 或 1 个节点不需要再排，直接返回。

  • 找中点（分割用）

  • 用 快慢指针：slow 每次走 1，fast 每次走 2。

  • 令 fast从head.next 起步，有两个效果：

    • 偶数长度时，slow 会停在“左中点”（更适合把链表切成近似等长的两半）；
    • 让循环条件更简洁，不会越界。

  • 循环结束后，slow 指向左半段的尾。用 mid = slow.next 记录右半段开头，再把 slow.next = null 断开链表，形成两段。

  • 分治递归

  • 对左右两段分别 sortList，直到被切成单节点（天然有序）。

  • 合并两个有序链表

  • 这一步与「合并两个有序链表-25」题一模一样：

    • 用一个 dummy 作为新链的假头，cur 向后推进；
    • 每次取两段头结点中更小的挂到 cur.next，然后对应段指针后移；
    • 某一段空了，直接把另一段剩余整体接上；
    • 返回 dummy.next 即为合并结果。
  • 稳定性：因为条件写的是 left.val < right.val（严格小于），当相等时会取 right，这在“相等元素按原相对次序”这个意义上并不稳定。如果你需要稳定排序，把比较改成 <= 让左侧先出即可。

41.二叉树展开为链表(中等 链表)

img

题目本质是：把每个节点的左子树搬到右边，并把原来的右子树挂在左子树的最右节点后面。
这样不断往下处理，最后就变成了单链表。

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
    1
   / \
  2   5
 / \   \
3   4   6

//将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6        
//将原来的右子树接到左子树的最右边节点
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 //将 2 的左子树插入到右子树的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 //将原来的右子树接到左子树的最右边节点
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6  
    class Solution {
    public void flatten(TreeNode root) {
        while (root != null) {
            if (root.left != null) {
                // 找到左子树的最右节点
                TreeNode pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                // 原右子树接到左子树最右节点
                pre.right = root.right;
                // 左子树移到右边
                root.right = root.left;
                root.left = null;
            }
            // 处理下一个节点
            root = root.right;
        }
    }
}

这题利用 原地修改指针 的方式，把左子树插到右边，并把原右子树接到左子树最右节点后面，逐层推进，最后自然变成右链表。

42.两两交换链表中的节点（中等 链表）

img

1
2
3
4
5
6
7
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) return head; // 递归终止
    ListNode next = head.next; // 下一个节点
    head.next = swapPairs(next.next); // 递归交换后续链表
    next.next = head; // 完成这两个节点的交换
    return next; // 返回新头节点
}

初始输入：1 -> 2 -> 3 -> 4

Step 1：处理 head=1

  • next = 2
  • 递归调用：head.next = swapPairs(3)
    • 此时递归还没返回，继续往下走。

Step 2：处理 head=3

  • next = 4
  • 递归调用：head.next = swapPairs(null)
    • 进入递归终止条件，直接返回 null。
  • 回来后：
    • head=3, next=4
    • 交换：4 -> 3 -> null
    • 返回新头 4

Step 3：回到 Step 1

  • head=1, next=2
  • 此时 swapPairs(3) 已经返回了链表 4 -> 3
  • 连接：1 -> (4 -> 3)
  • 再交换：2 -> 1 -> 4 -> 3
  • 返回新头 2

最终结果

链表变为：2 -> 1 -> 4 -> 3

我们用 递归调用栈图 来一步步演示 swapPairs 的执行过程，输入链表是 1 -> 2 -> 3 -> 4。

初始调用

1
swapPairs(1)
  • head = 1
  • next = 2
  • 调用：head.next = swapPairs(3)

栈展开过程（入栈）

  1. 调用 swapPairs(1) 等待 swapPairs(3) 的结果 栈状态： swapPairs(1) [挂起，等待 swapPairs(3)]
  2. 调用 swapPairs(3) 等待 swapPairs(null) 的结果 栈状态： swapPairs(1) swapPairs(3) [挂起，等待 swapPairs(null)]
  3. 调用 swapPairs(null) 进入终止条件，返回 null 栈状态： swapPairs(1) swapPairs(3) [准备出栈]

栈回溯过程（出栈）

  1. 处理 swapPairs(3)

    • head=3, next=4
    • head.next = swapPairs(null) = null
    • 交换：4 -> 3 -> null
    • 返回新头 4 栈状态：

    swapPairs(1) [收到结果链表 4 -> 3]

  2. 处理 swapPairs(1)

    • head=1, next=2
    • head.next = swapPairs(3) 已返回 4 -> 3
    • 拼接：1 -> (4 -> 3)
    • 交换：2 -> 1 -> 4 -> 3
    • 返回新头 2 栈清空。

最终结果

链表被交换为：

1
2 -> 1 -> 4 -> 3

总结图（调用栈）

swapPairs(1)
└─ swapPairs(3)
└─ swapPairs(null) → 返回 null
└─ 处理 (3,4) → 返回 4->3
└─ 处理 (1,2)，接上 [4->3] → 返回 2->1->4->3

✅ 这样你可以看到，递归是 先递到最深处（3,4）交换，再一层层往上拼接结果的。

43.全排列（中等 回溯）

img

回溯法：回溯法 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

找到一个可能存在的正确的答案；
在尝试了所有可能的分步方法后宣告该问题没有答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//全排列：给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>(); // 收集所有排列
        List<Integer> path = new ArrayList<>();      // 当前构造中的“路径/前缀”
        backtrack(nums, res, path);                  // 递归搜索
        return res;
    }

    // 回溯算法
    private void backtrack(int[] nums, List<List<Integer>> res, List<Integer> path) {
        if (path.size() == nums.length) {            // ✨ 终止：选满 n 个
            res.add(new ArrayList<>(path));          // 必须拷贝一份
            return;
        }
        for (int i = 0; i < nums.length; i++) {      // 枚举下一位的选择
            if (path.contains(nums[i])) continue;    // 这个数用过了，跳过
            path.add(nums[i]);                       // 做选择
            backtrack(nums, res, path);              // 递归
            path.remove(path.size() - 1);            // 撤销选择（回溯）
        }
    }
}

img

path=[]
├─ 选1 → path=[1]
│ ├─ 选2 → path=[1,2]
│ │ └─ 选3 → path=[1,2,3] → 收集 [1,2,3] 回退到 [1,2]
│ └─ 选3 → path=[1,3]
│ └─ 选2 → path=[1,3,2] → 收集 [1,3,2] 回退到 []
├─ 选2 → path=[2]
│ ├─ 选1 → path=[2,1]
│ │ └─ 选3 → path=[2,1,3] → 收集 [2,1,3]
│ └─ 选3 → path=[2,3]
│ └─ 选1 → path=[2,3,1] → 收集 [2,3,1]
└─ 选3 → path=[3]
├─ 选1 → path=[3,1]
│ └─ 选2 → path=[3,1,2] → 收集 [3,1,2]
└─ 选2 → path=[3,2]
└─ 选1 → path=[3,2,1] → 收集 [3,2,1]

回溯的关键就是“出栈时撤销”：path.remove(path.size()-1)，把本层的选择拿掉，返回上一层继续尝试其他分支。

复杂度

  • 本质上有 n! 个排列。每产生一个排列要做 O(n) 的复制工作。
  • 你的写法还用到了 path.contains(nums[i])（每次 O(n) 查找）。
  • 综合下来：时间复杂度 ≈ O(n · n! + n · n · n!) = O(n² · n!)
    （如果改成 boolean[] used，则查询是否使用过为 O(1)，整体降为 O(n · n!)。）
  • 空间复杂度：递归深度 n，path 长度 n，所以 O(n)（不计输出）。

可优化点-用 boolean[] used 替代 path.contains

contains 每次线性扫描，成本高；used[i] O(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 {
    List<List<Integer>> res = new ArrayList<>(); // 收集所有排列
    boolean[] used;  
    public List<List<Integer>> permute(int[] nums) {
        List<Integer> path = new ArrayList<>();// 当前构造中的“路径/前缀”
        //初始化used数组
        used = new boolean[nums.length];
        backtrack(nums, path);// 递归搜索
        return res;
    }

    //回溯算法
    private void backtrack(int[] nums, List<Integer> path) {
        if (path.size() == nums.length) {            // ✨ 终止：选满 n 个
            res.add(new ArrayList<>(path));          // 必须拷贝一份
            return;
        }

        //递归数组
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;//这个数用过了，跳过
            used[i] = true;//标记为已使用
            path.add(nums[i]);                       // 做选择
            backtrack(nums, path);              // 递归
            path.remove(path.size() - 1);            // 撤销选择（回溯）
            used[i] = false;
        }
    }      
}

44.子集（中等 回溯）

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
List<List<Integer>> res = new ArrayList<>(); // 收集所有排列
List<Integer> path = new ArrayList<>();// 当前构造中的“路径/前缀”
public List<List<Integer>> subsets(int[] nums) {


        backtrack(nums, 0);// 递归搜索
        return res;
    }

    //回溯算法
    private void backtrack(int[] nums, int startIndex) {
      //每个节点都是一个子集
      res.add(new ArrayList<>(path));          // 必须拷贝一份
      //递归数组
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);                       // 做选择
            backtrack(nums, i+1);              // 递归
            path.remove(path.size() - 1);            // 撤销选择（回溯）

        }
    }

45.二叉树的右视图（中等 二叉树）

img

img

右视图就是从右边看二叉树，能看到的每一层最右边的节点。
换句话说，对于二叉树的每一层，我们只需要记录 该层第一个访问到的节点（从右往左遍历时）。

  1. 主函数入口
  • 如果 root == null，直接返回空结果。
  • 否则创建 res 保存右视图结果。
  • 调用 dfs(root, 0, res)，从深度 0 开始递归。
  • 递归函数 dfs

递归遍历的顺序：
优先右子树，再遍历左子树。
这样保证每一层的第一个节点，必然是该层最右边的节点。

参数：

  • node 当前节点
  • depth 当前节点所在的层数
  • res 结果集

逻辑：

  1. 终止条件：node == null，直接返回。

  2. 记录条件：如果 depth == res.size()，说明这是第一次到达该层，把当前节点的值加入结果集。

    • 比如深度 0 时，结果集是空的，说明第一次到达第 0 层，就记录根节点值。
    • 深度 1 时，如果结果集长度还是 1，说明这是第一次到达第 1 层，就记录该节点。

  3. 递归：

    • 先递归右子树 dfs(node.right, depth + 1, res)。
  • 再递归左子树 dfs(node.left, depth + 1, res)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> rightSideView(TreeNode root) { 
    if(root == null) return new ArrayList<>();
    List<Integer> res = new ArrayList<>();
    dfs(root, 0, res);
    return res;
}

private void dfs(TreeNode node, int depth, List<Integer> res) {
    if (node == null) return;
    // 只有第一次到达某一层时，才记录该层的节点值
    if (depth == res.size()) {
        res.add(node.val);
    }
    dfs(node.right, depth + 1, res);
    dfs(node.left, depth + 1, res);
}

img

46随机链表的复制（中等 链表）

img

img

这道题是什么意思？

节点的结构

每个节点有三个属性：

  1. val：节点的值。
  2. next：指向下一个节点。
  3. random：随机指针，可以指向链表中的任意一个节点，甚至是 null。

换句话说，random 不是像 next 那样固定指向下一个节点，而是一个“随意的引用”，可能指向：

  • 前面的某个节点
  • 后面的某个节点
  • 自己
  • null

题目的要求

给你这样一个带有 随机指针 的链表，要求你深拷贝它。

深拷贝的含义：

  • 你要创建一个全新的链表，新链表的节点和原链表一一对应。
  • 每个新节点的 val 和原节点相同。
  • 新节点的 next 和 random 指针，也要正确地指向新链表中的节点（而不是老链表中的节点）。
  • 不能只是简单拷贝引用，否则新链表的 random 可能会指回旧链表。

img

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
public Node copyRandomList(Node head) {
    if (head == null) return null;

    // ① 在每个原节点后插入克隆节点
    Node cur = head;
    while (cur != null) {
        Node clone = new Node(cur.val);
        clone.next = cur.next;
        cur.next = clone;
        cur = clone.next;
    }

    // ② 利用“克隆紧挨原节点”的结构复制 random
    cur = head;
    while (cur != null) {
        if (cur.random != null) {
            cur.next.random = cur.random.next;
        }
        cur = cur.next.next;
    }

    // ③ 拆分：还原原链表 + 抽出克隆链表
    cur = head;
    Node cloneHead = cur.next;
    while (cur != null) {
        Node next = cur.next;          // next 是克隆节点
        cur.next = next.next;          // 原节点跳过克隆，连回原链
        if (next.next != null) {
            next.next = next.next.next; // 克隆节点指向下一个克隆
        }
        cur = cur.next;                // 前进到下一个原节点
    }
    return cloneHead;
}

插入克隆节点

img

所有克隆节点都插入成功

img

img

2.利用克隆节点紧挨原节点的结构复制random

img

3.拆分出原链和克隆链

img

47.LRU缓存（中等 链表）

img

img

手写双向链表

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class LRUCache {
    //定义节点信息，每一个节点都包含key,value,prev,next四个属性
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    //定义容量，双向链表头尾哨兵节点，哈希表
    private final int capacity;
    // 哑结点：初始 self-loop，方便统一增删
    private final Node dummy = new Node(0,0);
    // 哈希表：key -> 节点，方便快速定位到节点
    private final HashMap<Integer, Node> map = new HashMap<>();


    /**
     * 以 正整数 作为容量 capacity 初始化 LRU 缓存
     * @param capacity
     */
    public LRUCache(int capacity) {

        this.capacity = capacity;
        dummy.next = dummy;
        dummy.prev = dummy;
    }

    /**
     * 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
     * @param key
     * @return
     */
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        // 访问后变为最近使用：移到表头
        moveToHead(node);
        return node.value;
    }

    /**
     * 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。
     * 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            // 已存在：更新值 + 移到表头
            node.value = value;
            moveToHead(node);
        } else {
            // 不存在：新建节点，挂到表头
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);
            // 若超容量：删除尾部最久未使用节点
            if (map.size() > capacity) {
                Node tail = removeTail();
                map.remove(tail.key);
            }
        }
    }

    //删除节点
    /* ---------- 双向链表工具方法 ---------- */

    // 从链表中摘除 node
    private void unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        // 可选：帮助 GC
        // node.prev = node.next = null;
    }

    // 把 node 插到 dummy 之后（表头）
    private void addToHead(Node node) {
        node.next = dummy.next;
        node.prev = dummy;
        dummy.next.prev = node;
        dummy.next = node;
    }

    // 将 node 移到表头
    private void moveToHead(Node node) {
        unlink(node);
        addToHead(node);
    }

    // 移除尾部真实节点（dummy.prev），并返回它
    private Node removeTail() {
        Node tail = dummy.prev;
        unlink(tail);
        return tail;
    }
}

法2:用了 Java 内置的 LinkedHashMap 来实现 LRU，其实是利用了它的 插入顺序有序 这一特性。整体逻辑比手写链表 + HashMap 要简单很多

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
class LRUCache {
    private final int capacity;
    private final Map<Integer, Integer> cache = new LinkedHashMap<>(); // 内置 LRU

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        // 删除 key，并利用返回值判断 key 是否在 cache 中
        Integer value = cache.remove(key);
        if (value != null) { // key 在 cache 中
            cache.put(key, value);
            return value;
        }
        // key 不在 cache 中
        return -1;
    }

    public void put(int key, int value) {
        // 删除 key，并利用返回值判断 key 是否在 cache 中
        if (cache.remove(key) != null) { // key 在 cache 中
            cache.put(key, value);
            return;
        }
        // key 不在 cache 中，那么就把 key 插入 cache，插入前判断 cache 是否满了
        if (cache.size() == capacity) { // cache 满了
            Integer eldestKey = cache.keySet().iterator().next();
            cache.remove(eldestKey); // 移除最久未使用 key
        }
        cache.put(key, value);
    }
}

48.电话号码的字母组合（中等 链表）

img

  • 处理空串：直接返回空列表。
  • 用一个映射表存 2..9 → 字母。
  • 回溯函数参数常见写法：pos 当前处理到的数字索引，path 当前已拼的字符。
  • 对 digits[pos] 对应的每个字母尝试一次，递归到下一位；回退时删掉刚加的字母。
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 static final String[] LETTERS = {
            "",    // 0
            "",    // 1
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs",// 7
            "tuv", // 8
            "wxyz" // 9
    };

    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();// 存放结果
        if (digits == null || digits.length() == 0) return ans;
        StringBuilder path = new StringBuilder();
        backtrack(ans, path, digits, 0);
        return ans;
    }

    private void backtrack(List<String> ans, StringBuilder path, String digits, int index) {
        //如果遍历到字符串末尾，则将path加入结果集
        if (index == digits.length()) {
            ans.add(path.toString());
            return;
        }
        //获取当前数字对应的字母
        //digits.charAt(index) - '0'表示的是字符对应的数字，例如'2'-'0'=2
        int digit = digits.charAt(index) - '0';
        //遍历当前数字对应的字母
        String letters = LETTERS[digit];
        for (char letter : letters.toCharArray()) {
            path.append(letter);
            //递归遍历下一个数字
            backtrack(ans, path, digits, index + 1);
            //回溯，撤销选择
            path.deleteCharAt(path.length() - 1);
        }
    }
}

49.从前序与中序遍历序列构造二叉树（中等 二叉树）

img

先序：[ 根 | 左子树(先序) | 右子树(先序) ] → 第一个元素就是当前子树的根。

中序：[ 左子树(中序) | 根 | 右子树(中序) ] → 根在中序中的位置把区间一分为二，左边是左子树，右边是右子树。

先序拿“根”，中序分“左右”，用“左子树大小”在先序里切段，两个区间递归下去即可。

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
class Solution {
    // 把中序数组的“值 -> 下标”存起来，O(1) 定位根在中序中的位置
    private Map<Integer, Integer> idx;
    // 先序数组
    private int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        // 把中序数组的“值 -> 下标”存起来，O(1) 定位根在中序中的位置
        idx = new HashMap<>(inorder.length * 2);
        for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);

        // 递归构建：先序区间 [0..n-1]，中序区间 [0..n-1]
        return build(0, preorder.length - 1, 0, inorder.length - 1);
    }

    // 递归函数：用“先序[preL..preR] + 中序[inL..inR]”这两个区间，构造出对应的子树，并返回其根节点
    private TreeNode build(int preL, int preR, int inL, int inR) {
        if (preL > preR) return null;                // 空区间：没有节点

        int rootVal = preorder[preL];                // 先序的第一个就是当前子树的“根”
        int inRoot  = idx.get(rootVal);              // 根在中序中的位置
        int leftSize = inRoot - inL;                 // 左子树节点数 = 中序左半部分的长度

        TreeNode root = new TreeNode(rootVal);

        // 左子树：
        //   先序：根之后的 leftSize 个，即 [preL+1 .. preL+leftSize]
        //   中序：根左侧区间           即 [inL .. inRoot-1]
        root.left = build(preL + 1, preL + leftSize, inL, inRoot - 1);

        // 右子树：
        //   先序：左子树那段之后        即 [preL+leftSize+1 .. preR]
        //   中序：根右侧区间            即 [inRoot+1 .. inR]
        root.right = build(preL + leftSize + 1, preR, inRoot + 1, inR);

        return root;
    }
}

手工走一遍示例

1
2
preorder = [3, 9, 20, 15, 7]`
`inorder = [9, 3, 15, 20, 7]
  1. 整棵树
  • preL=0, preR=4, inL=0, inR=4
  • 根 = preorder[0]=3；inRoot = idx.get(3)=1
  • leftSize = 1 - 0 = 1
  • 左子树区间：
    • 先序 [1..1]（只有 9）
    • 中序 [0..0]（只有 9）
  • 右子树区间：
    • 先序 [2..4]（20,15,7）
    • 中序 [2..4]（15,20,7）
  1. 构左子树（值 9）
  • preL=1, preR=1, inL=0, inR=0
  • 根 = preorder[1]=9；inRoot = 0；leftSize=0
  • 左区间 [2..1] 空 → null
  • 右区间 [2..1] 空 → null
    → 左子树为单节点 9。
  1. 构右子树（根 20）
  • preL=2, preR=4, inL=2, inR=4
  • 根 = preorder[2]=20；inRoot=3；leftSize=3-2=1
  • 右子树的左子树区间：
    • 先序 [3..3]（15）
    • 中序 [2..2]（15）
  • 右子树的右子树区间：
    • 先序 [4..4]（7）
    • 中序 [4..4]（7）
  1. 右子树的左子树（值 15）
  • 单节点 15。
  1. 右子树的右子树（值 7）
  • 单节点 7。

最终得到结构：

1
2
3
4
5
  3
 / \
9   20
   /  \
  15   7

另一个巧妙的方法

基本思路

题目给我们两个序列：

  • 前序遍历 preorder：根 -> 左子树 -> 右子树
  • 中序遍历 inorder：左子树 -> 根 -> 右子树

利用这两个序列，我们要唯一地还原出一棵二叉树。

关键点：

  1. 前序遍历的第一个元素就是根节点。
  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
class Solution {
    private int pre = 0; // 前序数组的游标
    private int in = 0;  // 中序数组的游标

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Long.MAX_VALUE); // 初始 stop 设置为无穷大
    }
    
    private TreeNode build(int[] preorder, int[] inorder, long stop) {
        if (pre == preorder.length) return null; // 前序走完了

        // 中序遇到 stop，说明当前子树结束
        if (inorder[in] == stop) {
            in++;
            return null;
        }

        // 取当前前序的节点值，作为根
        int rootVal = preorder[pre++];
        TreeNode root = new TreeNode(rootVal);

        // 递归构造左子树，直到遇到 rootVal 为止
        root.left = build(preorder, inorder, rootVal);

        // 递归构造右子树，直到遇到 stop 为止
        root.right = build(preorder, inorder, stop);

        return root;
    }
}

这个解法的亮点是 利用 stop 来界定子树的范围，避免了传统做法中「用哈希表存值到索引」的繁琐操作。

stop：相当于一个“哨兵值”，表示递归到某个子树的边界。

  • 构造左子树时，边界是 当前根节点值。

  • 构造右子树时，边界是 父递归传下来的 stop 值。

  • pre：每次从前序里取一个新值（就是新的根）。

  • in：在中序中不断前进，直到遇到 stop，说明当前子树已经结束。

执行过程示例

以 preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7] 为例：

  1. pre=0，取 3当根，创建 TreeNode(3)

    • 左子树的 stop = 3
    • 右子树的 stop = MAX_VALUE

  2. 进入左子树：

    • pre=1，取 9 当根。
    • 左子树的 stop = 9 → 遇到 inorder[in] == 9 → 返回 null
    • 右子树的 stop = 3 → 遇到 inorder[in] == 3 → 返回 null
    • 返回节点 9

  3. 回到根 3，进入右子树：

    • pre=2，取 20 当根。
    • 左子树的 stop = 20 → pre=3，取 15，左右都返回 null。
    • 右子树的 stop = MAX_VALUE → pre=4，取 7，左右返回 null。
  • 返回节点 20，包含子树 15 和 7

最终得到树：

1
2
3
4
5
  3
 / \
9   20
   /  \
  15   7

这个写法的思路是：

  • 前序遍历负责建树（决定根节点）。
  • 中序遍历负责划分边界（决定子树范围）。
  • 用 stop 巧妙地避免了额外的哈希表索引查找，代码更简洁。

50.括号生成（中等 回溯）

img

回溯法

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
//括号生成
// 给定一个整数 n，生成所有由左右括号组成的合法的（格式正确的）长度为 2n 的字符串
// 例如：输入: n = 3, 输出: ["((()))","(()())","(())()","()(())","()()()"]
class Solution {
    public List<String> generateParenthesis(int n) {
        //创建结果集
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        //定义一个StringBuilder
        StringBuilder sb = new StringBuilder();
        //递归生成括号组合
        backtrack(res, sb, 0, 0, n);
        return res;
    }

    private void backtrack(List<String> res, StringBuilder sb, int open, int close, int max) {
        //1.处理非法结果
        //如果左括号数量大于n或者右括号数量大于左括号，则不合法
        if (open > max || close > open) {
            return;
        }
        //如果左括号和右括号的数量都等于n，则找到了一个合法的组合
        if (open == max && close == max) {
            res.add(sb.toString());
            return;
        }
        //2.递归生成左右括号组合
        //递归生成左括号
        sb.append('(');
        backtrack(res, sb, open + 1, close, max);
        sb.deleteCharAt(sb.length() - 1);

        //递归生成右括号
        sb.append(')');
        backtrack(res, sb, open, close + 1, max);
        sb.deleteCharAt(sb.length() - 1);
    }
}

51组合总和（中等 回溯）

img

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
/**
 * @author geqian
 * @version 1.0
 * @description 组合总和
 * 回溯法
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，
 * 并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * @date 2025/9/9 10:27
 */


 class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
         if(candidates == null || candidates.length == 0) return new ArrayList<>();
         List<List<Integer>> res = new ArrayList<>();// 收集所有可行解
         List<Integer> path = new ArrayList<>(); // 当前正在构造的组合（路径）
         backtrack(candidates, target, 0, res, path);// 从下标 0 开始做选择
         return res;
    }
    // 回溯法
    private void backtrack(int[] candidates, int target, int startIndex, List<List<Integer>> res, List<Integer> path){
        if(target < 0) return;  // 剪枝：和已经超了，不可能再凑成0
        if(target == 0){  // 命中：把当前 path 拷贝进答案
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = startIndex; i < candidates.length; i++){
      if(candidates[i] > target) continue;// 剪枝（不排序时用 continue，不能 return）
            path.add(candidates[i]);// 做选择
            backtrack(candidates, target - candidates[i], i, res, path);// 传 i：允许重复选这个数
            // 回溯，撤销选择
            path.remove(path.size() - 1);
        }
    }
}

img

img

img

img

一个“更快”的改进版本（排序 + 更强剪枝）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);                 // 先排好序
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] a, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < a.length; i++) {
            if (a[i] > target) break;           // 排序后可直接 break
            path.add(a[i]);
            backtrack(a, target - a[i], i, path, res); // i：可重复用
            path.remove(path.size() - 1);
        }
    }
}

排序后 a[i] > target 直接 break，能“剪掉”后面所有不可能的分支，比 continue 更省时。

这道题的关键要点

  • startIndex 防重：不回头选更早的下标，去掉排列重复；同时传 i 允许重复使用元素。
  • target 作为状态：命中 0 加入答案，负数回溯。
  • 剪枝：不排序时用 continue；排序后可换成 break 更强。
  • 回溯模板：做选择 → 递归 → 撤销选择（写成三行非常稳）。

52.单词搜索（中等 回溯）

img

img

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 boolean exist(char[][] board, String word) {
        int m = board.length;// 行数
        int n = board[0].length;// 列数
        boolean[][] visited = new boolean[m][n];// 标记访问过的点
        // 遍历二维数组，从每个点开始尝试搜索
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从每个点开始尝试搜索，如果找到匹配的单词，返回 true
                if (backtrack(board, word, visited, i, j, 0)) return true;
            }
        }
        // 所有点都遍历完了，都没有找到匹配的单词
        return false;
    }
    // 回溯法
    private boolean backtrack(char[][] board, String word, boolean[][] visited, int i, int j, int index) {
        // 终止条件：遍历到最后一个字符，返回 true
        if (index == word.length()) return true;
        // 边界条件：超出范围，或者已经访问过，或者当前字符不匹配
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)) return false;
        visited[i][j] = true;// 做选择，标记访问过
        // 递归遍历上、下、左、右四个方向
        boolean res = backtrack(board, word, visited, i - 1, j, index + 1);//上
        if (!res) res = backtrack(board, word, visited, i + 1, j, index + 1);//下
        if (!res) res = backtrack(board, word, visited, i, j - 1, index + 1);//左
        if (!res) res = backtrack(board, word, visited, i, j + 1, index + 1);//右
        visited[i][j] = false;// 撤销选择，恢复现场
        return res;
    }
}

代码详细讲解

这个代码是典型的 回溯法（Backtracking）+ DFS 深度优先搜索 解法。我们逐步拆开来看：

  1. 主函数 exist
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean exist(char[][] board, String word) {
    int m = board.length;// 行数
    int n = board[0].length;// 列数
    boolean[][] visited = new boolean[m][n];// 标记访问过的点
    // 遍历二维数组，从每个点开始尝试搜索
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 从每个点开始尝试搜索，如果找到匹配的单词，返回 true
            if (backtrack(board, word, visited, i, j, 0)) return true;
        }
    }
    // 所有点都遍历完了，都没有找到匹配的单词
    return false;
}
  • 思路：
    每一个格子都可能是单词的起点，所以需要从所有 (i, j) 出发做 DFS 搜索。
  • visited：防止走回头路（同一个格子在一个路径中不能重复用）。
  • 一旦找到一个路径能匹配 word，立刻返回 true。
  • 回溯函数 backtrack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private boolean backtrack(char[][] board, String word, boolean[][] visited, int i, int j, int index) {
    // 终止条件：遍历到最后一个字符，返回 true
    if (index == word.length()) return true;
    // 边界条件：超出范围，或者已经访问过，或者当前字符不匹配
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visited[i][j] || board[i][j] != word.charAt(index)) 
        return false;

    visited[i][j] = true; // 做选择，标记访问过

    // 递归遍历上、下、左、右四个方向
    boolean res = backtrack(board, word, visited, i - 1, j, index + 1);//上
    if (!res) res = backtrack(board, word, visited, i + 1, j, index + 1);//下
    if (!res) res = backtrack(board, word, visited, i, j - 1, index + 1);//左
    if (!res) res = backtrack(board, word, visited, i, j + 1, index + 1);//右

    visited[i][j] = false; // 撤销选择，恢复现场（关键！回溯）
    return res;
}

  1. 关键逻辑解释

  2. 递归的含义：
    backtrack(i, j, index) 表示：从坐标 (i, j) 出发，能否匹配 word[index...] 这一段子串。

  3. 终止条件：

    • 如果 index == word.length()，说明整段单词都已经匹配完毕 → 返回 true。

  4. 剪枝条件：

    • 出界 (i, j 越界)

  • 已访问过 (visited[i][j] == true)

    • 当前格子字母 ≠ 当前目标字符 (board[i][j] != word.charAt(index))

      满足任意条件直接返回 false。

  1. 做选择：

    • 标记当前格子已访问 → visited[i][j] = true。

  2. 递归搜索 4 个方向：

    • 分别向上、下、左、右继续搜索下一个字符。
    • 一旦某个方向返回 true，说明找到整条路径。

  3. 回溯：

    • 如果没找到，把当前格子恢复成未访问 (visited[i][j] = false)，继续尝试别的路径。

  4. 举个例子

比如输入：

1
2
3
4
5
6
board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED"
  • 从 (0,0) ‘A’ 开始，递归找 “B” → (0,1)
  • 再找 “C” → (0,2)
  • 再找 “C” → (1,2)
  • 再找 “E” → (2,2)
  • 再找 “D” → (2,1)
  • 单词匹配完成 → 返回 true

  • 总结

  • 回溯框架：

    • 试探 → 检查条件 → 递归 → 回退

  • 关键点：

    • visited 防止重复用格子。
    • 回溯时一定要恢复现场，不然会影响别的路径。

  • 时间复杂度：

    • 最坏情况下 O(m n 4^L)，其中 L = word.length()。

53.分割回文串（中等 回溯）

img

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
class Solution {
    public List<List<String>> partition(String s) {
        if(s == null || s.length() == 0){
            return new ArrayList<>();
        }
        // 存放结果集
        List<List<String>> res = new ArrayList<>();
        // 存放当前路径
        List<String> path = new ArrayList<>();
        // 回溯法,从0开始遍历字符串s
        backtrack(s, 0, res, path);
        return res;
    }

    private void backtrack(String s, int i, List<List<String>> res, List<String> path) {
     // 终止条件：切到了字符串末尾，说明当前 path 是一个合法方案
        if(i == s.length()){
            res.add(new ArrayList<>(path));// 必须拷贝
            return;
        }

    // 枚举“下一刀”切到哪里：j 从 i 走到 s.length()-1
        for(int j = i; j < s.length(); j++){
              // 剪枝：只有 s[i..j] 是回文才继续
            if(!isPalindrome(s, i, j)){
                continue;
            }
           // 做选择：把这一段加入路径
            path.add(s.substring(i, j+1));
           
        // 递归：从 j+1 处继续切
            backtrack(s, j+1, res, path);
             // 撤销选择（回溯）
            path.remove(path.size()-1);
        }
    }
    // 判断是否是回文串，用双指针从两端往中间比较，O(len) 时间判断 [i..j] 是否回文。
    private boolean isPalindrome(String s, int i, int j) {
        while(i < j){
            // 如果当前字符不相等,则不是回文串
            if(s.charAt(i++) != s.charAt(j--)){
                return false;
            }
        }
        return true;
    }
}

核心思路：把字符串从左到右切开，每次尝试把当前位置到任意位置的子串作为一段；只有当这段是回文时才继续向后递归；走到末尾就把当前切法加入答案。

img

为什么要 new ArrayList<>(path)？
path 是同一块可变内存，会在后续回溯中被修改；不拷贝会导致 res 中保存的引用被后续更改污染。

剪枝点
只有 s[i..j] 是回文时才继续深搜；否则直接跳过，有效减少搜索量。

54.路径总和（中等 二叉树）

img

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 {
    /**
     * 计算二叉树中路径和等于目标值的路径数目
     * @param root 二叉树的根节点
     * @param targetSum 目标路径和
     * @return 满足条件的路径数目
     */
    public int pathSum(TreeNode root, int targetSum) {
        return pathSum(root, (long) targetSum);
    }

    /**
     * 递归计算以当前节点为根的所有路径中满足条件的路径数目
     * @param root 当前子树根节点
     * @param target 目标路径和
     * @return 满足条件的路径数目
     */
    private int pathSum(TreeNode root, long target) {
        if (root == null) return 0;
        // 计算从当前节点开始的路径 + 左子树路径 + 右子树路径
        return pathSumFrom(root, target)
                + pathSum(root.left, target)
                + pathSum(root.right, target);
    }

    /**
     * 计算从当前节点开始向下满足条件的路径数目
     * @param node 当前节点
     * @param target 剩余需要满足的路径和
     * @return 满足条件的路径数目
     */
    private int pathSumFrom(TreeNode node, long target) {
        if (node == null) return 0;
        long remain = target - (long) node.val;
        // 如果当前节点值等于剩余目标值，则计数1
        int cnt = (target == (long) node.val) ? 1 : 0;
        // 递归计算左子树和右子树
        return cnt + pathSumFrom(node.left, remain)
                + pathSumFrom(node.right, remain);
    }
}

55.搜索二维矩阵（中等 二分查找 ）

img

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 boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;// 行数
        int n = matrix[0].length;// 列数
        // 从右上角开始搜索
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                // 找到目标值，返回true
                return true;
            } else if (matrix[i][j] > target) {
                // 当前值大于目标值，向左移动
                j--;
            } else {
                // 当前值小于目标值，向下移动
                i++;
            }
        }
        // 遍历完整个矩阵，没有找到目标值，返回false
        return false;
    }
}

56.搜索二维矩阵II（中等 矩阵/二分查找）

img

img

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 boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;// 行数
        int n = matrix[0].length;// 列数
        // 从右上角开始搜索
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                // 找到目标值，返回true
                return true;
            } else if (matrix[i][j] > target) {
                // 当前值大于目标值，向左移动
                j--;
            } else {
                // 当前值小于目标值，向下移动
                i++;
            }
        }
        // 遍历完整个矩阵，没有找到目标值，返回false
        return false;
    }
}

这道题和55题做法一模一样

57.矩阵置零（中等 矩阵）

img

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 void setZeroes(int[][] matrix) {
        int m = matrix.length;// 行数
        int n = matrix[0].length;// 列数
        boolean[] rowZeroes = new boolean[m];// 记录哪些行需要置零
        boolean[] colZeroes = new boolean[n];// 记录哪些列需要置零
        // 遍历矩阵，记录哪些行和列需要置零
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rowZeroes[i] = true;
                    colZeroes[j] = true;
                }
            }
        }
        // 遍历矩阵，将需要置零的行和列都置为零
        //行列分开置零，避免重复置零
        //首先是行置零，然后是列置零
        for (int i = 0; i < m; i++) {
            if (rowZeroes[i]) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
      //列置零
        for (int j = 0; j < n; j++) {
            if (colZeroes[j]) {
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

58.旋转图像(中等 矩阵)

img

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 void rotate(int[][] matrix) {
        int m =matrix.length;//行数
        int n = matrix[0].length;//列数
        // 先沿对角线翻转
        for (int i = 0; i < m; i++) {
            for (int j = i; j < n; j++) {
                //交换行列元素:行列互换，第一列变成了第一行
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // 再按行左右翻转
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
    }
}

img

59.在排序数组中查找元素的第一个和最后一个位置（中等 二分查找）

img

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        //二分查找，查找第一个等于target的元素和最后一个等于target的元素
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                //找到目标值，继续向左查找第一个等于target的元素
                int start = mid;
                while (start >= 0 && nums[start] == target) {
                    start--;
                }
                //找到目标值，继续向右查找最后一个等于target的元素
                int end = mid;
                while (end < nums.length && nums[end] == target) {
                    end++;
                }
                return new int[]{start + 1, end - 1};
            }
        }
        return new int[]{-1, -1};
    }
}

60搜索旋转排序数组（中等 二分查找）

img

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 {
    //返回target的下标值，若不存在返回-1
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        //二分查找
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //先判断mid是否为目标值
            if (nums[mid] == target) {
                return mid;
            }
            //左半边有序
            if (nums[left] <= nums[mid]) {
                //判断target是否在左半边
                if (nums[left] <= target && nums[mid] >= target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                //右半边有序
                if (nums[mid] <= target && nums[right] >= target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

要点小结：

  • 每轮必须更新指针，否则会死循环。
  • 通过 nums[left] <= nums[mid] 判断左侧是否有序；有序那侧再看 target 是否落在区间内，决定向哪边收缩。
  • 复杂度 O(log n)，空间 O(1)。

61.寻找旋转排序数组种的最小值（中等 二分查找）

img

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 findMin(int[] nums) {
     if(nums.length == 1) return nums[0];
     int left = 0;
     int right = nums.length - 1;
     //二分查找
     while(left < right){
        int mid = (right + left) / 2;
        //如果中间值大于右边，说明最小值在右半边
        if(nums[mid] > nums[right]){
            //最小值在右半边
            left = mid + 1;
        }else{
            //最小值在左半边或者就是中间的值
            right = mid;
        }
     }
     //因为是升序排列，所以最小值一定在left的位置
     return nums[left];
    }
}

62螺旋矩阵（中等 矩阵）

img

img

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
public List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length;             // 行数
    int n = matrix[0].length;          // 列数
    List<Integer> res = new ArrayList<>();

    // 定义四条边界：当前未遍历区域是 [top..bottom] × [left..right]
    int top = 0, bottom = m - 1, left = 0, right = n - 1;

    // 输出总数达到 m*n 即结束
    while (res.size() < m * n) {

        // 1) 走上边：固定行 top，列从 left -> right
        if (top <= bottom) {
            for (int j = left; j <= right; j++) res.add(matrix[top][j]);
            top++;                      // 上边用完，往下缩一行
        }

        // 2) 走右边：固定列 right，行从 top -> bottom
        if (left <= right) {
            for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
            right--;                    // 右边用完，往左缩一列
        }

        // 3) 走下边：固定行 bottom，列从 right -> left
        if (top <= bottom) {
            for (int j = right; j >= left; j--) res.add(matrix[bottom][j]);
            bottom--;                   // 下边用完，往上缩一行
        }

        // 4) 走左边：固定列 left，行从 bottom -> top
        if (left <= right) {
            for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
            left++;                     // 左边用完，往右缩一列
        }
    }
    return res;
}

img

下面这段代码实现的是“用四条边框逐层收缩”的顺时针螺旋遍历。思路很直观：

  • 用四个指针把当前“还没输出”的子矩形框出来：
    top（上边界行号）、bottom（下边界行号）、left（左边界列号）、right（右边界列号）。
  • 每一轮按 上→右→下→左 的顺序把四条边走一遍，并在走完一条边后把对应的边界向里缩 1。
  • 每条边在走之前都要做“是否还有这一条边”的检查（例如已经没有行/列了就别走），防止重复或越界。
  • 循环直到输出了 m * n 个元素为止。

为什么要加这些 if (top <= bottom) / if (left <= right)？

当矩形逐层缩小到只剩 一行 或 一列 时，“四边”中会有两边是重合/不存在的。如果不加判断，第三步或第四步可能会把同一行/列再走一遍，造成重复，或在 1×N、M×1 这类边界矩阵上越界。
这些守卫条件确保“有这条边才走”。

结束条件为什么用 res.size() < m * n？

这是最直接、不易出错的方式：当输出元素数量达到总数即结束。
也可以用另外一种写法：while (top <= bottom && left <= right)，但那样在每一条边循环内部更要小心边界，容易写出重复/漏掉元素的情况；本代码用元素计数避免了这种细节坑。

小例子走一轮（3×3）

初始 top=0,bottom=2,left=0,right=2

  • 上边：(0,0..2) → [1,2,3]，top=1
  • 右边：(1..2,2) → [6,9]，right=1
  • 下边：(2,1..0) → [8,7]，bottom=1
  • 左边：(1..1,0) → [4]，left=1
    再下一轮只剩中间 top=1=bottom,left=1=right 的 [5]，输出后结束。

复杂度

  • 时间：O(m·n) —— 每个元素只访问一次
  • 空间：O(1) 额外空间（结果列表不计）

可选的健壮性

如果可能传入空矩阵，外层先判空：

1
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return Collections.emptyList();

这段代码的核心就是“四边界收缩 + 方向遍历 + 边界守卫”。

63.打家劫舍（中等 动态规划）

img

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 rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;//当没有长度返回0
        if (n == 1) return nums[0];//当只有一个房间时，直接返回金额
        int[] dp = new int[n];//定义dp数组，dp[i]表示偷到第i个房间时能得到的最大金额
        dp[0] = nums[0];//初始化dp数组，第一个房间金额即为最大金额
        dp[1] = Math.max(nums[0], nums[1]);//第二个房间金额为前两个房间的最大值
        for (int i = 2; i < n; i++) {
            /**
             * 对第 i 个房子，有两种选择：
             * 1.不偷第 i 个房子
             * 那么最大金额就是前一个房子能偷到的最大金额：
             * dp[i - 1]
             * 2.偷第 i 个房子
             * 由于相邻房子不能偷，所以第 i-1 个房子一定不能偷。
             * 最大金额是：
             * dp[i - 2] + nums[i]
             */
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
}

img

img

64.完全平方数（中等 动态规划）

img

题意 → 动态规划建模（完全背包）

  • 要把整数 n 拆成若干个完全平方数（1, 4, 9, 16, …）的和，且个数最少。

  • 这就像一个完全背包：

    • 物品：价值为 1, 4, 9, 16, … 的“平方数物品”，每个物品可无限次拿（完全背包）。
    • 背包容量：n。
    • 目标：用最少件数装满容量为 n 的背包。

于是我们定义：

dp[i]：凑出总和 恰好为 i 的最少完全平方数个数（不可达的话就设为一个很大值，但代码里用更聪明的初始化方式规避了这个问题）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int numSquares(int n) {
    if (n == 0) return 0;
    int[] dp = new int[n + 1];

    // 1) 初始化
    for (int i = 1; i <= n; i++) {
        dp[i] = i;          // 最坏情况：i = 1^2 + 1^2 + ... + 1^2（i 个 1），所以上界是 i
    }

    // 2) 状态转移
    for (int i = 1; i <= n; i++) {                // 逐个求 dp[i]
        for (int j = 1; j * j <= i; j++) {        // 尝试最后一个平方数是 j^2
            dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
            // 解释：把 i 拆成 (i - j^2) + j^2
            // 其中 dp[i - j^2] 是“凑成 i - j^2 的最优解”，再加上一个 j^2，共 +1 个
        }
    }
    return dp[n];
}

为什么这样就能“无限使用平方数”？

因为 dp[i] 的转移用到 dp[i - j^2]，而 dp[i - j^2] 自己又是通过同样的公式由更小的状态推出来的。
这就允许把同一个平方数 j^2 用很多次（比如 i 不断减去 j^2），这正是完全背包“可重复使用”的本质

手算一遍（以 n = 12 为例）

先把 dp[i] 初始化为 i，表示“全用 1 的平方”这条朴素方案。接着按 i 从小到大更新。

  • i = 1：可选平方数只有 1

    • dp[1] = min(1, dp[0] + 1 = 1) → 1

  • i = 2：平方数 1

    • dp[2] = min(2, dp[1] + 1 = 2) → 2

  • i = 3：平方数 1

    • dp[3] = min(3, dp[2] + 1 = 3) → 3

  • i = 4：平方数 1, 4

    • 用 1：dp[3] + 1 = 4
    • 用 4：dp[0] + 1 = 1 → 最优是 1（4）

  • i = 5：平方数 1, 4

    • 用 1：dp[4] + 1 = 2
    • 用 4：dp[1] + 1 = 2 → 最优 2（4+1）

  • i = 6：平方数 1, 4

    • 用 1：dp[5] + 1 = 3
    • 用 4：dp[2] + 1 = 3 → 最优 3（4+1+1）

  • i = 7：平方数 1, 4

    • 用 1：dp[6] + 1 = 4
    • 用 4：dp[3] + 1 = 4 → 最优 4

  • i = 8：平方数 1, 4

    • 用 1：dp[7] + 1 = 5
    • 用 4：dp[4] + 1 = 2 → 最优 2（4+4）

  • i = 9：平方数 1, 4, 9

    • 用 1：dp[8] + 1 = 3
    • 用 4：dp[5] + 1 = 3
    • 用 9：dp[0] + 1 = 1 → 最优 1（9）

  • i = 10：1, 4, 9

    • 得到 2（9+1）

  • i = 11：1, 4, 9

    • 得到 3（9+1+1）

  • i = 12：1, 4, 9

    • 用 1：dp[11] + 1 = 4
    • 用 4：dp[8] + 1 = 3
    • 用 9：dp[3] + 1 = 4 → 最优 3（4+4+4）

因此 dp[12] = 3，与题目样例一致。

初始化为什么是 dp[i] = i？

这是一个安全上界：
任何 i 都能用 i 个 1^2 凑出来，因此“最坏”需要 i 个数，这样初始化后，后续一旦找到更好的组合，就会被 Math.min 替换掉。

总结一句话

把「最少平方数和为 n」转化为完全背包：
dp[i] = min(dp[i], dp[i - j^2] + 1)，外层枚举 i，内层枚举所有平方数 j^2，逐步把更优的方案“压”到 dp[i] 上，最终得到 dp[n]。

65.零钱兑换（中等 动态规划）

给定硬币面额 coins，任取数量，最少用多少枚能凑出 amount。凑不出就返回 -1。

img

思路分解

1) 状态定义

  • dp[i] 表示恰好凑出金额 i 所需的最少硬币数量。
  • dp[0] = 0（Java 默认 0）；其他位置先设成“不可达”。
  • 状态转移

对每个目标金额 i，尝试用每种面额 coin 作为最后一枚：

  • 如果 coin <= i，且 dp[i - coin] 可达（不是 MAX_VALUE），
    那么：
    dp[i] = min(dp[i], dp[i - coin] + 1)
    含义：凑出 i - coin 的最优解 + 这一枚 coin。

这正是完全背包的转移：同一枚硬币可以重复使用，因为我们从 dp[i - coin] 过来时，依然可以继续用 coin。

3) 初始化与不可达

  • dp[i] 初始为 Integer.MAX_VALUE，表示暂不可达。
  • 判断条件 dp[i - coin] != Integer.MAX_VALUE 的目的是避免溢出（MAX_VALUE + 1 会溢出为负数），也表示只有子问题可达，当前问题才有可能可达。

  • 循环顺序（为什么“金额在外、硬币在内”？）

  • 这是完全背包的两种等价写法之一：

    • 写法 A（本题）：
      for (i = 1..amount) for (coin : coins) 更新 dp[i]
    • 写法 B：
      for (coin : coins) for (i = coin..amount) 更新 dp[i]
  • 两者都会允许重复使用硬币，都是对的。本题使用写法 A。

  • 边界与返回

  • amount == 0 直接返回 0。

  • dp[amount] 仍是 MAX_VALUE 说明不可达 → 返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
public int coinChange(int[] coins, int amount) {
    if (amount == 0) return 0;
    int[] dp = new int[amount + 1];     // dp[i]：恰好凑出金额 i 的最少硬币数
    for (int i = 1; i <= amount; i++) {
        dp[i] = Integer.MAX_VALUE;      // 初始为“不可达”
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != Integer.MAX_VALUE) { // 避免溢出
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

例子走一遍（coins = [1,2,5], amount = 11）

i 尝试 coin 用前 dp[i] 看 dp[i-coin] 新 dp[i]
1 1 INF dp[0]=0 1
2 1,2 INF→1 dp[1]=1,dp[0]=0 1
3 1,2 INF→2 dp[2]=1,dp[1]=1 2
… … … … …
11 1,2,5 … dp[10]=2,dp[9]=3,dp[6]=2 3

最后得到 dp[11] = 3（5+5+1）。

66.每日温度（中等 栈）

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 结果数组
        int[] answer = new int[temperatures.length];
        // 单调栈，存放索引
        Stack<Integer> stack = new Stack<>();
        // 从左向右遍历温度数组
        for (int i = 0; i < temperatures.length; ++i) {
            // 如果栈不为空，且当前温度大于栈顶索引对应的温度
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                // 弹出栈顶索引，并计算天数差
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            // 将当前索引压入栈中
            stack.push(i);
        }
        return answer;
    }
}

67.划分字母区间（中等 贪心算法）

img

目标：把字符串切成尽可能多的片段，且同一个字母只出现在一个片段中，返回每个片段的长度。

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<Integer> partitionLabels(String s) {
        // 边界条件判断
        if(s == null || s.length() == 0) return new ArrayList<>();
        int[] last = new int[26];
        // 记录每个字母最后出现的位置
        for(int i = 0; i < s.length(); i++){
            last[s.charAt(i) - 'a'] = i;
        }
        // 记录每个片段的长度
        List<Integer> res = new ArrayList<>();
        // 记录当前片段的开始和结束位置
        int start = 0, end = 0;
        // 遍历字符串，更新当前片段的结束位置
        for(int i = 0; i < s.length(); i++){
            // 更新当前片段的结束位置
            end = Math.max(end, last[s.charAt(i) - 'a']);
            // 如果当前位置是当前片段的结束位置，则将当前片段的长度加入结果列表
            if(i == end){
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
}

1) 先预处理：每个字母最后一次出现的位置

1
2
3
4
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
}
  • last[c] 记录字符 c 在字符串中的最右位置。
  • 这是后面判断一个片段是否可以“完结”的关键：如果我们当前片段包含了某些字符，就必须把片段至少扩到这些字符的最后出现位置，否则切开后右边还会遇到它，违反“同字母只能在一个片段”的要求。
  • 一次线性扫描+贪心维护片段边界
1
2
3
4
5
6
7
8
9
List<Integer> res = new ArrayList<>();
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
    end = Math.max(end, last[s.charAt(i) - 'a']); // 片段必须覆盖到当前字符的最远处
    if (i == end) { // 到达当前片段的最右边界，可以切分
        res.add(end - start + 1);
        start = end + 1; // 开启下一个片段
    }
}
  • 扫描到第 i 位时，当前片段的右边界应该至少是这段里所有字符的“最后出现位置”的最大值；代码用 end = max(end, last[当前字符]) 来维护。
  • 当 i == end，说明从 start 到 end 的区间已经把片段里所有字符都“包圆”了——后面再也不会出现这些字符，因此可以在这里切开，把长度加入答案，并从下一个位置开始新的片段。

正确性为什么成立（贪心证明直觉）

  • 为了让片段数量尽可能多，我们应当在最早能切开的地方就切开；
  • “能切开”的条件是：当前片段里出现的所有字符，都已经在当前索引 i 之前完成了它们的最后出现（也就是 i == end）；
  • 在此之前任何位置切开都会导致右边再遇到片段内的某个字符而冲突，所以这是最早可切位置 ⇒ 贪心最优。

img

68.跳跃游戏II（中等 贪心算法）

img

顺藤摸瓜

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int maxPos = 0;// 当前能达到的最远位置
        int end = 0;// 当前能达到的最远位置的最后一个元素的位置
        int step = 0;// 跳跃次数
        // 从第一个元素开始遍历，直到倒数第二个元素
        for(int i = 0; i < n - 1; i++){
            // 更新当前能达到的最远位置
            maxPos = Math.max(maxPos, i + nums[i]);
            // 如果当前位置是当前能达到的最远位置的最后一个元素，则更新下一次跳跃的起始位置和跳跃次数
            if(i == end){
                end = maxPos;
                step++;
            }
        }
        return step;
    }
}

img

顺瓜摸藤
我们知道最终要到达最后一个位置，然后我们找前一个位置，遍历数组，找到能到达它的位置，离它最远的就是要找的位置。然后继续找上上个位置，最后到了第 0 个位置就结束了。

至于离它最远的位置，其实我们从左到右遍历数组，第一个满足的位置就是我们要找的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int jump(int[] nums) {
    int position = nums.length - 1; //要找的位置
    int steps = 0;
    while (position != 0) { //是否到了第 0 个位置
        for (int i = 0; i < position; i++) {
            if (nums[i] >= position - i) {
                position = i; //更新要找的位置
                steps++;
                break;
            }
        }
    }
    return steps;
}

img

69.数组中的第K个最大元素（中等 堆）

img

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
class Solution {
    /**
     * 在未排序的数组中找到第 k 个最大的元素。
     *
     * @param nums 待查找的整数数组
     * @param k    要查找的第 k 个最大元素的索引（索引从 1 开始）
     * @return 第 k 个最大的元素
     */
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        //为什么target = n-k
        // 例如：数组长度为 n，第 k 大元素即为排序后位于下标 n-k 的位置
        int target = n - k;           // 第 k 大 = 第 n-k 小（0-based）
        int left = 0, right = n - 1;
        // 快速选择算法，每次分区后判断 pivot 的位置
        while (true) {
            int p = partition(nums, left, right);
            // 判断 pivot 是否为第 k 大元素的位置 如果是返回p的下标
            if (p == target) return nums[p];
            // 否则根据 pivot 的位置调整查找范围
            // 例如：pivot 在左侧，则在右侧查找，pivot在右侧，则在左侧查找
            else if (p < target) left = p + 1;
            else right = p - 1;
        }
    }

    /**
     * 对数组进行分区操作。
     *
     * @param a 待分区的数组
     * @param l 分区起始位置（包含）
     * @param r 分区结束位置（不包含）
     * @return 基准元素的最终位置
     */
    private int partition(int[] a, int l, int r) {
        // 随机选基准，避免退化
        //为什么用ThreadLocalRandom而不是Random？
        //随机 pivot 用 ThreadLocalRandom.current().nextInt(l, r+1)，参数永远是“左闭右开”，且保证 l <= r 时范围合法。
        int pivotIdx = ThreadLocalRandom.current().nextInt(l, r + 1);
        // 随机交换到数组末尾，避免最坏情况
        swap(a, pivotIdx, r);
        // 升序排列，小于 pivot 的元素放到左侧
        int pivot = a[r];
        int i = l;                     // a[l..i-1] < pivot
        for (int j = l; j < r; j++) {  // a[i..j-1] >= pivot（未分类）
            if (a[j] < pivot) {        // 升序位置
                swap(a, i, j);
                i++;
            }
        }
        swap(a, i, r);                 // pivot 放到最终位置 i
        return i;
    }
     /**
     * 交换数组中的两个元素。
     *
     * @param a 要操作的数组
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    private void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

当然可以！下面我用一个具体用例，像“打断点”一样一步步走你的代码，并把每次关键变量和数组形态都打印出来，帮你直观看到流程。

用例

1
2
nums = [3,2,3,1,2,4,5,5,6]
k = 4

数组长度 n = 9，我们要找第 4 大。
在升序下标里：第 k 大 = 第 (n-k) 小 ⇒ 目标下标 target = 9 - 4 = 5（0-based）。

主流程（findKthLargest）

初始化：

1
left = 0, right = 8, target = 5

进入循环，每轮做一次 partition(nums, left, right)，得到一个基准元素的最终位置 p：

  • 若 p == target，答案就是 nums[p]；
  • 若 p < target，目标在右半边：left = p + 1；
  • 若 p > target，目标在左半边：right = p - 1。

第 1 轮 partition（区间 [0, 8]）

当前数组：
[3, 2, 3, 1, 2, 4, 5, 5, 6]

  1. 选随机基准 pivotIdx。假设抽到 pivotIdx = 4（值为 2）。
    交换到末尾： swap(4, 8) → [3, 2, 3, 1, 6, 4, 5, 5, 2] pivot = 2

  2. i 从 l 开始，j 从 l 扫到 r-1，维护不变式：

    1
    a[l..i-1] < pivot
    • j=0: a[0]=3 < 2 ? 否 → 不动
    • j=1: a[1]=2 < 2 ? 否 → 不动
    • j=2: a[2]=3 < 2 ? 否 → 不动
    • j=3: a[3]=1 < 2 ? 是 → swap(0,3)，i++ → [1, 2, 3, 3, 6, 4, 5, 5, 2] i=1
    • j=4..7: 6/4/5/5 都不小于 2 → 不动

  3. 把 pivot 放回它的最终位置 i： swap(i=1, r=8) → [1, 2, 3, 3, 6, 4, 5, 5, 2] // a[1] 本来就是 2，交换等于不变

  4. 返回 p = 1

回到主循环：

1
2
3
p = 1, target = 5
p < target → left = p + 1 = 2
现在区间缩小为 [2, 8]

第 2 轮 partition（区间 [2, 8]）

当前数组：
[1, 2, 3, 3, 6, 4, 5, 5, 2]

  1. 选随机基准。假设抽到 pivotIdx = 6（值为 5）。
    交换到末尾： swap(6, 8) → [1, 2, 3, 3, 6, 4, 2, 5, 5] pivot = 5
  2. i = 2；j=2..7 扫描：
    • j=2: a[2]=3 < 5 ? 是 → swap(2,2)（等于不动），i=3
    • j=3: a[3]=3 < 5 ? 是 → swap(3,3)（不动），i=4
    • j=4: a[4]=6 < 5 ? 否 → 不动
    • j=5: a[5]=4 < 5 ? 是 → swap(4,5)，i=5 → [1, 2, 3, 3, 4, 6, 2, 5, 5]
    • j=6: a[6]=2 < 5 ? 是 → swap(5,6)，i=6 → [1, 2, 3, 3, 4, 2, 6, 5, 5]
    • j=7: a[7]=5 < 5 ? 否 → 不动
  3. 放回 pivot： swap(i=6, r=8) → [1, 2, 3, 3, 4, 2, 5, 5, 6]
  4. 返回 p = 6

回到主循环：

1
2
3
p = 6, target = 5
p > target → right = p - 1 = 5
现在区间缩小为 [2, 5]

第 3 轮 partition（区间 [2, 5]）

当前数组：
[1, 2, 3, 3, 4, 2, 5, 5, 6]

  1. 随机基准。假设 pivotIdx = 3（值为 3）。
    交换到末尾： swap(3, 5) → [1, 2, 3, 2, 4, 3, 5, 5, 6] pivot = 3
  2. i = 2；j=2..4：
    • j=2: a[2]=3 < 3 ? 否
    • j=3: a[3]=2 < 3 ? 是 → swap(2,3)，i=3 → [1, 2, 2, 3, 4, 3, 5, 5, 6]
    • j=4: a[4]=4 < 3 ? 否
  3. 放回 pivot： swap(i=3, r=5) → 等于不动
  4. 返回 p = 3

回到主循环：

1
2
3
p = 3, target = 5
p < target → left = p + 1 = 4
现在区间缩小为 [4, 5]

第 4 轮 partition（区间 [4, 5]）

当前数组：
[1, 2, 2, 3, 3, 4, 5, 5, 6]

  1. 随机基准。假设 pivotIdx = 4（值为 3）。
    交换到末尾： swap(4, 5) → [1, 2, 2, 3, 4, 3, 5, 5, 6] pivot = 3
  2. i = 4；j=4..4：
    • j=4: a[4]=4 < 3 ? 否
  3. 放回 pivot： swap(i=4, r=5) → [1, 2, 2, 3, 3, 4, 5, 5, 6]
  4. 返回 p = 4 —— 嗯，这里我按“随机=4”其实 pivot=3，最终 p=4。
    但我们上面想得到 target=5，需要第 5 位。
    接着再来一轮（也可能 pivotIdx 选成 5，下面给的是另一种等价轨迹，能直接到答案）：

为了和上面的完整演示收敛到结果，这一步换个同样合理的随机：
若 pivotIdx = 5（值为 4），交换后数组：

1
2
3
4
5
swap(5, 5) → 不变
pivot = 4, i=4, j=4..4
j=4: a[4]=3 < 4 ? 是 → swap(4,4) 不变，i=5
swap(i=5, r=5) 不变
返回 p = 5

这时 p == target(5)，返回 nums[5]。

最终答案：nums[5] = 4，与题意示例一致（第 4 大是 4）。

代码里两处关键点再解释一下

  • 为什么 target = n - k？
    按升序排序后，第 k 大的元素位于 0-based 下标 n-k（例如 n=9、k=4 ⇒ 第 5 个（下标 5））。
  • 为什么用 ThreadLocalRandom？
    它是更轻量的每线程单例随机数生成器，避免了 new Random() 的共享竞争与额外开销，并且有方便的 nextInt(l, r+1)（左闭右开区间）形式，写起来也不容易越界。

方法2：

好问题 👍，我来详细讲讲这段 Solution1 代码是如何实现「数组中第 k 个最大元素」的。

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
class Solution{
    private int quickSelect(List<Integer> nums, int k) {
         //随机选择基准数
        Random random = new Random();
        int pivot = nums.get(random.nextInt(nums.size()));
        //分区，将大于，小于，等于pivot的元素划分到big，small，equal中
        List<Integer> big = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        for (int num : nums) {
            //num > pivot, num < pivot, num == pivot分别划分到对应的分区
            if (num > pivot) {
                big.add(num);
            } else if (num < pivot) {
                small.add(num);
            } else {
                equal.add(num);
            }
        }
        //将第k大的元素在big中递归划分
        if (k <= big.size()) {
            return quickSelect(big, k);
        }
        //如果k在small中，则在small中进行递归划分
         if (big.size() + equal.size() < k) {
            return quickSelect(small, k - (big.size() + equal.size()));
        }
        //如果k在equal中，则直接返回pivot
        return pivot;
    }

    //查找数组中的第k大元素
    public int findKthLargest(int[] nums, int k) {
        List<Integer> numsList = new ArrayList<>();
        for (int num : nums) {
            numsList.add(num);
        }
        return quickSelect(numsList, k);
    }
}

整体思路

这个解法基于 QuickSelect（快速选择算法） 的思想，但是实现方式比较“函数式”，它并没有原地交换数组，而是通过不断划分 List<Integer> 来缩小问题规模，直到找到第 k 大的数。

核心步骤：

  1. 随机选一个基准数（pivot）
    保证平均情况下划分比较均匀，避免退化到 O(n²)。

  2. 分区（Partition）

    遍历数组，把元素分成三类：

    • big：大于 pivot 的数
    • equal：等于 pivot 的数
    • small：小于 pivot 的数

  3. 递归选择
    根据 k 落在哪个区间，递归到对应的区间继续找，直到找到第 k 大。

代码逐行解释

quickSelect 方法

1
2
3
4
private int quickSelect(List<Integer> nums, int k) {
    //随机选择基准数
    Random random = new Random();
    int pivot = nums.get(random.nextInt(nums.size()));

👉 在 nums 中随机选一个数作为 pivot。
比如 nums = [3,2,1,5,6,4]，随机选中 pivot = 5。

1
2
3
4
5
6
7
8
9
10
11
12
13
//分区
List<Integer> big = new ArrayList<>();
List<Integer> small = new ArrayList<>();
List<Integer> equal = new ArrayList<>();
for (int num : nums) {
    if (num > pivot) {
        big.add(num);
    } else if (num < pivot) {
        small.add(num);
    } else {
        equal.add(num);
    }
}

👉 遍历数组，把数分成三类。
假设 pivot = 5，nums = [3,2,1,5,6,4]

  • big = [6]
  • equal = [5]
  • small = [3,2,1,4]
1
2
3
4
// 如果第k大在big中
if (k <= big.size()) {
    return quickSelect(big, k);
}

👉 如果 big 里元素个数 ≥ k，说明第 k 大一定在 big 里。
递归到 big 子数组继续找。

1
2
3
4
// 如果第k大在small中
if (big.size()+equal.size()<k) {
    return quickSelect(small, k - (big.size()+equal.size()));
}

👉 如果 第k> big.size()+equal.size() 区间，说明第 k 大在 small 中。

  • k - (big.size()+equal.size()) 的原因：要排除掉等于 pivot 的部分。
1
2
3
    // 如果第k大在equal中，直接返回pivot
    return pivot;
}

👉 如果既不在 big，也不在 small，那就一定在 equal 中，直接返回 pivot。

findKthLargest 方法

1
2
3
4
5
6
7
public int findKthLargest(int[] nums, int k) {
    List<Integer> numsList = new ArrayList<>();
    for (int num : nums) {
        numsList.add(num);
    }
    return quickSelect(numsList, k);
}

👉 这里只是把数组转成 List<Integer>，然后调用 quickSelect。

示例走一遍

输入：

1
nums = [3,2,1,5,6,4], k = 2

执行流程：

  1. pivot 随机取 5。

    • big = [6]
    • equal = [5]
    • small = [3,2,1,4]

  2. k=2, big.size()=1，不够 → 往 small/equal 方向看
    equal.size()=1, small.size()=4 → k >！>equal+big=2
    所以k在equal

  3. 也就是5

最终结果：5 ✅

总结

  • 这个实现利用 分治思想，每次随机选 pivot，把问题缩小。
  • 平均时间复杂度 O(n)，空间复杂度 O(n)（因为用了三个 List 存储分区）。
  • 和原地交换的 快速选择算法 相比，它写法更直观，但内存开销更大。

70.前K个高频元素（中等 堆）

img

Stream流的方式，优点代码量少缺点运行时间长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //统计每一个数字出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        //遍历数组，统计每个数字出现的次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //根据数字出现的次数进行排序,取出前k个高频元素并获取key最后收集到数组中
        int[] array = map.entrySet().stream()
                .sorted((e1, e2) -> e2.getValue() - e1.getValue())
                .limit(k)
                .mapToInt(Map.Entry::getKey)
                .toArray();
        return array;
    }
}

优先队列

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[] topKFrequent(int[] nums, int k) {
       Map<Integer,Integer>map = new HashMap<>();//统计每个元素出现的次数
        //遍历数组，统计每个元素出现的次数,默认值为0
       for(int num:nums){
           map.put(num,map.getOrDefault(num,0)+1);
       }
       //构建一个小顶堆，按照频次升序排列
        PriorityQueue<int[]>head = new PriorityQueue<>((a,b)->a[1]-b[1]);//小顶堆：按频次升序
        //将元素加入到小顶堆中，如果堆的大小超过k，则移除堆顶的元素
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            head.offer(new int[]{entry.getKey(), entry.getValue()});
            if(head.size()>k){
                head.poll();
            }
        }
        //将堆中的元素放入结果数组中
        int[]res = new int[k];
        //堆顶元素即为频次最高的元素，依次取出放入结果数组中
        for(int i=k-1;i>=0;i--){
            res[i] = head.poll()[0];
        }
        return res;
    }

}
  • 只保留频次最大的 k 个元素在堆里；
  • 复杂度 O(n log k)，空间 O(n)。

img

71.单词拆分（中等 动态规划）

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 boolean wordBreak(String s, List<String> wordDict) {
        //放到HashSet中，便于快速查找
        Set<String> set = new HashSet<>(wordDict);
        int n = s.length();//字符串长度
        boolean[] dp = new boolean[n + 1];//dp[i]表示s的前i个字符是否可以拆分
        dp[0] = true;//初始化，空字符串可以拆分
        //遍历字符串s，枚举分割点j
        for (int i = 1; i <= n; i++) {
            //如果前j个字符可以拆分，并且s[j,i)在字典中存在
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    //那么s的前i个字符也可以拆分，更新dp[i]为true
                    dp[i] = true;
                    break;//跳出内层循环，因为我们已经找到了一个可行的拆分方式
                }
            }

        }
        return dp[n];
    }
}

我们就用打断点的方式（相当于调试 step by step）走一遍代码。我用例子：

1
s = "leetcode", wordDict = ["leet","code"]

初始状态

1
2
3
4
Set<String> set = {"leet", "code"};
n = 8;
boolean[] dp = new boolean[9]; // 长度 = n+1
dp[0] = true;

此时：

1
dp = [true, false, false, false, false, false, false, false, false]

外层循环 i=1

  • j=0：
    dp[0] && s.substring(0,1)="l" in set? → false
    → dp[1] 还是 false
1
dp = [true, false, false, false, false, false, false, false, false]

i=2

  • j=0: “le” → 不在字典
  • j=1: “e” → 不在字典
    → dp[2] = false
1
dp = [true, false, false, false, false, false, false, false, false]

i=3

  • j=0: “lee” → 不在字典
  • j=1: “ee” → 不在字典
  • j=2: “e” → 不在字典
    → dp[3] = false
1
dp = [true, false, false, false, false, false, false, false, false]

i=4

  • j=0:
    dp[0]=true && "leet" ∈ set ✅ → dp[4]=true
    （直接 break 掉内层循环）
1
dp = [true, false, false, false, true, false, false, false, false]

i=5

  • j=0: “leetc” 不在
  • j=1: “eetc” 不在
  • j=2: “etc” 不在
  • j=3: “tc” 不在
  • j=4: dp[4]=true, “c” 不在
    → dp[5] = false
1
dp = [true, false, false, false, true, false, false, false, false]

i=6

类似，”co”/“ode” 都不在字典 → dp[6]=false

i=7

类似，”cod” 不在字典 → dp[7]=false

i=8

  • j=4:
    dp[4]=true && "code" ∈ set ✅ → dp[8]=true
1
dp = [true, false, false, false, true, false, false, false, true]

最终结果

1
dp[8] = true` → 返回 `true

💡 你可以看到断点流程：

  • 每个 i 就像检查前缀能不能拼出来
  • 当走到 i=4 时发现 “leet”
  • 当走到 i=8 时发现 “code”
  • 所以整体能拆分。
i (前缀长度) s[0..i-1] 前缀 j=0 检查 j=1 检查 j=2 检查 j=3 检查 j=4 检查 结果 dp[i]
0 “” - - - - - true (初始化)
1 “l” “l” ❌ false
2 “le” “le” ❌ “e” ❌ false
3 “lee” “lee” ❌ “ee” ❌ “e” ❌ false
4 “leet” “leet” ✅ → dp[4]=true 不用继续 true
5 “leetc” “leetc” ❌ “eetc” ❌ “etc” ❌ “tc” ❌ “c” ❌ false
6 “leetco” … … … … “co” ❌ false
7 “leetcod” … … … … “cod” ❌ false
8 “leetcode” … … … “code” ✅ (dp[4]=true) true

72.最长递增子序列（中等 动态规划）

img

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 lengthOfLIS(int[] nums) {
        //边界条件判断
       if(nums==null||nums.length==0) return 0;
       int n=nums.length;
       int[]dp = new int[n];//dp[i]表示以nums[i]结尾的最长递增子序列的长度
        //初始化dp数组
        for(int i=0;i<n;i++){
            dp[i]=1;
            //遍历dp数组，更新dp[i]的值
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        //找到dp数组中的最大值
        int max=0;
        for(int i=0;i<n;i++){
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}

核心逻辑回顾

  • dp[i]：以 nums[i] 结尾的最长递增子序列长度。
  • 状态转移： java复制编辑if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); }
  • 最终答案：dp[] 数组的最大值。
i nums[i] dp[i] 对应递增子序列（示例）
0 10 1 [10]
1 9 1 [9]
2 2 1 [2]
3 5 2 [2,5]
4 3 2 [2,3]
5 7 3 [2,3,7]
6 101 4 [2,3,7,101]
7 18 4 [2,3,7,18]

73.乘积最大子数组（中等 动态规划）

正确思路（O(n)，Kadane 变体）

设：

  • maxProd：以当前位置为结尾的最大乘积
  • minProd：以当前位置为结尾的最小乘积（最负）
  • ans：全局最大

转移：

  • 如果 nums[i] 为负数，maxProd 和 minProd 交换（因为乘以负数正负会互换）
  • 然后：maxProd = Math.max(nums[i], maxProd * nums[i]); minProd = Math.min(nums[i], minProd * nums[i]); ans = Math.max(ans, maxProd);
  • 遇到 0 时，这两者都会被重置为 0（在上面的式子中自然体现：max(0, 0*东西)），下一位再从自身重新开始。

正确代码（Java）

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 maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;//数组长度
        int maxProduct = nums[0];//最大乘积
        int minProduct = nums[0];//最小乘积
        int result = nums[0];
        //i！=0，因为第一个元素已经被初始化了
        for (int i = 1; i < n; i++) {
            if (nums[i] < 0) {//如果当前元素为负数，则交换最大最小乘积
                int temp = maxProduct;
                maxProduct = minProduct;
                minProduct = temp;
            }
            //更新最大最小乘积
            maxProduct = Math.max(nums[i], maxProduct * nums[i]);
            minProduct = Math.min(nums[i], minProduct * nums[i]);
            result = Math.max(result, maxProduct);
        }
        return result;
    }
}

简短示例走一遍

1
nums = [2, 3, -2, 4]
  • 初始：maxProd = 2, minProd = 2, ans = 2
  • i=1, x=3：
    maxProd = max(3, 2*3)=6，minProd = min(3, 2*3)=6，ans=6
  • i=2, x=-2（负数，交换）：
    交换后：maxProd=6, minProd=6（这里两者相等）
    maxProd = max(-2, 6*(-2)) = max(-2, -12) = -2
    minProd = min(-2, 6*(-2)) = -12
    ans = max(6, -2) = 6
  • i=3, x=4：
    maxProd = max(4, -2*4)=max(4, -8)=4
    minProd = min(4, -12*4) = -48
    ans = max(6, 4) = 6
    最终答案 6（子数组 [2,3]）。

74.分割等和子集（中等 动态规划）

我们可以从 0−1背包的角度来看。将 target看作背包容量，每个 nums[i] 是物品的价值以及重量。

问题转化 为：一共 n 个物品，每个物品只能选择一次，背包容量为 target，判断背包的总价值能否达到 target。

同理，定义 dp[i][j] 表示将前 i个物品装入背包，背包容量为 j时，背包能得到的最大价值。

状态转移方程：

img

img

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 boolean canPartition(int[] nums) {
        int sum =0;
        for (int num : nums) {
            sum += num;
        }

        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        //dp[j] 表示背包容量为j时，能否凑出总和为j的组合
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;//初始化
        for (int num : nums) {
            //从target倒序遍历，保证每个物品只用一次
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];//要么不装，要么装上
            }
            //剪枝，如果找到了就直接返回
            if(dp[target]) return true;
            //如果背包容量为0，但是没有找到总和为target的组合，则返回false(背包容量为0，但是总和不为0，说明总和不可能凑出)
        }
        return dp[target];
    }
}

75不同路径（中等 多维动态规划）

img

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 uniquePaths(int m, int n) {
        if(m == 0 || n == 0) return 0;
        int[][] dp = new int[m][n];//初始化dp数组
        //初始化第一列
        for(int i = 0;i < m;i++){
            dp[i][0] = 1;
        }
        //初始化第一行
        for(int j = 0;j < n;j++){
            dp[0][j] = 1;
        }
        //填充dp数组
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

76.最小路径和（中等 多维动态规划）

img

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
class Solution {
    public int minPathSum(int[][] grid) {
       if(grid == null || grid.length == 0) {
           return 0;
       }
       int m = grid.length; //行数
       int n = grid[0].length;//列数
        //初始化第一列
       for(int i = 1; i < m; i++) {
           grid[i][0] += grid[i-1][0];
       }
       //初始化第一行
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j-1];
        }
        //动态规划
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                //当前位置的最小路径和等于左边或者上边的最小路径和加上当前位置的数
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int m = grid.length; //行数
        int n = grid[0].length;//列数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue; //左上角，不用处理
                else if (i == 0) grid[i][j] += grid[i][j - 1];//第一行，只能从左边来
                else if (j == 0) grid[i][j] += grid[i - 1][j];//第一列，只能从上边来
                else {
                    grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
                }
            }
        }
        return grid[m - 1][n - 1];
    }
}

img

77.最长回文子串（中等）

img

思路里最实用、代码最短也最不易错的是中心扩展（Expand Around Center）：

核心想法

回文串绕着“中心”对称。中心有两种：

  • 单字符中心：如 aba（奇数长度）
  • 双字符中心：如 abba（偶数长度）

我们把每个位置都当作中心，向两边同时扩展，遇到不相等就停下。记录扩展出的最长回文区间。

时间复杂度：O(n²)（最坏），空间 O(1)
n ≤ 1000 时完全可过，且实现简单可靠。

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 String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        int bestL = 0, bestR = 0;// 最长回文子串的左右边界
        // 枚举中心点，枚举回文串的长度
        for (int i = 0; i < n; i++) {
            //以s[i]为中心（奇数长度）
            int[] p1 = expand(s, i, i);
            //以s[i]和s[i+1]为中心（偶数长度）
            int[] p2 = expand(s, i, i + 1);
            // 取最长的回文子串
            if (p1[1] - p1[0] > bestR - bestL) {
                bestL = p1[0];
                bestR = p1[1];
            }
            // 取最长的回文子串
            if (p2[1] - p2[0] > bestR - bestL) {
                bestL = p2[0];
                bestR = p2[1];
            }

        }
        // 返回最长回文子串
        return s.substring(bestL, bestR + 1);
    }
    private int[] expand (String s,int L, int R){
        //当L和R指向同一个字符时，L向左移动到边界，R向右移动到边界
      while(L>=0 && R<s.length() && s.charAt(L)==s.charAt(R)){
        --L;
        ++R;
      }
      //返回回文子串的左右边界
      return new int[]{L+1,R-1};
    }
}

另一种中心扩展法 来解决 最长回文子串 问题。

🔑 思路回顾

  • 回文串：正着读和反着读一样。

  • 中心扩展法

    ：回文串的对称性决定了它一定有一个“中心”。

    • 奇数回文：如 "aba"，中心是 b
    • 偶数回文：如 "abba"，中心是 bb

  • 遍历每个字符，把它当作回文中心，分别往两边扩展，看能扩展到多长。

📝 代码讲解

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 String longestPalindrome(String s) {
         if(s.length() < 2) return s;
         int maxLen = 1; // 初始化最长回文子串的长度，至少为 1
         int begin = 0;  // 记录最长回文子串的起始下标
         char[] chars = s.toCharArray();

         // 遍历所有可能的回文中心
         for(int i = 0; i < chars.length - 1; i++){
             // 情况1：以 i 作为中心（奇数回文）
             int len1 = expandAroundCenter(chars,i,i);
             // 情况2：以 i 和 i+1 作为中心（偶数回文）
             int len2 = expandAroundCenter(chars,i,i+1);

             // 取两者中的最大长度
             int len = Math.max(len1,len2);

             // 如果发现更长的回文，更新起始位置和最大长度
             if(len > maxLen){
                 begin = i - (len-1)/2;
                 maxLen = len;
             }
         }
         // substring 的右边界是开区间，所以要写 begin + maxLen
         return s.substring(begin, begin + maxLen);
    }

    // 中心扩展函数：返回以 left 和 right 为中心的最长回文子串长度
    private int expandAroundCenter(char[] chars,int left,int right){
        while (left >= 0 && right < chars.length && chars[left] == chars[right]){
            --left;
            ++right;
        }
        // 跳出循环时，left 和 right 分别越界或不相等
        // 有效回文串的长度 = (right-1) - (left+1) + 1 = right-left-1
        return right - left - 1;
    }
}

📊 举例走一遍

输入：

1
s = "babad"

第一步：初始化

  • maxLen = 1
  • begin = 0
  • 遍历每个字符 i

第二步：遍历

  • i = 0 (b)

    • len1 = 1 ("b")
    • len2 = 0 ("")
    • 最大 = 1，不更新

  • i = 1(a)

    • len1 = 3 ("bab")
    • len2 = 0
    • 最大 = 3 > 1，更新：
      • begin = 1 - (3-1)/2 = 0
      • maxLen = 3

  • i = 2 (b)

    • len1 = 3 ("aba")
    • len2 = 0
    • 最大 = 3，等于 maxLen，不更新

  • 继续扫描… 最长子串始终 "bab" 或 "aba"

第三步：结果

  • substring(0, 0+3) = "bab"

✅ 总结

  • 这段代码用 中心扩展法，复杂度是 O(n²)，空间是 O(1)。
  • 思路很直观：从每个位置开始，往两边扩展，找到所有可能的回文串，再记录最长的。

要不要我帮你画一个 二维表格（索引 × 回文中心扩展结果），一步步展示 "babad" 的中心扩展过程？这样你能更清楚看到每一步最长回文是怎么更新的。

78.最长公共子序列（中等 多维动态规划）

img

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 longestCommonSubsequence(String text1, String text2) {
        if (text1.length() == 0 || text2.length() == 0) return 0;
        //初始化dp数组，dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列的长度
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        //遍历字符串，填充dp数组
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                //如果当前字符相等，则最长公共子序列长度加1
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                //否则，取前一个字符的最长公共子序列长度和当前字符的前一个字符的最长公共子序列长度的最大值
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        //返回dp数组的最后一个元素，即text1和text2的最长公共子序列的长度
        return dp[text1.length()][text2.length()];
    }
}

这段代码是在用滚动数组的一维 DP来求两个字符串的最长公共子序列（LCS）。先给出标准二维写法，再解释它是如何被压缩到一维的，以及代码里 leftup、nextLeftup 的作用。

1）标准二维 DP（便于理解）

设
dp[i+1][j+1] = text1[0..i] 与 text2[0..j] 的 LCS 长度。

状态转移：

  • 若 text1[i] == text2[j]，这个字符可以作为公共子序列的一部分：
    dp[i+1][j+1] = dp[i][j] + 1
  • 否则只能继承较长的那个：
    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

边界：dp[0][*] = 0, dp[*][0] = 0。

2）滚动数组（一维 DP）如何实现

我们只保留上一行的信息，将二维压缩成长度为 n+1 的一维数组 dp（n = text2.length()）：

  • 在外层遍历 i（text1 的下标），每一轮都会把 dp 更新为“第 i+1 行”的值；
  • 在内层遍历 j，从左到右更新 dp[j+1]。

关键是：在更新 dp[j+1] 时，我们需要用到左上角 dp[i][j]（二维定义里的）。
此时：

  • dp[j+1]（更新前）其实是上一行的 dp[i][j+1]
  • dp[j]（已经被本行更新）是当前行的 dp[i+1][j]
  • leftup 用来保存“上一行的 dp[i][j]”（也就是二维里的左上角）
  • nextLeftup = dp[j+1] 在覆盖 dp[j+1] 之前，先把它（上一行的 dp[i][j+1]）存起来，给下一个 j 当作左上角使用

于是转移式在一维里变成：

1
2
3
4
5
if (text1[i] == text2[j])
    dp[j+1] = 1 + leftup;       // 左上 + 1
else
    dp[j+1] = Math.max(dp[j+1], dp[j]); // max(上一行同列, 本行前一列)
leftup = nextLeftup;            // 准备给下一个 j 用

3）逐步模拟（text1=”abcde”, text2=”ace”）

初始化：dp = [0, 0, 0, 0]，对应 j=-1,0,1,2（方便处理空前缀）

  • i=0（’a’）
    • j=0（’a’）：相等 → dp[1]=leftup+1=1；更新 leftup=旧dp[1]=0
    • j=1（’c’）：不等 → dp[2]=max(旧dp[2]=0, dp[1]=1)=1；leftup=旧dp[2]=0
    • j=2（’e’）：不等 → dp[3]=max(0, dp[2]=1)=1；leftup=旧dp[3]=0
      dp = [0,1,1,1]
  • i=1（’b’）：
    • j=0：不等 → dp[1]=max(1,0)=1；leftup=旧dp[1]=1
    • j=1：不等 → dp[2]=max(1, dp[1]=1)=1；leftup=旧dp[2]=1
    • j=2：不等 → dp[3]=max(1, dp[2]=1)=1；leftup=旧dp[3]=1
      dp = [0,1,1,1]
  • i=2（’c’）：
    • j=0：不等 → dp[1]=max(1,0)=1；leftup=旧dp[1]=1
    • j=1：相等 → dp[2]=leftup+1=2；leftup=旧dp[2]=1
    • j=2：不等 → dp[3]=max(1, dp[2]=2)=2；leftup=旧dp[3]=1
      dp = [0,1,2,2]
  • i=3（’d’）：
    • 更新后仍为 dp = [0,1,2,2]
  • i=4（’e’）：
    • j=0：不等 → dp[1]=1
    • j=1：不等 → dp[2]=2
    • j=2：相等 → dp[3]=leftup+1=3（此时 leftup 是上一行的 dp[2]=2）
      dp = [0,1,2,3]

最终返回 dp[n] = dp[3] = 3。

4）复杂度

  • 时间：O(m * n)
  • 空间：O(n)（滚动数组）

5）把代码和上面的解释对上

1
2
3
4
5
6
7
8
9
10
11
12
int[] dp = new int[n+1];  // 一维滚动：dp[j+1] 表示“当前行”的值，初始化为 0
for (int i = 0; i < m; i++) {
    int leftup = dp[0];   // 即二维的 dp[i][0]，为 0
    for (int j = 0; j < n; j++) {
        int nextLeftup = dp[j+1];  // 更新前保存“上一行的 dp[i][j+1]”，下轮当左上角
        dp[j+1] = (text1.charAt(i) == text2.charAt(j))
                  ? leftup + 1
                  : Math.max(dp[j+1], dp[j]);
        leftup = nextLeftup;       // 滚动左上角
    }
}
return dp[n];

只要把“二维版的三种位置关系”在脑子里对应好（上、左、左上），你就能看懂这段一维 DP：

  • dp[j+1] 更新前 = 上
  • dp[j]（本行已更新）= 左
  • leftup = 左上（上一轮保存的）

这样就完全等价于二维 DP 的写法了。

79.编辑距离（中等 多维动态规划）

img

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 int minDistance(String word1, String word2) {
        //如果word1和word2相等，则不需要进行任何操作
        if(word1.equals(word2)) {
            return 0;
        }
        //如果word1为空，则需要进行插入操作
        if(word1.length() == 0) {
            return word2.length();
        }
        //如果word2为空，则需要进行删除操作
        if(word2.length() == 0) {
            return word1.length();
        }
        //创建一个二维数组，用于存储word1和word2的编辑距离
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        //初始化第一行和第一列
        for(int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for(int j = 0; j <= word2.length(); j++) {
            dp[0][j] = j;
        }
        //遍历word1和word2，计算编辑距离
        for(int i = 1; i <= word1.length(); i++) {
            for(int j = 1; j <= word2.length(); j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(Math
                            .min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }

}

你这份代码实现的是 编辑距离（Levenshtein Distance） 的经典动态规划解法，我给你分两步讲清楚：

🔹代码逻辑解析

  1. 特殊情况处理

    • 如果 word1 == word2，返回 0（不需要操作）。
    • 如果 word1 为空，结果就是 word2.length()（全靠插入）。
    • 如果 word2 为空，结果就是 word1.length()（全靠删除）。

  2. DP 数组定义

    • dp[i][j] 表示 word1 的前 i 个字符 和 word2 的前 j 个字符 的最小编辑距离。
    • 数组大小 (len1+1) * (len2+1)，因为我们要考虑空串情况。

  3. 初始化

    • dp[i][0] = i：word1 转换成空串，需删除 i 个字符。
    • dp[0][j] = j：空串转换成 word2，需要插入 j 个字符。

  4. 状态转移方程

    • 如果 word1[i-1] == word2[j-1] → 不需要操作 dp[i][j] = dp[i-1][j-1];

    • 否则 → 取三种操作的最小值：

      • 插入：dp[i][j-1] + 1
      • 删除：dp[i-1][j] + 1
      • 替换：dp[i-1][j-1] + 1
      1
      dp[i][j] = Math.min(Math.min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+1);

🔹示例 1

输入：

1
word1 = "horse", word2 = "ros"

我们画出 DP 表格（行：word1，列：word2）：

i j “” r ro ros
“” 0 1 2 3
h 1 1 2 3
ho 2 2 1 2
hor 3 2 2 2
hors 4 3 3 2
horse 5 4 4 3

最终答案：dp[5][3] = 3

对应操作路径：

  • horse → rorse （替换 h → r）
  • rorse → rose （删除 r）
  • rose → ros （删除 e）

🔹示例 2

输入：

1
word1 = "intention", word2 = "execution"

DP 表太大我就不完全画了，但结果是 dp[9][9] = 5，操作过程：

  1. intention → inention （删 t）
  2. inention → enention （i → e）
  3. enention → exention （n → x）
  4. exention → exection （n → c）
  5. exection → execution （插入 u）

✅ 总结：

  • DP 表的本质就是 逐步缩小问题规模，把大问题拆成小问题。
  • 表格里每一格 dp[i][j] 记录的是“前 i 个字符”和“前 j 个字符”变成一样所需的最小操作数。

思路2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    char[] w1, w2;
    Integer[][] memo;
    public int minDistance(String word1, String word2) {
        w1 = word1.toCharArray();
        w2 = word2.toCharArray();
        int len1 = word1.length(), len2 = word2.length();
        memo = new Integer[len1][len2];
        return dfs(len1 - 1, len2 - 1);
    }
    private int dfs(int i, int j){
        if(i < 0) return j + 1;
        if(j < 0) return i + 1;
        if(memo[i][j] != null) return memo[i][j];
        memo[i][j] = w1[i] == w2[j] ? dfs(i - 1, j - 1) : Math.min(dfs(i-1, j-1), Math.min(dfs(i - 1, j), dfs(i, j - 1))) + 1;
        return memo[i][j];
    }
}

你这份代码用的是 递归 + 记忆化搜索（Top-down DP） 的写法，和之前二维 DP 表的思路是一致的，只是换了一种实现方式。
我帮你拆解一下：

🔹思路核心

  1. 递归定义

    dfs(i, j)表示 word1[0..i] 转换为 word2[0..j] 的最小编辑距离。

    • 如果 i < 0，说明 word1 已经用完，只能插入剩下的 j+1 个字符。
    • 如果 j < 0，说明 word2 已经用完，只能删除剩下的 i+1 个字符。

  2. 状态转移

    • 如果 w1[i] == w2[j] → 不需要操作，递归到 dfs(i-1, j-1)。
    • 否则 → 三种操作取最小值 + 1：
      • 替换：dfs(i-1, j-1)
      • 删除：dfs(i-1, j)
      • 插入：dfs(i, j-1)
    1
    memo[i][j] = w1[i] == w2[j] ? dfs(i-1, j-1) : Math.min(dfs(i-1, j-1), Math.min(dfs(i-1, j), dfs(i, j-1))) + 1;

  3. 记忆化缓存

    • 用 memo[i][j] 缓存子问题结果，避免重复计算。
    • 如果已经算过，就直接返回。

🔹代码运行过程举例

以 word1 = "horse"，word2 = "ros" 为例：

  • 递归树最顶层是 dfs(4, 2) → 对应 word1="horse", word2="ros"

  • 因为 e != s，所以需要考虑三种操作：

    • 替换 dfs(3,1)
    • 删除 dfs(3,2)
    • 插入 dfs(4,1)

逐层递归下去，最终会走到边界情况（i < 0 或 j < 0），然后逐步返回。
同时，由于 memo 缓存，重复子问题只会计算一次。

最后返回结果：3。

🔹与二维 DP 的区别

  • 二维 DP（Bottom-up）
    • 从小问题开始，逐步填表，直到最终答案。
    • 优点：迭代更直观，容易画表格。
    • 缺点：必须额外开一个二维数组。
  • 递归 + 记忆化（Top-down）
    • 从大问题出发，递归拆分为子问题。
    • 优点：写法简洁，符合思维逻辑。
    • 缺点：递归开销大，如果没有 memo 会超时。

✅ 总结：
这份代码就是用 dfs(i, j) 表示前缀的最小编辑距离，
通过递归去解决问题，并用 memo 避免重复计算，
实质上和二维 DP 是完全等价的。

要不要我帮你把这个 递归搜索过程（以 horse → ros 为例）画成一棵递归调用树？这样你能直观看到每一步怎么拆分。

80.颜色分类（中等 技巧）

img

你这段就是著名的「荷兰国旗问题」解法（Dutch National Flag），用三指针一次扫描把 0/1/2 原地排成 0、1、2 的顺序。思路既直观又高效：O(n) 时间、O(1) 额外空间，不调用 sort。

核心指针与不变量

  • s（start）：左边界，维护区间 [0 .. s-1] 都是 0
  • i（index）：当前扫描位置
  • n（end）：右边界，维护区间 [n+1 .. 末尾] 都是 2

因此任意时刻数组被分成 4 段：

1
2
3
4
[ 0区 | 未处理 | 2区 ]
0区: [0 .. s-1] 全是 0
未处理: [s .. i-1] 已处理为 1；[i .. n] 未检查
2区: [n+1 .. end] 全是 2

初始化：s = 0, i = 0, n = nums.length - 1

扫描规则（while/for 都可，本质一样）

对 i 从左向右处理，直到 i > n：

  1. nums[i] == 0：把它丢到最左边

    • swap(nums, s, i)，然后 s++，i++
    • 理由：交换后 i 位置是旧的 nums[s]，但 s 左侧保证全 0，且被换来的元素至多是 1（因为 2 会被放在右端），而 i 右移继续安全

  2. nums[i] == 2：把它丢到最右边

    • swap(nums, n, i)，然后 n--，但 i 不动
    • 理由：右端 n 位置换过来的数还没检查（可能是 0/1/2），所以要继续用同一个 i 重新判断一次

  3. nums[i] == 1：本来就应该在中间

    • i++ 即可

这三条保证每一步都在扩大“已归位”的 0 区/2 区，缩小“未处理区”。

举例走一遍：[2,0,2,1,1,0]

初始：s=0, i=0, n=5

1
2
3
4
5
6
7
8
i=0: nums[i]=2 → 与 n 交换 → [0,0,2,1,1,2], n=4, i=0（不动）
i=0: nums[i]=0 → 与 s 交换(同位置) → [0,0,2,1,1,2], s=1, i=1
i=1: nums[i]=0 → 与 s 交换(同位置) → [0,0,2,1,1,2], s=2, i=2
i=2: nums[i]=2 → 与 n 交换 → [0,0,1,1,2,2], n=3, i=2（不动）
i=2: nums[i]=1 → i=3
i=3: nums[i]=1 → i=4
结束条件：i(4) > n(3) ⇒ done
结果：[0,0,1,1,2,2]

为什么交换 2 时不递增 i？

因为从右侧 n 换来的元素还没经过检查，可能是 0，如果你此时 i++，就会跳过这个新换过来的 0，导致 0 被留在中间，排序错误。保持 i 不动能立刻在下一轮把它继续分类。

复杂度

  • 时间：每个元素最多被交换/访问常数次，O(n)
  • 空间：只用常数指针，O(1)

代码要点回顾（与你的一致）

1
2
3
4
5
6
7
8
9
10
11
12
13
public void sortColors(int[] nums) {
    if (nums.length == 0) return;
    int s = 0, n = nums.length - 1;
    for (int i = 0; i <= n; ) {
        if (nums[i] == 0) {
            swap(nums, s++, i++);
        } else if (nums[i] == 2) {
            swap(nums, n--, i); // i 不变
        } else {
            i++;
        }
    }
}

这就是完整的「三指针 + 一次扫描」解法。用它解这题最稳、最快。

81.下一个排列（中等 技巧）

img

思路：灵神的思路非常nb

img

img

img

答疑
问：第一步找到 x 后，为什么 x 右边的数是递减的？

答：反证法。假设 x 右边的数不是递减的，也就是说，在 x 的右边，存在 nums[i]<nums[i+1] 的情况，那么我们应把 nums[i] 当作 x，这与事实矛盾。

问：为什么第二步交换后，右边的序列仍然是递减的？

答：设交换前 nums=[…,x,c,b,a,…] 且 ax>a>⋯，仍然是递减的。

问：如果 nums 是第一个排列，我们是怎么算的？

答：例如 nums=[1,2,3]。第一步找到 2，第二步交换 2 和 3，第三步反转 2（只有一个数，反转后还是 2），最终得到 [1,3,2]。读者可以动手算算 [1,3,2] 的后续排列，以加深印象。

总结来说就是三步

  • 从右向左，找第一个小于右侧相邻数字的数 x
  • 找 x 右边最小的大于 x 的数 y，交换 x 和 y
  • 反转 y 右边的数，把右边的数变成最小的排列
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 void nextPermutation(int[] nums) {
        int n = nums.length;
        //第一步，从右往左找到第一个小于右侧相邻数字的数nums[i]
        int i = n - 2;//从倒数第二个数开始，因为倒数第一个数要作为比较对象
        //从右往左找到第一个小于右侧相邻数字的数nums[i]
        // 只有符合nums[i]<nums[i+1]的数才是我们要找的就会跳出循环，否则i--继续找
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        //如果找到了就进入第二步，否则跳过第二步，翻转整个数组

        if (i >= 0) {
            //第二步，在nums[i]的右侧找到第一个大于nums[i]的数nums[j]，交换这两个数字
            int j = n - 1;
            //只有符合nums[j]>nums[i]的数才是我们要找的就会跳出循环，否则j--继续找
            while (nums[j] <= nums[i]) {
                j--;
            }
            //找到了交换nums[i]与nums[j]的位置
            swap(nums, i, j);
        }
        //第三步，翻转n[i+1,n-1]范围的数组顺序（如果上面跳过了第二步，此时i=-1，也就是翻转整个数组）
        reverse(nums, i + 1, n - 1);
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

82.寻找重复数（中等 技巧）

img

转换为环形链表II本文档第36题，一毛一样的题

快慢指针法

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 findDuplicate(int[] nums) {
        // 快慢指针法，快指针每次走两步，慢指针每次走一步，当它们相遇时，说明有环。
        // 然后将其中一个指针重新指向数组的起始位置，然后两个指针每次都走一步，直到再次相遇，即为环的开始点，也就是重复的数。
        int slow = nums[0];// 慢指针，走一步
        int fast = nums[nums[0]];// 快指针，走两步
        // 当它们未相遇时，继续循环
        while (slow != fast) {
            slow = nums[slow];// 慢指针继续走一步
            fast = nums[nums[fast]];// 快指针继续走两步
        }
        //当它们相遇时，将其中一个指针重新指向数组的起始位置
        fast = 0;
        // 然后两个指针每次都走一步，直到再次相遇，即为环的开始点，也就是重复的数。
        while (slow != fast) {
            slow = nums[slow];// 慢指针继续走一步
            fast = nums[fast];// 快指针继续走一步
        }
        // 当它们再次相遇时，即为环的开始点，也就是重复的数。
        return slow;
    }
}

83.无重复字符的最长子串（中等 滑动窗口）

img

  • 标签：滑动窗口

  • 维护一个不含重复字符的窗口 [start … end]。

  • end 向右扫描字符；若遇到重复字符，就把 start 跳到该字符上次出现位置的后一位，从而“丢掉”重复。
  • 用 map<char, index+1> 记录每个字符最近一次出现的位置 + 1（存 index+1 是为了可以直接赋值到 start，不用再 +1）。
  • 每一步用 end - start + 1 更新最长长度 ans。

窗口不变量：区间 [start … end] 始终是无重复字符的最长可能窗口。

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 int lengthOfLongestSubstring(String s) {
    int n = s.length();
    int ans = 0; // 答案：最长子串长度
    Map<Character, Integer> map = new HashMap<>(); // 记录字符最近一次出现的位置 + 1

    // 双指针滑动窗口：start为左边界，end为右边界
    for (int start = 0, end = 0; end < n; end++) {
        char alpha = s.charAt(end); // 当前右指针字符

        // 如果当前字符见过，且上次出现位置在当前窗口内，
        // 就把左边界跳到“上次出现位置的下一位”
        if (map.containsKey(alpha)) {
            start = Math.max(map.get(alpha), start);
            // 注意：map里存的是 index + 1，所以这里直接取值即可
        }

        // 记录当前字符的“下一位位置”（end + 1）
        map.put(alpha, end + 1);

        // 用当前窗口长度更新答案
        ans = Math.max(ans, end - start + 1);
    }
    return ans;
}

为什么 map 存的是 end + 1？

因为你希望在重复时把 start 直接跳到重复字符的下一位。
如果存的就是 end，那你在用的时候还要 +1；现在直接存 end + 1，可读性更好，也避免了 off-by-one 的小错误。

为什么 start = Math.max(map.get(alpha), start)？

  • 只有当上次出现的位置在当前窗口内时，才需要移动 start。
  • 如果上次出现位置早就被丢掉了（< start），就不必回退 start，因此取 max。

例子 1："abcabcbb"（答案 3）

step end 字符 map 中上次位置 start 更新为 当前窗口 长度
1 0 a 无 0 [a] 1
2 1 b 无 0 [ab] 2
3 2 c 无 0 [abc] 3 ✅
4 3 a 1 1 [bca] 3
5 4 b 2 2 [cab] 3
6 5 c 3 3 [abc] 3
7 6 b 5 5 [cb] 2
8 7 b 7 7 [b] 1

例子 2："pwwkew"（答案 3）

step end 字符 上次位置 start 窗口 长度
1 0 p 无 0 [p] 1
2 1 w 无 0 [pw] 2
3 2 w 2 2 [w] 1
4 3 k 无 2 [wk] 2
5 4 e 无 2 [wke] 3 ✅
6 5 w 3 3 [kew] 3 ✅

84.找到字符串中所有的字母异位词（中等 滑动窗口）

img

  • 目标：找出字符串 s 中，所有与 p 是字母异位词（anagram）的长度为 |p| 的子串的起始下标。
  • 做法：维护一个固定长度为 m = p.length() 的滑动窗口在 s 上滑动；用一个长度 26 的整型数组来“记录差异”，使窗口子串与 p 的频次之和为 0 即代表匹配。

直观理解：先把 p 每个字母的需要量记录在 sCount[26] 里（sCount[c]++）；
窗口中每遇到一个字母，就抵消掉（sCount[c]--）。
当窗口长度等于 m 且 sCount 全部为 0，说明窗口刚好和 p 的频次完全一致 ⇒ 找到一个异位词。

思路（滑动窗口）

  • 创建 cnt[26]，先把 p 的字符频次加进去：cnt[c-'a']++。

  • 维护长度为 m的窗口 [left, right] 在 s上移动：

    • 当字符 s[right] 进入窗口：cnt[s[right]-'a']--。
    • 保持窗口大小不超过 m，若超过则让字符 s[left] 移出窗口：cnt[s[left]-'a']++，并 left++。
    • 若当前窗口大小正好为 m，且 cnt 恰好全部为 0，说明是一个异位词，记录 left。

cnt 之所以能判断“是否异位”，是因为：窗口内字符频次与 p 的频次一一抵消，最后全为 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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();// 存放结果的列表
        int n = s.length();
        int m = p.length();
        if (n < m) return res;// 如果s的长度小于p，直接返回空列表

        int[] sCount = new int[26];// 用于统计s中每个字符的频次
        for (int i = 0; i < m; i++) {
            sCount[p.charAt(i) - 'a']++;// 初始化，统计p中每个字符的频次
        }
        int left = 0;
        for (int right = 0; right < n; right++) {
            sCount[s.charAt(right) - 'a']--;// 将当前字符的频次减1
            if (right - left + 1 > m) {// 当窗口大小大于p的长度时，移动左指针
                sCount[s.charAt(left) - 'a']++;// 将移出窗口的字符频次加1
                left++;// 左指针右移
            }
            //长度等于m时检查是否全为0
            if (right - left + 1 == m && checkZero(sCount)) {
                res.add(left);
            }
        }
        return res;
    }

    private boolean checkZero(int[] sCount) {
        for (int i = 0; i < sCount.length; i++) {
            if (sCount[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

img

img

1
s = "cbaebabacd"`, `p = "abc"`, `m = 3
  • 初始：cnt[a]=1, cnt[b]=1, cnt[c]=1
  • 右移：
    • right=0, s[0]='c'：cnt[c]-- => 0
    • right=1, s[1]='b'：cnt[b]-- => 0
    • right=2, s[2]='a'：cnt[a]-- => 0
      窗口长度=3，cnt 全 0 => 记录 left=0
    • right=3, s[3]='e'：cnt[e]-- => -1，窗口过大，左边 c 移出：cnt[c]++ => 1（窗口 [1,3]）
      …
      最终会得到 [0, 6]。

85.二叉树的最近公共祖先（中等 二叉树）

img

自底向上地在树里查找 p 和 q，并把“在当前子树里找到的那个目标节点/祖先”返还给父节点，父节点据此判定自己是不是最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 1) 递归的终止条件（返回“我在这棵子树里看到了谁”）
    if (root == null || root == p || root == q) return root;

    // 2) 分别在左子树、右子树里找
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    // 3) 归并子结果
    if (left != null && right != null) return root;  // p、q 分别出现在左右子树 ⇒ 当前 root 就是最近公共祖先
    else return (left != null ? left : right);       // p、q 只在一边 ⇒ 把那一边向上传
}

核心不变量（递归函数返回值的语义）

lowestCommonAncestor(x, p, q) 的返回值表示：

  • 如果在以 x 为根的子树中找到了 p 或 q 之一，就返回找到的那个节点；
  • 如果在以 x 为根的子树中同时包含 p 和 q，返回它们在这棵子树中的最近公共祖先；
  • 如果一个都没找到，返回 null。

这个语义由第 1 步的终止条件 + 第 3 步的归并规则保证。

为何正确

  • 若当前 root 本身是 p 或 q，直接返回 root（这也允许“祖先可以是自己”）。

  • 递归拿到 left和 right：

    • 若都非空，说明 p 与 q 分居左右，第一次在同一层“汇合”，所以 root 就是 LCA。
    • 若只有一边非空，说明 p 和 q 都在同一个分支或者只发现了其中一个，把那一边的结果继续向上传递。
    • 若两边都为空，说明这棵子树里没有 p/q，返回 null。

小例子干跑（示例 1）

1
root = 3`, `p = 5`, `q = 1
  • 在 3 的左子树找到 5，右子树找到 1，于是 left != null && right != null ⇒ 返回 3，即最近公共祖先。

复杂度

  • 时间：O(n)，每个节点最多访问一次；
  • 空间：O(h)，递归栈深度（h 为树高，最坏 O(n)，平均 O(log n)）。

适用范围

  • 适用于普通二叉树（不是二叉搜索树，不依赖节点值大小）。
  • 不要求节点包含父指针；只要 p、q 都在这棵树里就能找到答案。

这段代码的优雅之处就在于：用一个返回值同时承载“找到谁/找到祖先”的信息，再通过“左右都非空 ⇒ 自己是祖先”的判定一举命中 LCA。

86.腐烂的橘子（中等 图论）

img

这题用的是多源 BFS（按层扩散），把“腐烂扩散每过 1 分钟”映射成“BFS 的一层”。代码里每一轮（round）就是 1 分钟，队列里存的就是当前这一分钟已经腐烂、会去感染周围的橘子坐标。

思路拆解

  1. 预处理
  • 扫一遍网格：
    • count 统计新鲜橘子的数量（值为 1）。
    • 把所有初始腐烂橘子（值为 2）的坐标全部入队（这是多源 BFS 的“多源”）。
  1. 按分钟扩散（BFS 层序）

  • 只要还有新鲜橘子（count > 0）且队列不空，就继续：

    • round++：进入下一分钟。

    • 取出当前队列大小 n，这 n 个腐烂橘子只负责本分钟向四周扩散；这一点保证“一分钟只扩散一层”。

    • 对这 n个橘子逐个出队，检查其四个方向（上、下、左、右）：

      • 邻格是新鲜橘子（值为 1）→ 立刻置为 2（表示被感染）；
      • count--（新鲜数量减少）；
      • 新感染的橘子加入队列（将在下一分钟继续传染）。
  1. 结束判断
  • 循环结束后：
    • 如果 count > 0，说明还有新鲜橘子没被感染（被 0 隔开等），返回 -1；
    • 否则返回 round（用掉的分钟数）。

关键变量

  • queue：当前“这一分钟内会传播的腐烂橘子”集合（坐标）。
  • count：剩余的新鲜橘子数量；每感染一个就减 1。
  • round：BFS 的层数，也就是分钟数。

复杂度

  • 时间：O(m*n)，每个格子最多入队一次。
  • 空间：O(m*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
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.util.LinkedList;
import java.util.Queue;

/**
 * 994. 腐烂的橘子
 * 多源 BFS：把所有初始为 2 的格子作为源点同时入队，按层(分钟)向四周传播。
 * 每完成一层传播，分钟数 +1；当所有 1 都被感染后返回累计分钟数；若仍有 1 无法被感染，返回 -1。
 */
public class Solution {
    public int orangesRotting(int[][] grid) {
        // 行数 M、列数 N
        int M = grid.length;
        int N = grid[0].length;

        // 队列存放将要“传播”的腐烂橘子坐标 (r, c)
        // 这里是“多源 BFS”，初始把所有 2 都入队
        Queue<int[]> queue = new LinkedList<>();

        // count 统计当前网格中“新鲜橘子”的数量
        int count = 0;

        // 1) 预处理：统计新鲜橘子数量，并把所有初始腐烂橘子入队
        for (int r = 0; r < M; r++) {
            for (int c = 0; c < N; c++) {
                if (grid[r][c] == 1) {
                    // 新鲜橘子
                    count++;
                } else if (grid[r][c] == 2) {
                    // 腐烂橘子：作为当前 BFS 的源点入队
                    queue.add(new int[]{r, c});
                }
                // grid[r][c] == 0 为空气，忽略
            }
        }

        // 如果一开始没有新鲜橘子，直接 0 分钟
        // （如果题目一定要求走 BFS 也可以不加，但这个剪枝能快些）
        // if (count == 0) return 0;

        // round 表示已经经过的“分钟数”（BFS层数）
        int round = 0;

        // 2) BFS 层序遍历（每一层 = 一分钟）
        // 条件：还存在新鲜橘子(count>0) 并且 队列里还有能继续传播的腐烂橘子
        while (count > 0 && !queue.isEmpty()) {
            // 进入下一分钟
            round++;

            // 当前队列中的结点数，恰好是“本分钟内”会向外传播的腐烂橘子数量
            int n = queue.size();

            // 把这一层的所有腐烂橘子逐个出队，并尝试感染其四邻的新鲜橘子
            for (int i = 0; i < n; i++) {
                int[] orange = queue.poll();
                int r = orange[0];
                int c = orange[1];

                // 上：r-1, c
                if (r - 1 >= 0 && grid[r - 1][c] == 1) {
                    grid[r - 1][c] = 2;     // 感染为腐烂
                    count--;                // 新鲜橘子总数减少
                    queue.add(new int[]{r - 1, c}); // 入队，下一分钟继续传播
                }

                // 下：r+1, c
                if (r + 1 < M && grid[r + 1][c] == 1) {
                    grid[r + 1][c] = 2;
                    count--;
                    queue.add(new int[]{r + 1, c});
                }

                // 左：r, c-1
                if (c - 1 >= 0 && grid[r][c - 1] == 1) {
                    grid[r][c - 1] = 2;
                    count--;
                    queue.add(new int[]{r, c - 1});
                }

                // 右：r, c+1
                if (c + 1 < N && grid[r][c + 1] == 1) {
                    grid[r][c + 1] = 2;
                    count--;
                    queue.add(new int[]{r, c + 1});
                }
            }
            // 至此，完成了“本分钟”的所有传播；下一轮 while 即进入“下一分钟”
        }

        // 3) 结束判断
        // 如果还有新鲜橘子残留（count>0），说明有些 1 被 0 隔断，无法被感染，返回 -1
        if (count > 0) {
            return -1;
        } else {
            // 所有新鲜橘子都被感染，返回累计的“分钟数”
            return round;
        }
    }
}

小例子（示意）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
grid = 
2 1 1
1 1 0
0 1 1

初始：queue=[(0,0)], count=7
round=0

第1分钟：感染 (0,1),(1,0)
queue=[(0,1),(1,0)], count=5, round=1

第2分钟：由 (0,1),(1,0) 继续感染 (0,2),(1,1)
queue=[(0,2),(1,1)], count=3, round=2

第3分钟：由 (0,2),(1,1) 继续感染 (2,1)
queue=[(2,1)], count=2, round=3

第4分钟：由 (2,1) 感染 (2,2)
queue=[(2,2)], count=1, round=4

第5分钟：由 (2,2) 感染 (1,2)（如果存在且为1）
...
直到 count==0 返回 round；若中途 queue 空了但 count>0，则返回 -1

为何可靠

  • “一分钟传播一层”用队列分批（n = queue.size()）保证；
  • 多源同时开始（初始所有 2 入队）= 同时刻的多个传播源；
  • 改写为 2 立即标记，避免重复感染/重复入队。

87.课程表（中等 图论）

img

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 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 初始化入度数组
        int[] indegrees = new int[numCourses];
        // 初始化邻接表
        List<List<Integer>> adjacency = new ArrayList<>();
        // 初始化队列
        Queue<Integer> queue = new LinkedList<>();
        // 初始化邻接表的大小为课程数量
        for(int i = 0; i < numCourses; i++)
            // 添加一个空的ArrayList到邻接表中
            adjacency.add(new ArrayList<>());
       
       
        // 遍历先决条件数组
        for(int[] cp : prerequisites) {
            // 增加课程cp[0]的入度
            indegrees[cp[0]]++;
            // 将课程cp[0]添加到课程cp[1]的邻接表中
            adjacency.get(cp[1]).add(cp[0]);
        }
    
    
        // 遍历所有课程
        for(int i = 0; i < numCourses; i++)
            // 如果课程i的入度为0，将其加入队列
            if(indegrees[i] == 0) queue.add(i);
       
       
        // 当队列不为空时，循环处理
        while(!queue.isEmpty()) {
            int pre = queue.poll(); // 从队列中取出一个课程
            numCourses--; // 已完成的课程数量减一
            // 遍历当前课程的邻接课程
            for(int cur : adjacency.get(pre))
                // 如果邻接课程的入度减一后为0，将其加入队列
                if(--indegrees[cur] == 0) queue.add(cur);
        }
        // 如果所有课程都已完成，返回true；否则返回false
        return numCourses == 0;
     }
}

这段代码用的是拓扑排序（Kahn 算法，BFS 版本）\来判断是否能把所有课程学完。问题可以抽象成：
把每门课看作有向图的一个结点，先修关系 b -> a（学 a 之前必须学 b）就是一条从 b 指向 a 的有向边。只要这个有向图*没有环，就能排出一种满足依赖的学习顺序；如果存在环*（互相依赖），就一定学不完。

这段代码用的是拓扑排序（Kahn 算法，BFS 版本）来判断是否能把所有课程学完。问题可以抽象成：
把每门课看作有向图的一个结点，先修关系 b -> a（学 a 之前必须学 b）就是一条从 b 指向 a 的有向边。只要这个有向图没有环，就能排出一种满足依赖的学习顺序；如果存在环（互相依赖），就一定学不完。

代码做了什么（逐步解释）

1）建图 + 统计入度

1
2
3
4
5
6
7
8
9
int[] indegrees = new int[numCourses];   // 入度数组：每门课还需要完成的“前置”数量
List<List<Integer>> adjacency = new ArrayList<>(); // 邻接表：从某课出发能到达的后续课程
for(int i = 0; i < numCourses; i++) adjacency.add(new ArrayList<>());

for (int[] cp : prerequisites) {
    // cp = [a, b] 代表要学 a 必须先学 b，也就是边 b -> a
    indegrees[cp[0]]++;            // a 的入度 +1（多了一个前置 b）
    adjacency.get(cp[1]).add(cp[0]); // 在 b 的出边链表里加入 a（b 学完后可以解锁 a）
}
  • indegrees[x]：x 课程当前还有多少门先修课没完成。
  • adjacency[u]：从 u 出发能“解锁”的课程列表（u 的直接后继）。

2）把所有“无前置”的课先入队

1
2
3
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++)
    if (indegrees[i] == 0) queue.add(i);

入度为 0 的课程表示现在就能学（无需前置），先放到队列里等待处理。

3）BFS 拓扑排序（按“解锁顺序”学习）

1
2
3
4
5
6
7
8
9
10
11
while(!queue.isEmpty()) {
    int pre = queue.poll();  // 取出一门当前可学的课
    numCourses--;            // 视为“完成”这门课（剩余待学课程数减一）

    // 学完 pre 之后，它指向的后续课程的入度都要 -1
    for (int cur : adjacency.get(pre)) {
        if (--indegrees[cur] == 0) {
            queue.add(cur);  // 被完全解锁（入度为 0），可以入队等待学习
        }
    }
}

这个循环会不断“拿出可学的课 → 学掉它 → 解锁它的后续课”。
如果图无环，最终所有课程都会被学完，队列也会在某个时刻为空。

4）判定是否学完

1
return numCourses == 0;
  • 如果 numCourses == 0，说明所有课程都被成功出队处理，没有环，学习可完成；
  • 如果还有剩余课程，说明图里有环（这些课入度始终不是 0，永远无法入队），因此返回 false。

为什么能判断“有环/无环”

拓扑排序的性质：

  • 无环有向图（DAG）一定存在拓扑序；Kahn 算法能遍历到所有结点；
  • 有环则会卡住：在环上的结点入度始终 ≥ 1，无法被减到 0，最终不能全部出队。

复杂度

  • 设课程数 N = numCourses，先修关系数 M = prerequisites.length
  • 时间复杂度：O(N + M)（建图 + BFS）
  • 空间复杂度：O(N + M)（邻接表 + 入度数组 + 队列）

小例子直观看看

示例：numCourses = 2, prerequisites = [[1,0]]

  • 边：0 -> 1
  • 入度：in[0]=0, in[1]=1
  • 队列初始：[0]
  • 取出 0 学完 → 解锁 1 → in[1]=0 → 入队 [1]
  • 取出 1 学完 → 结束 → 学完所有课 → 返回 true

示例：numCourses = 2, prerequisites = [[1,0],[0,1]]

  • 边：0 -> 1 和 1 -> 0（有环）
  • 入度：in[0]=1, in[1]=1
  • 队列初始：空（没有入度为 0 的课）
  • 无法开始，最终 numCourses != 0 → 返回 false

这就是整段代码的核心思想与执行流程：用 Kahn 拓扑排序检查是否存在环，从而判断能否完成所有课程。

88.实现Trie（前缀树） （中等 图论）

img

  • 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
    class Trie {
        private final TrieNode root;
        
        public Trie() {
            // 初始化前缀树对象
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (node.children[c - 'a'] == null) {
                    return false;
                }
                node = node.children[c - 'a'];
            }
            return node.isEnd;
        }

        public boolean startsWith(String prefix) {
            TrieNode node = root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if (node.children[c - 'a'] == null) {
                    return false;
                }
                node = node.children[c - 'a'];
            }
            return true;
        }
        
        // TrieNode内部类定义
        private static class TrieNode {
            TrieNode[] children;
            boolean isEnd;
            
            public TrieNode() {
                children = new TrieNode[26];
                isEnd = false;
            }
        }
    }

算法思路：

TrieNode结构：

  • children[26]：26个字母的子节点数组
  • isEnd：标记是否为单词结尾

insert方法：

  • 从根节点开始，逐字符遍历单词
  • 如果字符对应的子节点不存在，创建新节点
  • 最后标记单词结尾

search方法：

  • 从根节点开始，逐字符查找
  • 如果路径不存在，返回false
  • 如果路径存在但节点不是单词结尾，返回false
  • 只有路径存在且节点是单词结尾，才返回true

startsWith方法：

  • 从根节点开始，逐字符查找前缀
  • 如果前缀路径存在，返回true
  • 如果路径不存在，返回false

这个实现的时间复杂度：

  • 插入：O(m)，m为单词长度
  • 搜索：O(m)，m为单词长度
  • 前缀搜索：O(m)，m为前缀长度

空间复杂度：O(ALPHABET_SIZE N M)，其中N是插入的单词数量，M是平均单词长度。

89.接雨水（困难 双指针）

img

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 trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        // 计算每个位置左侧的最大值和右侧的最大值
        int[] leftMax = new int[n];
        leftMax[0] = height[0];//第一个位置左侧的最大值就是它本身
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i - 1]);//每个位置左侧的最大值是它本身和前一个位置的左侧最大值的较大者
        }
        //计算每个位置右侧的最大值
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];//最后一个位置右侧的最大值就是它本身
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(height[i], rightMax[i + 1]);//每个位置右侧的最大值是它本身和后一个位置的右侧最大值的较大者
        }
        //计算每个位置能接的雨水量
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];//每个位置能接的雨水量是它左侧最大值和右侧最大值的较小者减去它本身的高度
        }
        return ans;
    }
}

预处理每个位置左边最高柱子与右边最高柱子，再用公式
water[i] = min(leftMax[i], rightMax[i]) - height[i]

为什么这个公式成立？

在位置 i 上能蓄的水高度，受两边「挡板」限制。

  • 左边能挡到的最高高度是 leftMax[i]（从 0..i 的最高柱）
  • 右边能挡到的最高高度是 rightMax[i]（从 i..n-1 的最高柱）
    真实能蓄水的高度是两侧挡板中较低的那块（否则水会从矮的一边溢出），所以是
    level = min(leftMax[i], rightMax[i])。
    实际水量则是这高度减去该位置的柱高：
    water[i] = max(0, level - height[i])（代码中省略 max(0, …)，因为当 level < height[i] 时差为负，最终加和也不会出错）。

法二 双指针做法

  • 两个指针：l = 0，r = n-1

  • 两个变量：leftMax = 0，rightMax = 0（分别记录到当前为止左右侧的最高柱）

  • 答案：ans = 0

  • 循环 while (l < r)：

    • 如果

      height[l] < height[r]：

      • 若 height[l] >= leftMax，更新 leftMax = height[l]

    • 否则此处可接水 leftMax - height[l]，累加到 ans

      • l++

    • 否则

      height[r] <= height[l]：

      • 若 height[r] >= rightMax，更新 rightMax = height[r]
      • 否则此处可接水 rightMax - height[r]，累加到 ans
      • r--

为什么对较小侧结算？
因为此时两侧较小的那一边已经成为瓶颈，另一边再高也不会让“较小值”变大，当前侧的水量已经确定。

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 int trap(int[] height) {
        int n = height.length;
        if (n <= 2) return 0;

        int l = 0, r = n - 1;
        int leftMax = 0, rightMax = 0;
        int ans = 0;

        while (l < r) {
            if (height[l] < height[r]) {
                // 左侧成为短板，能接的水由 leftMax 决定
                if (height[l] >= leftMax) {
                    leftMax = height[l];
                } else {
                    ans += leftMax - height[l];
                }
                l++;
            } else {
                // 右侧成为短板，能接的水由 rightMax 决定
                if (height[r] >= rightMax) {
                    rightMax = height[r];
                } else {
                    ans += rightMax - height[r];
                }
                r--;
            }
        }
        return ans;
    }
}

例子快速过一遍

以 height = [4,2,0,3,2,5]：

  • 初始：l=0,r=5,leftMax=0,rightMax=0,ans=0
  • 因为 height[l]=4 < height[r]=5，更新 leftMax=4，l=1
  • height[l]=2 < rightMax(=5)，加 leftMax(4)-2=2 → ans=2，l=2
  • height[l]=0 < rightMax(=5)，加 4-0=4 → ans=6，l=3
  • height[l]=3 < rightMax(=5)，加 4-3=1 → ans=7，l=4
  • height[l]=2 < rightMax(=5)，加 4-2=2 → ans=9，l=5
  • 结束，答案 9