算法面试八股文——30道LeetCode高频题（BAT面试必刷）

写在前面：本文精选 LeetCode Hot 100 + 面试150 中 BAT 大厂最高频的 30 道题，每道题都配有一句话总结 + 深度解析 + 面试加分回答 + 完整代码。背下这 30 道，算法面试过关率 80%+。

📖 学习指南

🎯 学习目标：通过本文，你将系统掌握 算法 的核心知识，能够自信地应对任何相关面试问题。

适合人群

  • 🔰 初学者：想系统学习 算法 的开发者
  • 🚀 有经验者：想深入理解 算法 原理的高级开发者
  • 💼 面试准备者：想刷 算法 面试题的求职者

学习建议

  1. 先理解概念，再深入原理：先搞懂”是什么”，再搞懂”为什么”
  2. 结合实战场景：不要死记硬背，要理解实际应用场景
  3. 动手实践：在自己电脑上安装环境，执行本文的示例代码
  4. 反复复习：面试前一周，每天复习 10 个问题

学习时间估算

  • ⏱️ 快速复习（只看一句话总结）：2 小时
  • 📚 系统学习（看深度解析）：1-2 天
  • 💪 深入理解（研究源码）：1 周+

🗺️ 知识图谱

mindmap
  root((算法))
    基础概念
      核心概念1
      核心概念2
      核心概念3
    高级特性
      特性1
      特性2
    实战应用
      应用场景1
      应用场景2
    性能优化
      优化技巧1
      优化技巧2

⚠️ 常见陷阱与误区

陷阱 1：概念理解错误

❌ 错误示例：

1
# 错误的理解或用法

✅ 正确做法：

  • 正确理解概念
  • 避免常见误区

陷阱 2：忽略边界条件

❌ 错误做法：

  • 不考虑特殊情况
  • 忽略异常处理

✅ 正确做法：

  • 总是考虑边界条件
  • 添加异常处理

💡 面试技巧

技巧 1：结构化回答

不要只回答”是什么”，要按照以下结构回答：

  1. 一句话总结（概念）
  2. 深度解析（原理、实现、优缺点）
  3. 面试加分回答（实际项目经验、源码理解、行业最佳实践）

技巧 2：结合实战场景

不要只背概念，要结合实际项目经验回答。

技巧 3：引导到你会的方向

如果遇到不会的问题，不要慌，可以引导到你会的方向。

🎯 实战演练（真实面试场景）

场景 1：请你设计一个系统？

回答思路：

  1. 需求分析：明确系统需求
  2. 技术选型：选择合适的技术栈
  3. 架构设计：设计系统架构
  4. 性能优化：考虑性能瓶颈和优化方案

🚀 学习路径总结

第一阶段：基础概念（1-2 天）

  • 理解核心概念
  • 掌握基本操作
  • 完成入门教程

第二阶段：高级特性（2-3 天）

  • 掌握高级特性
  • 理解实现原理
  • 完成进阶教程

第三阶段：实战应用（1 周+）

  • 搭建实际项目
  • 解决实战问题
  • 阅读源码（可选）

第四阶段：面试准备（1 周）

  • 刷完本文的所有问题
  • 复习相关知识点
  • 准备项目经验
  • 模拟面试

📚 扩展学习资源

官方资源

书籍推荐

  • 《算法 实战》
  • 《算法 权威指南》

博客推荐

目录

  1. 【数组/哈希表】两数之和
  2. 【数组/双指针】盛最多水的容器
  3. 【数组/滑动窗口】无重复字符的最长子串
  4. 【数组/滑动窗口】最小覆盖子串
  5. 【数组/前缀和】和为K的子数组
  6. 【链表】反转链表
  7. 【链表】合并两个有序链表
  8. 【链表】合并K个升序链表
  9. 【链表】环形链表II
  10. 【链表】LRU缓存
  11. 【数组/排序】三数之和
  12. 【数组/二分】搜索旋转排序数组
  13. 【数组/二分】在排序数组中查找元素的第一个和最后一个位置
  14. 【数组/Stack】接雨水
  15. 【树/DFS】二叉树的最大深度
  16. 【树/BFS】二叉树的层序遍历
  17. 【树/DFS】二叉树的最近公共祖先
  18. 【树/DFS】二叉树中的最大路径和
  19. 【动态规划】最大子数组和
  20. 【动态规划】最长递增子序列
  21. 【动态规划】编辑距离
  22. 【动态规划】零钱兑换
  23. 【动态规划/0-1背包】分割等和子集
  24. 【回溯】全排列
  25. 【回溯】子集
  26. 【回溯】N皇后
  27. 【并查集/DFS】岛屿数量
  28. 【堆/优先队列】数组中的第K大元素
  29. 【堆/滑动窗口】滑动窗口最大值
  30. 【图/BFS】课程安排

Q1：两数之和（Easy）【数组/哈希表】

一句话总结

用哈希表把 target - nums[i] 存起来，O(1) 查找补数，把暴力 O(n²) 优化到 O(n)。

深度解析

暴力解法：两层循环，固定 i，遍历 j 找 nums[i] + nums[j] == target。时间复杂度 O(n²)。

优化思路：遍历到 nums[i] 时，如果 target - nums[i] 已经在哈希表里，说明找到了答案。

1
2
3
4
5
6
7
8
9
10
11
12
// 哈希表版（面试写这个！）
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

复杂度分析：

  • 时间复杂度：O(n)，只遍历一次
  • 空间复杂度：O(n)，哈希表最多存 n 个元素

面试加分回答

  1. 返回下标还是值？ 题目通常要求返回下标，注意不是返回 nums[i] 和 nums[j] 的值！
  2. 可以排序吗？ 如果可以排序，可以用双指针 O(n log n)；但原题要求返回原始下标，所以不能排序。
  3. 变体题 [167] 两数之和 II：输入是有序数组，直接用左右指针 O(n)，不需要哈希表。
  4. 变体题 [15] 三数之和：固定一个数，转化为两数之和，注意去重逻辑。

Q2：盛最多水的容器（Medium）【数组/双指针】

一句话总结

双指针从两端向中间夹逼，每次移动较矮的那边，因为移动较高那边不可能得到更大的面积。

深度解析

暴力解法：枚举所有 (i, j) 组合，计算 min(height[i], height[j]) * (j - i)。O(n²)。

核心洞察：

  • 面积是 min(left_h, right_h) * width
  • 如果 height[left] < height[right]，那么移动 right 不可能让面积变大（宽度变小，且高度上限还是 height[left]）
  • 所以每次移动较矮的那边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        int h = Math.min(height[left], height[right]);
        int w = right - left;
        maxArea = Math.max(maxArea, h * w);
        
        // 移动较矮的那边
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

复杂度分析：

  • 时间复杂度：O(n)，双指针各遍历一次
  • 空间复杂度：O(1)

面试加分回答

为什么移动较矮的那边是正确的？可以用反证法：假设 height[left] < height[right]，如果移动 right，新面积是 min(height[left], height[new_right]) * (new_right - left)，宽度变小了，而高度上限还是 height[left]，所以面积不可能超过当前的 maxArea。因此移动较矮那边是唯一可能更新答案的选择。

Q3：无重复字符的最长子串（Medium）【数组/滑动窗口】

一句话总结

维护一个动态窗口，右指针扩张加入字符，遇到重复时左指针收缩直到无重复，全程记录最大窗口长度。

深度解析

滑动窗口模板题：用哈希表 window 记录窗口内每个字符的出现次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    int maxLen = 0;
    
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        window.put(c, window.getOrDefault(c, 0) + 1);
        
        // 当出现重复字符时，收缩窗口
        while (window.get(c) > 1) {
            char d = s.charAt(left);
            left++;
            window.put(d, window.get(d) - 1);
        }
        
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

优化版（用数组代替哈希表，因为字符集有限）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int lengthOfLongestSubstring(String s) {
    int[] window = new int[128]; // ASCII 字符集
    int left = 0, right = 0;
    int maxLen = 0;
    
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        window[c]++;
        
        while (window[c] > 1) {
            char d = s.charAt(left);
            left++;
            window[d]--;
        }
        
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

复杂度分析：

  • 时间复杂度：O(n)，每个字符最多被访问两次（右指针一次，左指针一次）
  • 空间复杂度：O(1)，数组大小固定 128

面试加分回答

  1. 为什么用 while (window.get(c) > 1) 而不是 if？ 因为收缩窗口时可能移除多个字符，需要循环直到当前字符 c 的计数降为 1。
  2. 变体题 [76] 最小覆盖子串：从”无重复”变成”包含目标字符”，需要维护 valid 计数器判断窗口是否有效。
  3. Python 可以用 ord(c) 转 ASCII，Java 可以直接用 c（char 自动转 int）。

Q4：最小覆盖子串（Hard）【数组/滑动窗口】

一句话总结

用滑动窗口 + 哈希表，右指针扩张直到窗口包含目标子串的所有字符，然后左指针收缩到不能再缩，记录最小窗口。

深度解析

这是滑动窗口最难的题目之一，核心是用两个哈希表：need（目标字符需求）和 window（当前窗口字符统计）。

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
public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    
    // 统计目标字符串 t 的字符需求
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    
    int left = 0, right = 0;
    int valid = 0; // 窗口中满足 need 的字符种类数
    int start = 0, minLen = Integer.MAX_VALUE;
    
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }
        
        // 当窗口满足条件时，尝试收缩
        while (valid == need.size()) {
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            char d = s.charAt(left);
            left++;
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

复杂度分析：

  • 时间复杂度：O(|S| + |T|)，每个字符最多被访问两次
  • 空间复杂度：O(|S| + |T|)，两个哈希表的大小

面试加分回答

  1. 为什么用 equals 而不是 == 比较？ 因为 window.get(c) 是 Integer 对象，用 == 比较的是引用而不是值。
  2. 如何判断窗口满足条件？ 用 valid == need.size()，即窗口中满足需求的字符种类数等于目标字符种类数。
  3. 变体题 [438] 找到字符串中所有字母异位词：窗口大小固定为 t.length()，找到满足条件的起点。
  4. 坑点：如果 t 中有重复字符（比如 "AA"），窗口中也需要至少两个 A 才算满足条件。

Q5：和为K的子数组（Medium）【数组/前缀和】

一句话总结

用前缀和把”子数组和 = K”转化为”两数之差 = K”，用哈希表 O(1) 查找，count += map.get(prefixSum - K)。

深度解析

暴力解法：枚举所有 (i, j) 子数组，计算求和。O(n²)。

前缀和思路：

  • prefixSum[j] - prefixSum[i] = K 等价于子数组 i+1...j 的和为 K
  • 遍历到位置 j 时，查找哈希表里是否有 prefixSum[j] - K
  • 如果有，说明存在以 j 结尾的、和为 K 的子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixSumCount = new HashMap<>();
    prefixSumCount.put(0, 1); // 关键：前缀和为 0 出现 1 次
    
    int prefixSum = 0, count = 0;
    for (int num : nums) {
        prefixSum += num;
        // 查找是否存在 prefixSum - k
        count += prefixSumCount.getOrDefault(prefixSum - k, 0);
        // 更新当前前缀和的计数（放在后面！）
        prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) + 1);
    }
    return count;
}

为什么要先 count += ... 再更新哈希表？

  • 假设 k = 0，如果先更新哈希表，prefixSum - k = prefixSum 会取到当前这个值，导致把自己算进去。
  • 正确的顺序是：先查再存，保证查到的是之前的前缀和。

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)，哈希表存前缀和

面试加分回答

  1. prefixSumCount.put(0, 1) 的意义：处理从下标 0 开始的子数组。比如 nums = [1], k = 1，prefixSum = 1，查找 prefixSum - k = 0，如果不初始化 map[0] = 1，就查不到。
  2. 变体题 [560] 就是这道题本身，[930] 和相同的二元子数组是类似思路。
  3. 如果数组全是正数，可以用双指针（因为右移左指针必然和减少）；但这道题数组可以有负数，所以必须用前缀和 + 哈希表。

Q6：反转链表（Easy）【链表】

一句话总结

迭代法用三个指针（prev, curr, next）原地反转，递归法从后往前反转。

深度解析

迭代法（面试必写！）：

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        ListNode next = curr.next; // 暂存下一个节点
        curr.next = prev;        // 反转指针
        prev = curr;              // prev 右移
        curr = next;              // curr 右移
    }
    return prev; // prev 是新的头节点
}

递归法（理解思路，面试可选写）：

1
2
3
4
5
6
7
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseList(head.next);
    head.next.next = head; // 让下一个节点指向自己
    head.next = null;      // 断开原来的指针
    return newHead;
}

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：迭代法 O(1)，递归法 O(n)（递归栈）

面试加分回答

  1. 画图的顺序：next = curr.next → curr.next = prev → prev = curr → curr = next，这个顺序不能乱，否则会断链。
  2. 变体题 [92] 反转链表 II：反转从位置 left 到 right 的部分，用虚拟头节点简化边界处理。
  3. 变体题 [25] K 个一组翻转链表：每 K 个节点反转一次，不足 K 个保持原样。需要用到反转链表 + 尾插法。

Q7：合并两个有序链表（Easy）【链表】

一句话总结

用虚拟头节点（dummy node）+ 双指针，每次取较小的节点接入新链表，最后接上剩余部分。

深度解析

为什么要用虚拟头节点？ 避免处理 head 为 null 的边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            curr.next = list1;
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
    
    // 接上剩余部分
    curr.next = (list1 != null) ? list1 : list2;
    
    return dummy.next;
}

递归版（代码更简洁，但空间复杂度 O(n)）：

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

复杂度分析：

  • 时间复杂度：O(n + m)
  • 空间复杂度：迭代法 O(1)，递归法 O(n + m)

面试加分回答

  1. 变体题 [23] 合并 K 个升序链表：可以用优先队列（堆）或分治法。
  2. 分治法：两两合并，类似归并排序的自底向上过程，时间复杂度 O(N log K)。
  3. 虚拟头节点是链表的万能技巧，在 [19] 删除链表倒数第 N 个节点、[141] 环形链表等题目中都有应用。

Q8：合并K个升序链表（Hard）【链表】

一句话总结

用优先队列（小顶堆）维护 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
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
    
    // 把所有非空的头节点加入堆
    for (ListNode list : lists) {
        if (list != null) {
            minHeap.offer(list);
        }
    }
    
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    
    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        curr.next = node;
        curr = curr.next;
        if (node.next != null) {
            minHeap.offer(node.next);
        }
    }
    
    return 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
29
public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) return null;
    return mergeKLists(lists, 0, lists.length - 1);
}

private ListNode mergeKLists(ListNode[] lists, int left, int right) {
    if (left == right) return lists[left];
    int mid = left + (right - left) / 2;
    ListNode l1 = mergeKLists(lists, left, mid);
    ListNode l2 = mergeKLists(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

复杂度分析：

  • 优先队列：时间 O(N log K)，空间 O(K)
  • 分治法：时间 O(N log K)，空间 O(log K)（递归栈）

面试加分回答

  1. 为什么优先队列的时间是 O(N log K)？ 每个节点入堆和出堆各一次，每次堆操作 O(log K)，共 N 个节点。
  2. 分治法和优先队列哪个更好？ 分治法空间更优（O(log K) vs O(K)），且实际运行中分治法往往更快（避免了堆的维护开销）。
  3. 如果 K 很大（比如 K=10000），优先队列的初始建堆成本是 O(K)，而分治法没有这个问题。

Q9：环形链表II（Medium）【链表】

一句话总结

快慢指针判环，相遇后慢指针回到起点，两指针同速前进，再次相遇点就是入环点（Floyd 判圈算法）。

深度解析

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

  • 快指针每次走 2 步，慢指针每次走 1 步
  • 如果有环，两指针必然在环内相遇

第二步：找到入环点（数学推导）

  • 设：头到入环点距离 = a，入环点到相遇点距离 = b，环长 = c
  • 相遇时：慢指针走了 a + b，快指针走了 a + b + n * c（多走了 n 圈）
  • 快指针路程是慢指针的 2 倍：2(a + b) = a + b + n * c
  • 化简得：a = n * c - b
  • 含义：从相遇点再走 a 步，刚好回到入环点；从起点走 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 slow = head, fast = head;
    
    // 第一步：判环
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            // 第二步：找入环点
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null; // 无环
}

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

面试加分回答

  1. 为什么快指针一定要走 2 步？ 走 3 步、4 步也行，但 2 步是最优的（保证一定能相遇，且不会跳过慢指针）。
  2. 数学推导是面试加分项，如果记不住推导，可以说”这是 Floyd 判圈算法的结论，第二步把慢指针重置到起点后两指针同速前进，再次相遇点就是入环点”。
  3. 变体题 [142] 就是这道题，[287] 寻找重复数可以用类似思路（把数组看成链表，重复元素就是入环点）。

Q10：LRU缓存（Medium）【链表/哈希表】

一句话总结

用哈希表 + 双向链表，哈希表 O(1) 查找，双向链表 O(1) 删除/插入，最近使用的放表头，最久未使用的在表尾。

深度解析

为什么需要双向链表？ 删除节点时需要 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
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 LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    private int capacity;
    private Map<Integer, Node> map;
    private Node dummyHead, dummyTail; // 虚拟头尾节点
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        dummyHead = new Node(0, 0);
        dummyTail = new Node(0, 0);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);     // 从当前位置删除
        insertToHead(node); // 插入到表头（表示最近使用）
        return node.val;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // 已存在：更新值，并移到表头
            Node node = map.get(key);
            node.val = value;
            remove(node);
            insertToHead(node);
        } else {
            // 不存在：创建新节点
            Node node = new Node(key, value);
            if (map.size() >= capacity) {
                // 容量满了，删除最久未使用的（表尾）
                Node toRemove = dummyTail.prev;
                remove(toRemove);
                map.remove(toRemove.key);
            }
            insertToHead(node);
            map.put(key, node);
        }
    }
    
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void insertToHead(Node node) {
        node.next = dummyHead.next;
        node.prev = dummyHead;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }
}

复杂度分析：

  • 时间复杂度：O(1) 对于 get 和 put
  • 空间复杂度：O(capacity)

面试加分回答

  1. 为什么用虚拟头尾节点？ 避免处理边界情况（比如链表为空、只有一个节点等）。
  2. Java 中有现成的 LinkedHashMap 可以实现 LRU，但面试时要求自己实现双向链表。
  3. 变体题 [146] 就是这道题，[460] LFU 缓存更难，需要维护访问频次。

Q11：三数之和（Medium）【数组/排序】

一句话总结

排序 + 固定一个数 + 双指针找剩下两个数，注意去重：外层循环跳过相同元素，找到解后左右指针也要跳过相同元素。

深度解析

为什么要先排序？ 只有排序后才能用双指针（利用有序性）。

去重是本题的核心难点：

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 List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    
    for (int i = 0; i < nums.length - 2; i++) {
        // 去重①：外层循环跳过相同的 nums[i]
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 去重②：找到解后，左右指针跳过相同的元素
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
}

复杂度分析：

  • 时间复杂度：O(n²)（排序 O(n log n) + 双层循环 O(n²)）
  • 空间复杂度：O(1)（忽略结果存储）

面试加分回答

  1. 为什么去重逻辑有两处？ ① 防止 nums[i] 重复导致三元组重复；② 防止 nums[left] 和 nums[right] 重复导致三元组重复。
  2. 很多候选人只做了去重①，漏了去重②，导致结果中有重复三元组，这是常见的扣分点。
  3. 变体题 [15] 三数之和、[16] 最接近的三数之和、[18] 四数之和 都是类似思路。
  4. 如果数组中有重复元素，必须先排序，否则去重逻辑无法工作。

Q12：搜索旋转排序数组（Medium）【数组/二分】

一句话总结

数组被分成两段有序部分，二分后必有一段是有序的，判断目标值是否在那一段里，否则在另一段。

深度解析

核心思路：

  1. 计算 mid
  2. 判断 nums[left...mid] 是否有序
  3. 如果有序，判断 target 是否在这个范围内
  4. 如果不有序，则 nums[mid...right] 一定有序，判断 target 是否在那个范围内
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 search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) return mid;
        
        // 判断哪一半是有序的
        if (nums[left] <= nums[mid]) {
            // 左半部分有序
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // 右半部分有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

复杂度分析：

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

面试加分回答

  1. 为什么用 nums[left] <= nums[mid] 而不是 <？ 当 left == mid 时（即只有两个元素），需要 <= 来判断左半部分是否只有一个元素（必然有序）。
  2. 变体题 [33] 搜索旋转排序数组（无重复）、[81] 搜索旋转排序数组 II（有重复）：II 中可能有 nums[left] == nums[mid] == nums[right]，此时无法判断哪边有序，只能 left++ 跳过。
  3. 变体题 [153] 寻找旋转排序数组中的最小值：类似的二分思路，找到无序的那一半继续二分。

Q13：在排序数组中查找元素的第一个和最后一个位置（Medium）【数组/二分】

一句话总结

分别用二分查找找左边界和右边界：找左边界时即使找到目标也继续往左收缩，找右边界时即使找到也继续往右收缩。

深度解析

找左边界：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1; // 关键：相等时也收缩右边界
        }
    }
    // 循环结束后，left 是第一个 >= target 的位置
    if (left >= nums.length || nums[left] != target) return -1;
    return left;
}

找右边界：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1; // 关键：相等时也收缩左边界
        } else {
            right = mid - 1;
        }
    }
    // 循环结束后，right 是最后一个 <= target 的位置
    if (right < 0 || nums[right] != target) return -1;
    return right;
}

完整代码：

1
2
3
4
5
public int[] searchRange(int[] nums, int target) {
    int left = leftBound(nums, target);
    int right = rightBound(nums, target);
    return new int[]{left, right};
}

复杂度分析：

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)

面试加分回答

  1. 为什么找左边界时 nums[mid] == target 要走 right = mid - 1？ 因为要找的是”第一个”等于 target 的位置，所以即使找到了也要继续往左找。
  2. 循环条件是 left <= right（闭区间），结束时 left 和 right 交叉，需要检查 left 是否越界以及 nums[left] 是否等于 target。
  3. 变体题 [35] 搜索插入位置：就是找左边界，如果没找到就返回应该插入的位置（即 left）。

Q14：接雨水（Hard）【数组/Stack】

一句话总结

双指针法：维护左右最大高度，如果 left_max < right_max 则当前位置的积水量由 left_max 决定，移动左指针；否则由 right_max 决定，移动右指针。

深度解析

方法一：暴力法（对每个位置，找左右最大高度）

  • 时间 O(n²)，空间 O(1)

方法二：动态规划（预处理每个位置的左右最大高度）

  • 时间 O(n)，空间 O(n)

方法三：双指针（最优！）

  • 核心思路：如果 height[left] 的左边最大值 < height[right] 的右边最大值，那么 left 位置的积水量由 left_max 决定（因为右边一定有比 left_max 大的）
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
public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0;
    int water = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            // left 位置的积水量由 leftMax 决定
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            // right 位置的积水量由 rightMax 决定
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    return water;
}

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

面试加分回答

  1. 为什么双指针法是正确的？ 当 height[left] < height[right] 时，可以保证 left_max < right_max（因为 right_max >= height[right] > height[left] >= left_max），所以 left 位置的积水量一定由 left_max 决定。
  2. 单调栈法：用递减栈找”凹下去”的部分，计算每个凹槽的积水量。时间 O(n)，但实现较复杂。
  3. 变体题 [42] 接雨水（Hard）、[407] 接雨水 II（三维版本，用堆）。

Q15：二叉树的最大深度（Easy）【树/DFS】

一句话总结

DFS 递归：树的最大深度 = 1 + max(左子树深度, 右子树深度)；BFS 层序遍历：层数即深度。

深度解析

DFS 递归法（最简洁）：

1
2
3
4
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

BFS 层序遍历法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        depth++;
    }
    return depth;
}

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：DFS O(n)（递归栈），BFS O(n)（队列）

面试加分回答

  1. 变体题 [111] 二叉树的最小深度：注意最小深度是”从根到最近叶子节点的层数”，如果根只有一个子节点，最小深度不是 1 而是要继续往下找。
  2. DFS 和 BFS 哪个更好？ 这道题两者都可以，但如果是 [199] 二叉树的右视图，BFS 更自然（每层取最后一个）。
  3. 递归的终止条件：root == null 时返回 0，这是所有二叉树递归题的基础。

Q16：二叉树的层序遍历（Medium）【树/BFS】

一句话总结

BFS + 队列，外层 while 遍历层，内层 for 处理当前层的每个节点，把子节点入队。

深度解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // 当前层的节点数
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        res.add(level);
    }
    return res;
}

变体：层序遍历 II（从下往上）：

1
2
// 方法：正常层序遍历，最后 Collections.reverse(res)
// 方法：用 LinkedList，每层插入到头部 add(0, level)

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

面试加分回答

  1. 关键技巧：用 levelSize = queue.size() 记录当前层的节点数，这样内层 for 循环就知道该处理哪些节点。
  2. 变体题：[102] 层序遍历、[107] 层序遍历 II、[199] 右视图（每层取最后一个）、[637] 层平均值。
  3. 如果要求”之字形”层序遍历（[103]）：用双端队列，或者用两个栈交替。

Q17：二叉树的最近公共祖先（Medium）【树/DFS】

一句话总结

递归查找：如果 root 是 p 或 q，直接返回 root；否则递归查找左右子树，如果左右都不为空则返回 root，否则返回非空的那个。

深度解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 终止条件：找到 p 或 q，或者遇到空节点
    if (root == null || root == p || root == q) return root;
    
    // 递归查找左右子树
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    // 如果左右都不为空，说明 p 和 q 分别在两个子树，root 就是 LCA
    if (left != null && right != null) return root;
    
    // 否则返回非空的那个（p 和 q 在同一侧）
    return (left != null) ? left : right;
}

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)（递归栈）

面试加分回答

  1. 为什么这个递归是正确的？ 递归的语义是”在以 root 为根的子树中查找 p 或 q，如果找到就返回该节点，否则返回 null”。根据左右子树的返回值就能判断 LCA。
  2. 如果 p 或 q 不存在于树中？ 上述代码会返回”存在那一个”的节点。如果需要检查 p 和 q 是否都存在，需要两次遍历。
  3. 变体题 [236] 二叉树的最近公共祖先、[235] 二叉搜索树的最近公共祖先（BST 可以利用有序性优化到 O(h)）。

Q18：二叉树中的最大路径和（Hard）【树/DFS】

一句话总结

递归计算”从下往上”的最大贡献值，路径和是”左贡献 + 根 + 右贡献”，用全局变量记录最大值。

深度解析

难点：路径可以以任意节点为起点和终点，但不能分叉（即不能走”根->左->右->根”）。

思路：递归计算”以当前节点为终点的最大路径和”（即只能从一边上来），然后用”左 + 根 + 右”更新全局最大值。

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 {
    int maxSum = Integer.MIN_VALUE; // 全局最大路径和
    
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxSum;
    }
    
    // 返回"以 node 为终点的最大路径和"
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        
        // 递归计算左右子树的最大贡献值（如果为负就舍弃）
        int leftGain = Math.max(dfs(node.left), 0);
        int rightGain = Math.max(dfs(node.right), 0);
        
        // 以当前节点为最高点的最大路径和
        int currPathSum = node.val + leftGain + rightGain;
        
        // 更新全局最大值
        maxSum = Math.max(maxSum, currPathSum);
        
        // 返回"以 node 为终点的最大路径和"（只能选左右中较大的一边）
        return node.val + Math.max(leftGain, rightGain);
    }
}

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)（递归栈）

面试加分回答

  1. 为什么返回值只能是 node.val + max(leftGain, rightGain)？ 因为返回值是”以 node 为终点的最大路径和”，路径不能分叉，所以只能选左右中的一边。
  2. 全局变量 maxSum 的更新：在递归过程中，每个节点都可能是”路径的最高点”，所以用 node.val + leftGain + rightGain 来更新。
  3. 如果树中所有节点都是负数：Math.max(dfs(node.left), 0) 会把负数变成 0，但 maxSum 的初始化是 INT_MIN，所以最终会返回最大的那个负数。

Q19：最大子数组和（Medium）【动态规划】

一句话总结

Kadane 算法：遍历数组，维护”以当前位置为终点的最大子数组和”，如果前面的和为负就丢弃，从当前元素重新开始。

深度解析

状态定义：dp[i] = 以 nums[i] 为终点的最大子数组和

状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])

空间优化：只需要一个变量 prev 记录 dp[i-1]

1
2
3
4
5
6
7
8
9
10
11
12
// 空间优化版（面试写这个！）
public int maxSubArray(int[] nums) {
    int prev = nums[0]; // dp[i-1]
    int maxSum = prev;
    
    for (int i = 1; i < nums.length; i++) {
        int curr = Math.max(nums[i], prev + nums[i]);
        maxSum = Math.max(maxSum, curr);
        prev = curr;
    }
    return maxSum;
}

完整 DP 版（帮助理解）：

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

复杂度分析：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)（空间优化版）

面试加分回答

  1. 状态转移方程的含义：dp[i] = max(nums[i], dp[i-1] + nums[i])，即”要么自己重新开始，要么接在前面”。
  2. 变体题 [53] 最大子数组和、[152] 乘积最大子数组（注意乘积有负数，需要同时维护最大值和最小值）。
  3. 如果要求返回子数组的起止下标：在更新 maxSum 时记录 start 和 end，当 prev < 0 时重置 start。

Q20：最长递增子序列（Medium）【动态规划】

一句话总结

DP 法 O(n²)：dp[i] = max(dp[j] + 1) for all j < i and nums[j] < nums[i]；贪心 + 二分 O(n log n)：维护一个递增数组，用二分找到第一个 >= 当前元素的位置并替换。

深度解析

方法一：动态规划 O(n²)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1); // 每个元素至少可以单独成为一个子序列
    int maxLen = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

方法二：贪心 + 二分 O(n log n)（较难，面试可选）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    
    for (int num : nums) {
        int left = 0, right = size;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        tails[left] = num;
        if (left == size) size++;
    }
    return size;
}

复杂度分析：

  • DP 法：时间 O(n²)，空间 O(n)
  • 贪心 + 二分：时间 O(n log n)，空间 O(n)

面试加分回答

  1. 贪心 + 二分的思想：tails[i] 表示”长度为 i+1 的递增子序列的最小可能的尾元素”。用二分找到第一个 >= 当前元素的位置并替换，可以保证 tails 是递增的。
  2. 为什么贪心是正确的？ 对于相同长度的递增子序列，尾元素越小，后面越有可能接上更大的元素。
  3. 变体题 [300] 最长递增子序列、[334] 递增的三元组（O(n) 解法：维护最小和两个最小值）。

Q21：编辑距离（Hard）【动态规划】

一句话总结

dp[i][j] = 将 word1[0...i-1] 转换成 word2[0...j-1] 的最小操作数，状态转移：相等则 dp[i][j] = dp[i-1][j-1]，否则取”删除、插入、替换”三者最小值 +1。

深度解析

状态定义：dp[i][j] = 将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小操作数

状态转移：

  • 如果 word1.charAt(i-1) == word2.charAt(j-1)：dp[i][j] = dp[i-1][j-1]（不需要操作）
  • 否则：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
    • dp[i-1][j] + 1：删除 word1[i-1]
    • dp[i][j-1] + 1：插入 word2[j-1]
    • dp[i-1][j-1] + 1：替换 word1[i-1] 为 word2[j-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
public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    // 初始化：把一个字符串变成空串的代价
    for (int i = 0; i <= m; i++) dp[i][0] = i; // 删除 i 次
    for (int j = 0; j <= n; j++) dp[0][j] = j; // 插入 j 次
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,     // 删除
                    Math.min(
                        dp[i][j - 1] + 1, // 插入
                        dp[i - 1][j - 1] + 1 // 替换
                    )
                );
            }
        }
    }
    return dp[m][n];
}

复杂度分析：

  • 时间复杂度：O(mn)
  • 空间复杂度：O(mn)，可优化到 O(n)（滚动数组）

面试加分回答

  1. 初始化的重要性：dp[i][0] = i 表示把 word1[0...i-1] 删除成空串需要 i 次操作；dp[0][j] = j 表示插入 j 次得到 word2[0...j-1]。
  2. 空间优化：用一维数组 + 临时变量存储左上角的值，类似 [198] 打家劫舍的优化思路。
  3. 变体题 [72] 编辑距离、[44] 通配符匹配、[10] 正则表达式匹配（都是 DP + 字符串的经典题）。

Q22：零钱兑换（Medium）【动态规划】

一句话总结

完全背包问题：状态 dp[i] = 凑成金额 i 所需的最少硬币数，状态转移 dp[i] = min(dp[i], dp[i - coin] + 1)，遍历顺序是正序（每个硬币可以用无限次）。

深度解析

为什么是完全背包？ 因为每个硬币可以用无限次。

状态定义：dp[i] = 凑成金额 i 所需的最少硬币数

状态转移：dp[i] = min(dp[i], dp[i - coin] + 1) for each coin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // 初始化为 impossible 值
    dp[0] = 0; // 凑成金额 0 需要 0 个硬币
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

复杂度分析：

  • 时间复杂度：O(amount × len(coins))
  • 空间复杂度：O(amount)

面试加分回答

  1. 为什么初始化为 amount + 1？ 因为最多需要 amount 个 1 元硬币，所以 amount + 1 可以表示”不可能”。
  2. 0-1 背包 vs 完全背包：0-1 背包的倒序遍历（for (int j = W; j >= weight[i]; j--)）保证每个物品只被选一次；完全背包的正序遍历（for (int j = weight[i]; j <= W; j++) 允许每个物品被选多次。
  3. 变体题 [322] 零钱兑换、[518] 零钱兑换 II（II 是求组合数，用 dp[i][j] 表示前 i 个硬币凑成金额 j 的组合数）。

Q23：分割等和子集（Medium）【动态规划/0-1背包】

一句话总结

0-1 背包变形：判断是否能从数组中选出若干元素使得和等于 target = sum / 2，状态 dp[j] = dp[j] || dp[j - nums[i]]，倒序遍历。

深度解析

转化为 0-1 背包问题：

  1. 如果数组总和是奇数，直接返回 false
  2. 否则，问题变成”能否从数组中选出若干元素使得和等于 target = sum / 2“
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if (sum % 2 != 0) return false;
    
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true; // 凑成和为 0 总是可以的
    
    for (int num : nums) {
        // 关键：倒序遍历，保证每个元素只被选一次
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}

复杂度分析：

  • 时间复杂度：O(n × target)
  • 空间复杂度：O(target)

面试加分回答

  1. 为什么倒序遍历？ 正序遍历会变成”完全背包”（每个元素可以用多次），倒序才能保证每个元素只被选一次。
  2. 0-1 背包的模板：
    • 最大值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，倒序
    • 是否存在：dp[j] = dp[j] || dp[j - weight[i]]，倒序
  3. 变体题 [416] 分割等和子集、[494] 目标和（转化为 0-1 背包：pos_sum - neg_sum = target）

Q24：全排列（Medium）【回溯】

一句话总结

回溯法：用 used 数组标记已选元素，每层遍历所有可选元素，如果未使用就选择、递归、撤销选择。

深度解析

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 List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, new boolean[nums.length], new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    // 终止条件：路径长度等于数组长度
    if (path.size() == nums.length) {
        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, used, path, res);
        
        // 撤销选择（回溯）
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

复杂度分析：

  • 时间复杂度：O(n! × n)（共有 n! 个排列，每个排列需要 O(n) 复制到结果）
  • 空间复杂度：O(n)（递归栈 + path + used）

面试加分回答

  1. 排列 vs 子集的区别：排列是有序的（[1,2] 和 [2,1] 不同），所以用 used 数组；子集是无序的，所以用 start 索引避免重复选择。
  2. 含重复元素的排列 [47]：需要先排序，然后去重：if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) continue;（关键是 !used[i-1]，表示”同一层不能选相同的元素”）。
  3. 回溯法的通用模板：终止条件 → 遍历所有选择 → 做选择 → 递归 → 撤销选择。

Q25：子集（Medium）【回溯】

一句话总结

回溯法：每个节点都是子集，用 start 索引避免重复选择同一元素，收集所有节点的路径。

深度解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    // 每个节点都是子集
    res.add(new ArrayList<>(path));
    
    for (int i = start; i < nums.length; i++) {
        // 做选择
        path.add(nums[i]);
        
        // 递归：注意是 i+1，不能重复选
        backtrack(nums, i + 1, path, res);
        
        // 撤销选择
        path.remove(path.size() - 1);
    }
}

迭代法（位运算）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    int n = nums.length;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subset.add(nums[i]);
            }
        }
        res.add(subset);
    }
    return res;
}

复杂度分析：

  • 回溯法：时间 O(n × 2ⁿ)，空间 O(n)
  • 位运算：时间 O(n × 2ⁿ)，空间 O(n)

面试加分回答

  1. 为什么每个节点都是子集？ 因为子集问题的定义是”数组的所有子序列”，每个节点代表”选了某些元素”的一种组合。
  2. 含重复元素的子集 [90]：需要排序 + 去重：if (i > start && nums[i] == nums[i-1]) continue;
  3. 排列、子集、组合的区别：
    • 排列：有序，used 数组
    • 子集：无序，start 索引
    • 组合：无序 + 固定长度，start 索引 + 终止条件判断长度

Q26：N皇后（Hard）【回溯】

一句话总结

回溯 + 合法性检查：每层选一列放置皇后，检查列、左上对角线、右上对角线是否冲突，全部放置完毕后收集结果。

深度解析

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
public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(board[i], '.');
    }
    backtrack(board, 0, res);
    return res;
}

private void backtrack(char[][] board, int row, List<List<String>> res) {
    if (row == board.length) {
        res.add(construct(board));
        return;
    }
    
    for (int col = 0; col < board.length; col++) {
        if (!isValid(board, row, col)) continue;
        
        // 做选择
        board[row][col] = 'Q';
        
        // 递归进入下一行
        backtrack(board, row + 1, res);
        
        // 撤销选择
        board[row][col] = '.';
    }
}

private boolean isValid(char[][] board, int row, int col) {
    // 检查列
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    // 检查左上对角线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    // 检查右上对角线
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

private List<String> construct(char[][] board) {
    List<String> path = new ArrayList<>();
    for (char[] row : board) {
        path.add(new String(row));
    }
    return path;
}

复杂度分析：

  • 时间复杂度：O(n!)（每层最多 n 个选择，共 n 层）
  • 空间复杂度：O(n)（递归栈）

面试加分回答

  1. 如何用三个集合优化 isValid？ 用 Set 记录已被占用的列、左上对角线（row - col）、右上对角线（row + col），可以把合法性检查优化到 O(1)。
  2. 左上对角线和右上对角线的标识：左上对角线上的格子满足 row - col 相等；右上对角线上的格子满足 row + col 相等。
  3. 变体题 [51] N 皇后（返回所有解）、[52] N皇后 II（只返回个数）。

Q27：岛屿数量（Medium）【并查集/DFS】

一句话总结

DFS 法：遍历矩阵，遇到陆地就 DFS 淹没整个岛屿（改成 ‘0’），计数 +1；并查集法：把相邻的陆地合并，最终连通分量数就是岛屿数。

深度解析

方法一：DFS

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
public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int count = 0;
    
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    // 边界检查 + 终止条件
    if (i < 0 || i >= grid.length || j < 0 || 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);
}

方法二：并查集

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
class UnionFind {
    int[] parent;
    int count;
    
    public UnionFind(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        parent = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    int id = i * n + j;
                    parent[id] = id;
                    count++;
                }
            }
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
            count--;
        }
    }
}

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int m = grid.length, n = grid[0].length;
    UnionFind uf = new UnionFind(grid);
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                grid[i][j] = '0'; // 避免重复合并
                int id = i * n + j;
                    if (i + 1 < m && grid[i + 1][j] == '1') uf.union(id, (i + 1) * n + j);
                    if (i - 1 >= 0 && grid[i - 1][j] == '1') uf.union(id, (i - 1) * n + j);
                    if (j + 1 < n && grid[i][j + 1] == '1') uf.union(id, i * n + (j + 1));
                    if (j - 1 >= 0 && grid[i][j - 1] == '1') uf.union(id, i * n + (j - 1));
                }
            }
        }
    }
    
    return uf.count;
}

复杂度分析：

  • DFS：时间 O(m × n)，空间 O(m × n)（递归栈）
  • 并查集：时间 O(m × n × α(mn))，空间 O(m × n)

面试加分回答

  1. DFS 和并查集哪个更好？ DFS 代码更简洁，并查集适合需要动态查询连通性的场景。
  2. 变体题：[200] 岛屿数量、[463] 岛屿的周长、[695] 岛屿的最大面积、[130] 被围绕的区域（DFS 标记边界上的岛屿，剩下的就是要被包围的）。
  3. 如果是”太平洋大西洋水流问题 [417]”：从边界开始 DFS，标记能流到太平洋和大西洋的格子，交集就是答案。

Q28：数组中的第K大元素（Medium）【堆/优先队列】

一句话总结

维护一个大小为 K 的小顶堆，遍历数组把元素加入堆，如果堆大小超过 K 就移除堆顶（最小元素），最后堆顶就是第 K 大。

深度解析

1
2
3
4
5
6
7
8
9
10
11
12
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // 移除最小的元素
        }
    }
    
    return minHeap.peek(); // 堆顶就是第 K 大
}

方法二：快速选择（平均 O(n)，最坏 O(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
public int findKthLargest(int[] nums, int k) {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

private int quickSelect(int[] nums, int left, int right, int k) {
    if (left == right) return nums[left];
    
    int pivotIndex = partition(nums, left, right);
    
    if (pivotIndex == k) {
        return nums[pivotIndex];
    } else if (pivotIndex < k) {
        return quickSelect(nums, pivotIndex + 1, right, k);
    } else {
        return quickSelect(nums, left, pivotIndex - 1, k);
    }
}

private int partition(int[] nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    
    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, i, right);
    return i;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

复杂度分析：

  • 堆：时间 O(n log k)，空间 O(k)
  • 快速选择：平均 O(n)，最坏 O(n²)

面试加分回答

  1. 为什么用小顶堆而不是大顶堆？ 小顶堆的堆顶是最小的，维护大小为 K 的小顶堆，堆顶就是第 K 大；如果用大顶堆，需要维护大小为 n - K + 1 的堆，不如小顶堆直观。
  2. 快速选择的优势：平均 O(n) 比堆的 O(n log k) 更快，但最坏情况是 O(n²)（比如数组已经有序）。
  3. 变体题 [215] 数组中的第 K 大元素、[347] 前 K 个高频元素（先用哈希表统计频率，再用小顶堆）。

Q29：滑动窗口最大值（Hard）【堆/滑动窗口】

一句话总结

维护一个单调递减队列（双端队列）：入队时移除所有比当前元素小的队尾元素，出队时如果队头下标超出窗口范围就移除，队头就是当前窗口的最大值。

深度解析

为什么用单调递减队列？ 因为队列头部要始终是当前窗口的最大值。

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[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // 存下标，维护单调递减队列
    
    for (int i = 0; i < n; i++) {
        // 移除窗口外的元素（队头下标 <= i - k）
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }
        
        // 维护单调递减：移除队尾所有比当前元素小的
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        
        // 当前元素入队
        deque.offerLast(i);
        
        // 当窗口大小达到 k 时，记录结果
        if (i >= k - 1) {
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    
    return res;
}

复杂度分析：

  • 时间复杂度：O(n)（每个元素最多入队和出队一次）
  • 空间复杂度：O(k)（队列大小不超过 k）

面试加分回答

  1. 为什么时间复杂度是 O(n) 而不是 O(nk)？ 因为虽然有两个 while 循环，但每个元素最多入队一次、出队一次，总共是 O(2n) = O(n)。
  2. 队列里存下标而不是值：因为需要判断队头元素是否超出窗口范围（deque.peekFirst() <= i - k）。
  3. 变体题 [239] 滑动窗口最大值、[480] 滑动窗口中位数（中位数需要用两个堆或一个平衡二叉搜索树）。

Q30：课程安排（Medium）【图/BFS】

一句话总结

拓扑排序：用 BFS + 入度数组，不断移除入度为 0 的节点，如果能移除所有节点说明无环（可以取完所有课程），否则有环。

深度解析

方法一：BFS（Kahn 算法）

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 boolean canFinish(int numCourses, int[][] prerequisites) {
    // 构建邻接表和入度数组
    List<Integer>[] graph = new ArrayList[numCourses];
    int[] inDegree = new int[numCourses];
    
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new ArrayList<>();
    }
    
    for (int[] pre : prerequisites) {
        graph[pre[1]].add(pre[0]); // pre[1] -> pre[0]
        inDegree[pre[0]]++;
    }
    
    // BFS：把所有入度为 0 的节点加入队列
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int count = 0;
    while (!queue.isEmpty()) {
        int curr = queue.poll();
        count++;
        
        for (int next : graph[curr]) {
            inDegree[next]--;
            if (inDegree[next] == 0) {
                queue.offer(next);
            }
        }
    }
    
    return count == numCourses; // 是否能取完所有课程
}

方法二：DFS（判断有向图是否有环）

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
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = new ArrayList[numCourses];
    for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();
    for (int[] pre : prerequisites) {
        graph[pre[1]].add(pre[0]);
    }
    
    int[] visited = new int[numCourses]; // 0=未访问, 1=访问中, 2=已访问
    
    for (int i = 0; i < numCourses; i++) {
        if (!dfs(graph, i, visited)) return false;
    }
    return true;
}

private boolean dfs(List<Integer>[] graph, int node, int[] visited) {
    if (visited[node] == 1) return false; // 发现环
    if (visited[node] == 2) return true;  // 已经访问过，无环
    
    visited[node] = 1; // 标记为访问中
    for (int next : graph[node]) {
        if (!dfs(graph, next, visited)) return false;
    }
    visited[node] = 2; // 标记为已访问
    return true;
}

复杂度分析：

  • BFS：时间 O(V + E)，空间 O(V + E)
  • DFS：时间 O(V + E)，空间 O(V)

面试加分回答

  1. BFS vs DFS 拓扑排序的区别：BFS 可以得到拓扑序（出队顺序），DFS 只能判断是否有环（后序遍历逆序是拓扑序）。
  2. visited 数组的三个状态：0=未访问，1=访问中（在递归栈中），2=已访问。如果在 DFS 过程中遇到状态 1 的节点，说明有环。
  3. 变体题 [207] 课程安排 I（判断是否有环）、[210] 课程安排 II（输出拓扑序）。

总结：30 道题的刷题路线

1
2
3
4
5
第1周：数组 + 哈希表 + 双指针（题1-5, 11-14）
第2周：链表（题6-10）
第3周：树（题15-18）
第4周：动态规划（题19-23）
第5周：回溯 + 并查集 + 堆（题24-30）

最后的最后：这 30 道题不是让你背答案，而是理解”为什么这么做”。每道题至少亲手写 3 遍，直到能在 15 分钟内完整写出为止。祝大家 Offer 拿到手软！

如有错误欢迎指正，转载请注明出处。

面试准备 > 算法
#面试 #八股文 #算法 #LeetCode #高频题
算法面试八股文——30道LeetCode高频题（BAT面试必刷）
https://whyalwaysme.lol/2026/06/08/2026-06-07-algorithm-interview-deep/
作者
Cassiur
发布于
2026年6月8日
许可协议