LeetCode 热题100快速通关指南（附模板） (优化完整版，真人心得版，持续更新)_leetcode热题100道怎么刷

LeetCode 热题100快速通关指南 (优化完整版)

目录

1. 哈希(Hash)
2. 双指针(Two Pointers)
3. 滑动窗口(Sliding Window)
4. 子串(Substring)
5. 普通数组(Array)
6. 矩阵(Matrix)
7. 链表(Linked List)
8. 二叉树(Binary Tree)
9. 图论(Graph)
10. 回溯(Backtracking)
11. 二分查找(Binary Search)
12. 栈(Stack)
13. 堆(Heap)
14. 贪心算法(Greedy)
15. 动态规划(DP)
16. 高级动态规划
17. 技巧(Tricks)
18. 字符串算法(String)
19. 并查集(Union Find)
20. 学习路线图
21. 快速学习技巧

1. 哈希 (Hash)

• 核心思想：利用哈希映射快速查找、统计频率或建立键值对应关系。

• 常用集合：哈希表（如 HashMap）。

• 口诀记忆：“一看配对就哈希，空间换时间是王道”

• 时间复杂度：查找 O(1)，构建 O(n)

• 空间复杂度：O(n)

• 我的心法与模板：

  • 心法：一看到题目要求\"查找\"、“配对”、“计数，分组”，第一反应就是哈希表。它是用空间换时间的利器，能把 O(N²) 的暴力查找降到 O(N)。
  • 优化模板 (以\"两数之和\"为例)：

    import java.util.*;public int[] twoSum(int[] nums, int target) { // 边界检查 if (nums == null || nums.length < 2) return new int[0]; // 1. 创建哈希表 Map<Integer, Integer> map = new HashMap<>(); // 2. 遍历数组 for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; // 3. 边遍历边检查 if (map.containsKey(complement)) {////重点！ // 4. 找到，立即返回 return new int[] { map.get(complement), i }; } // 5. 没找到，将当前元素存入哈希表 map.put(nums[i], i); } // 6. 遍历完没找到，返回空数组（比异常更友好） return new int[0];}

• 经典题目：

  • LeetCode 1: 两数之和（模板，学会边遍历边检查和put入hashmap。
    不能直接把数组放入hashmap中（比如put（3，2）会覆盖（3，1）））
  • LeetCode 49: 字母异位词分组（模板，边遍历边检查，字母异位先变为数组，再排序，学会哈希用在分组上（键是有序字母，值分组，是数组））
  • LeetCode 128: 最长连续序列（模板，一边遍历一边检查，找到开头非常关键！）

  真人心得：
  关键概念：哈希的优点就是可以将遍历的当前元素和某个附带信息（比如下标）存起来，供后面的遍历使用（快速查找！）。而后面具体如何使用就是按照某种规则去进行快速查找，比如两数之和就是按照（相加得到预期值），而字母异位词分组就是按照（字母相同，顺序不同，规则就是排序后相同）进行快速查找，而最长连续序列就是按照（是否是某个序列的开头，规则就是没有比当前更加小的值了。）去查找。
  可以看得出后面两个规则都要进行简单的推理。

2. 双指针 (Two Pointers)

• 核心思想：通过快慢指针或左右指针缩小搜索范围，降低时间复杂度。

• 常用集合：数组、链表。

• 口诀记忆：“有序数组左右夹，原地修改快慢跑”

• 时间复杂度：O(n)

• 空间复杂度：O(1)

• 比喻：两个人同时在跑道上跑步，速度不同或者从不同位置开始

• 我的心法与模板：

  • 心法：看到有序数组的配对问题，立刻想左右指针。看到需要原地修改数组或链表找环/中点，立刻想快慢指针。

    • 需要注意指针指针移动是否独立于循环，如果是，考虑while循环！
    • 对索引没有要求的，比如求和，可以考虑排序

  • 模板 (左右指针，适用于有序数组)：

    public int[] twoSumSorted(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) {///////左右指针需要用while int sum = nums[left] + nums[right]; if (sum == target) { // 找到了，根据题目要求处理 return new int[]{left, right}; } else if (sum < target) { left++; // 和太小，左指针右移增大和 } else { // sum > target right--; // 和太大，右指针左移减小和 } } return new int[0]; // 未找到}

  • 模板 (快慢指针，适用于原地修改数组，如\"移动零\")：

    public void moveZeroes(int[] nums) { int slow = 0; // slow 指向下一个非零元素要放置的位置 for (int fast = 0; fast < nums.length; fast++) { if (nums[fast] != 0) { // 交换元素（更通用的写法） int temp = nums[slow]; nums[slow] = nums[fast]; nums[fast] = temp; slow++; } }}想象你是餐厅老板，餐厅里有很多顾客：

• fast指针：像服务员一样快速在餐厅里巡视
• slow指针：像领班一样负责安排顾客就座

你的任务是把所有VIP客户（非零元素）安排到餐厅前排座位，普通客户（零元素）安排到后排。
对于移动0的题目，我们看的对象应该是非0，因为非0是vip用户。简单点说就是把由快指针在前面找vip，找到了就把放到slow的位置。
```

真人心得：
所谓配对，就是几个元素遵守某个规则得到预期值。
而我们要做的就是找出遵守这个规则的元素。
既然是与规则相关，那么将整个数组排序，有利于我们根据规则找到值。
这就是用双指针解决两数之和的思路，就是一个有序数组，左右指针，
然后夹逼（计算左右指针按照规则得到的值与预期值相比如何，如果小了，就移动左边的指针，如果大了就移动右边指针。）
注意：为什么开始的两数之和使用哈希解决，因为要返回的是下标，哈希可以直接存储下标。
如果不考虑效率的话，对于哈希能解决的题目（这里特指规则比较简单的，比如加减法），双指针都能实现。

现在看三数之和：属于我们分析的按照某个规则得到预期值的情况。a+b+c=0；变成a+b=-c；
这样就是变成两数之和了，只是将规则变化了一下。他与用双指针解决两数之和的区别就是它的合是变化的，这很好解决。
记得排序，这是左右指针解决找到按某个规则都得到预期值的元素的关键！！

左右指针关键概念：排序，按某个规则得到预期值，夹逼。
前后指针关键概念：在原数组修改。

• 经典题目：
  • LeetCode 15: 三数之和（属于遵守某个规则（加法得到预期值0）的情况，也就是三个元素配对出0的情况，用左右指针。）
  • LeetCode 283: 移动零（属于在原地修改数组，用快慢指针。思想参考：将vip用户提到最前面）
  • LeetCode 141: 环形链表
  • LeetCode 11：盛最多水的容器（属于遵守某个规则找到预期值（能盛最多水）的情况，也就是两个数据配对出某个值。
    左右指针，夹逼。思想：左右指针，在必须移动一个指针的情况下导致宽减一的情况下，必须选可以让高变大的方向移动指针。）

3. 滑动窗口 (Sliding Window)

• 核心思想：维护一个动态窗口，动态调整窗口大小。

• 常用集合：哈希表、数组。

• 口诀记忆：“连续子串滑窗口，左右指针配哈希”

• 时间复杂度：O(n)

• 空间复杂度：O(k)，k是窗口内不同字符的数量

• 比喻：公交车上乘客上车(右指针)和下车(左指针)，保持车上满足特定条件的乘客

• 我的心法与模板：

  • 心法：题目要求\"连续子数组/子串\"的\"最长/最短/数量\"问题，99% 是滑动窗口。本质是双指针的优化。
  • 优化模板 (无重复字符的最长子串 - 具体化版本)：

    public int lengthOfLongestSubstring(String s) { // 1. 初始化窗口和结果 Map<Character, Integer> window = new HashMap<>(); int left = 0, right = 0; int maxLen = 0; // 2. 右指针扩大窗口 while (right < s.length()) { char c = s.charAt(right); right++; window.put(c, window.getOrDefault(c, 0) + 1); // 3. 具体的收缩条件：当窗口中有重复字符时 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. 结果更新：每次调整窗口后更新最长子串长度

真人心得：
我们之前学了双指针合哈希，滑动窗口就是双指针合哈希的结合！
既然是结合了哈希合双指针，那就分析。
哈希的优点就是可以将遍历的当前元素和某个附带信息（比如下标）存起来，供后面的遍历使用（快速查找！）。
而双指针的优点就是可以在遍历的过程中，动态调整窗口大小（比如左指针和右指针夹逼）。
那么这样看来双指针不就是等于移动窗口了？
当然不是！
我们前面的双指针的题目是（找到几个元素，这几个元素按照某个规则得到预期值），而我们前面碰到的规则比如三数之和，盛最多水的容器，这些规则都是简单的加法。
而滑动窗口用到哈希的重点就是规则变复杂了，也就是需要哈希存储额外的信息来辅助实现规则。

比如无重复字符的最长子串，规则就是（子串内不能有重复字符），这个规则就比较复杂了，不能简单的用加法来实现。
无重复字符的最长子串的思路：
用快慢指针形成窗口（就是快的指针一直往前移动，当出现重复了，一定是窗口里的某个元素和快指针目前指向的元素重复了，此时就按照规则–子串内不能有重复字符，一直移动左边的指针直到符合规则）。
它的规则用hash具体来辅助就是时刻记录窗口类的字符和对应的出现次数，当出现次数大于1了，就说明有重复字符了，这时候就需要收缩窗口了。

现在以【找到字符串中所有字母异位词】题目为例。
规则就是窗口内出现字符的次数与给定的目标一致，
潜在规则就是窗口的大小和给定目标的大小一样。
就像上一题一样，用哈希来存储，key就是字符，value就是对应字符出现的次数。
这里有个优化小提示：凡是用哈希存储连贯英文字符的值和对应的频率，都可以用数组来代替。
因为有26个小写英文，可以直接用一个简单的大小为26的数组a[]来代替哈希表，a[1]=3就代表b的出现次数是3。
继续，
依旧是快慢指针形成窗口，但是窗口初始大小和目标大小一样，然后通过判断数组（也就是哈希）是否等于目标的数组（就是对应字母和对应频率都相同）。然后每次移动一格。
这一题反而比上一题简单，因为窗口是固定的。

关键概念：可以看出，关键就是规则的获取和转化，尤其考虑如何用哈希来辅助判定规则，这是重点！！

• 经典题目：
  • LeetCode 3: 无重复字符的最长子串（一个弹性的横线窗口，用hash存窗口内的各个字母的次数）
  • LeetCode 76: 最小覆盖子串
  • LeetCode 438: 找到字符串中所有字母异位词（hashmap是降低排序消耗的关键，对于字符串计频率数，可以直接用普通数组代替hashmap实现同样的效果，注意边界）：
  • while(right<s.length()-1) 先移动，后判断

4. 子串 (Substring)

• 核心思想：滑动窗口（连续子串）、前缀和 + 哈希表（子数组和）。

• 常用集合：哈希表、单调队列。

• 时间复杂度：O(n)

• 空间复杂度：O(n)

• 我的心法与模板：

  • 心法：如果题目和\"子数组的和\"有关，立刻想\"前缀和 + 哈希表\"。preSum[j] - preSum[i] = k 这个公式是解题关键。
  • [[模板 (前缀和 + 哈希表，求和为 K 的子数组)]]：

    public int subarraySum(int[] nums, int k) {// 1. 初始化哈希表（记录每种前缀和出现的次数）Map<Integer, Integer> map = new HashMap<>();// 重要：初始化前缀和为0的出现1次// 为什么？处理从头开始的子数组（如整个数组）map.put(0, 1);int preSum = 0; // 当前累计的前缀和int count = 0; // 满足条件的子数组个数// 2. 遍历数组for (int num : nums) { // 更新到当前位置的前缀和 preSum += num; // 3. 关键：查找符合条件的前缀和 // preSum[j] - preSum[i] = k ⇒ preSum[i] = preSum - k // 看是否在之前出现过这种前缀和 if (map.containsKey(preSum - k)) { count += map.get(preSum - k); // 添加出现次数 } // 4. 将当前前缀和存入哈希表 // 用于后续查找（注意：必须在检查后再存入） map.put(preSum, map.getOrDefault(preSum, 0) + 1);}return count;

}
```

• 经典题目：
  • LeetCode 560: 和为K的子数组
  • LeetCode 53: 最大子数组和
  • LeetCode 209: 长度最小的子数组

真人心得：
我们分析一下字串问题的解决，一般此问题都是按照某个规则得到字串，然后有可能是获取字串，也有可能是获取符合子串的个数。
其实同样是用移动窗口（现在学到这里了，移动窗口其实是个概念，可以是单个指针和开始元素形成窗口，也可以是双指针按照某个规则移动），本质就是指针移动，按照我们的概念，其实一个单遍历也是指针移动，也可以形成窗口。
按照惯例，就是先形成窗口，然后再获取并且分析规则。
以LeetCode 560: 和为K的子数组为例：
规则是：该数组中和为 k 的子数组的个数 。
关键是规则的分析：这里用到了前缀和的概念，某个元素的前缀和就是是从0开始到当前位置的元素和。
preSum[j] - preSum[i] = K
⇒ preSum[i] = preSum[j] - K
简单点就是说我们可以将我们符合规则的数组转换为【当前元素的前缀合减去k值，如果得到的值是一个前缀和，并且是我们已经遍历过的，那就说明它们的差值，也就是相差的元素的合就是一个符合规则的数组。】
关键词，已经遍历过的，说明要用哈希（因为可能会有负数，导致一个前缀和出现多次），可以看出，哈希的功能其实就是缓存，缓存了就不要像暴力法再次遍历了。
其实没什么高大上的，前面我们解决三数之合问题时，不是就把a+b+c=0，转换成了a+b=-c吗？然后一边遍历（缩小窗口），然后对窗口里的左右指针（也可以看作小窗口）进行夹逼，因为规则简单，就没有用到哈希。
这里的转换不就同样是把左边的因子移动到了右边，这就是前缀和，明明这么简单的转换概念，如果是高中的我们肯定轻而易举，可是到算法里面就找不出来呢？因为这是隐藏的信息，我们要时刻拥有转换规则的思维。
我们得到了每个遍历的前缀和（也就是数组），然后将其放入哈希表中，供后来使用，如果后面某个数组按照规则转换的公式得到了另一个数组能够在哈希表中找到，那么这两个数组中间的元素就是符合规则的子数组。

本质分析：
根据上面一题的分析，那不就是移动窗口吗？为什么还要分为字串类型的题目了，我们要找到本质，从现在来看，我们学会了哈希（缓存数据，避免暴力遍历，为什么要缓存呢？因为遍历到后面时，规则可能要利用到前面的信息），它的本质就是缓存数据供后面使用。
我们还学会了指针移动（包括双指针和移动窗口）它的本质其实就是帮助我们优化遍历（多样化的遍历，也避免了暴力遍历），至于附带的什么排序，夹逼，用哈希记录对应字符串的频率或者用哈希保存前缀和，这都是辅助我们利用规则。
三个本质：缓存数据供后面使用，指针优化遍历，转换并利用规则，如果规则简单，题目要求的返回信息少，就不用哈希，如果题目规则可能复杂一点，就需要用到哈希提前缓存的数据辅助我们在后面的运算。
现在我们就得出结论，哈希，指针移动（双指针，移动窗口）都是算
法必备的技能，而转换并利用规则我们可以当作高中题目去转换思考，思考如何转换成可以用哈希存储的规则！
有时候哈希不够用了或者说不是最佳的呢？那就还有队列和栈甚至是数组和单个int值！（这也就是前面存储英文字符时为什么可以用数组）。
重点就是将规则转换为可以用某种数据结构存储的形式，避免暴力遍历！
现在为止，我们已经认识了何为算法了！，算法的本质已经窥见一二了，避免了解题没有头绪和思路，跳出了就题论题的局限。

现在我们看题目
[LeetCode 239. 滑动窗口最大值]
三个本质：缓存数据供后面使用（可以用合适的数据结构辅助规则），指针优化遍历，转换并利用规则
让我们先把本质记录在这里。
首先先获取规则：滑动窗口中的最大值 。
我们一开始想道可以这样解决，每次滑动窗口移动时，都用一个int值（这也可以算作是缓存）遍历一次窗口中的值，记录下窗口中最大的值，然后返回。每次遍历都是这样。
可这是一个困难题目，怎么会这么简单，肯定需要优化，想想我们的要素，用于缓存的数据结构（辅助规则），指针优化遍历！
很好，按照我们的三要素，我们很容易就得到了优化算法的思路，从数据结构和指针（遍历）移动方式和规则理解下手。
我们是否可以这样考虑，用一个双端队列来缓存窗口中的值，当未来一个值进入窗口时，如果他比当前窗口中的最大值还大，那么他一定就是最大的值（此时删除队列中所有比他小的值）如果进来的值比他小，那么就这个小的值有可能成为将来最大的值（因为最大的值可能会移除窗口），当然还需要考虑判断队列头部的最大值是否已经移出窗口（这个逻辑需要用索引判定，只需对比 “索引是否 ≥ 窗口左边界）。
为什么要用双端队列呢？因为我们需要在窗口滑动时，能够快速地从两端添加和删除元素(先进先出的特性)。这样最大值永远都是队列的头部元素（这里你可以尝试简单的举例）

总结：可以看出数据结构是优化规则的关键！理解各种数据结构的特点是理解和转换规则的关键！！

5. 普通数组 (Array)

• 核心思想：贪心、排序、双指针、数学推导，动态规划。

• 常用集合：数组（原地修改）。

• 时间复杂度：取决于具体算法，通常为O(n)或O(nlogn)

• 空间复杂度：通常为O(1)或O(n)

• 我的心法与模板：

  • 心法：当题目要求 O(1) 空间复杂度，且数组元素范围在 [1, N] 之间时，可以把数组本身当作哈希表，利用正负号或交换元素到对应索引位置来标记信息。这叫\"原地哈希\"。
  • 模板 (原地哈希，找缺失的第一个正数)：

    public int firstMissingPositive(int[] nums) { int n = nums.length; // 1. 将所有数字放到它应该在的位置上 (nums[i] 应该在 nums[nums[i]-1]) for (int i = 0; i < n; i++) { while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // 交换 nums[i] 和 nums[nums[i] - 1] int temp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = temp; } } // 2. 再次遍历，找到第一个不在正确位置上的数字 for (int i = 0; i < n; i++) { if (nums[i] != i + 1) { return i + 1; } } return n + 1;}

• 经典题目：

  • LeetCode 41: 缺失的第一个正数（原地哈希）

  • LeetCode 442: 数组中重复的数据

  • LeetCode 287: 寻找重复数

  • LeetCode 53: 最大子数组和（注意：这是一个贪心问题，使用 Kadane 算法（动态规划），也可以用前缀和）

  • LeetCode 56：合并区间。(先排序，再合并)

  • LeetCode 189：轮转数组。(技巧，三次反转，先反转自身，在反转前k个元素，最后反转后面的元素。)

    真人心得：
    数组篇是在哈希，移动窗口（双指针），之后的，而前面我们获得了算法的基本能力（哈希缓存，遍历优化（指针或者窗口））。

    这里就是数组篇的基本操作了，包括动态规划（其实也可以用前缀和思想），排序，反转（需要记忆技巧），原地哈希，除了反转外，其他的多少都在前面接触过一些了，如果不用动态规划解题。

    主要讲原地哈希的思想：
    想想以前我们是怎么做的，用哈希缓存，遍历数组，这样空间复杂度就是O(n)了，对于某些题目，这样是为了判断某个值是否存在。
    ==本质：原地哈希就是将这个判断功能用在原本数组上，比如判断nums【i】是否存在，假设nums【2】=3，那么就将nums【3】变为负数，表示3存在。相当于值是key（3），值代表的索引的符号是value（通过负号判断），就是加入了一个负号，实现了功能复用。对于具体题目可能要遍历几次，因为至少有一次要调整符号。.
    也就是说通过索引判定一个数值是否存在，而索引是有序的。

6. 矩阵 (Matrix)

• 核心思想：模拟、哈希表标记、双指针。

• 常用集合：二维数组。

• 时间复杂度：O(m*n)，m和n是矩阵的行数和列数

• 空间复杂度：通常是O(1)，有时需要O(m+n)或O(m*n)

• 我的心法与模板：

  • 心法：处理矩阵问题，关键是控制好边界和方向。对于旋转、螺旋等问题，可以一层一层地处理，或者用方向数组 int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}} 来简化方向切换。
  • 模板 (螺旋矩阵)：

    public List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<>(); if (matrix == null || matrix.length == 0) return result; int top = 0, bottom = matrix.length - 1; int left = 0, right = matrix[0].length - 1; while (top <= bottom && left <= right) { // 从左到右 for (int i = left; i <= right; i++) { result.add(matrix[top][i]); } top++; // 从上到下 for (int i = top; i <= bottom; i++) { result.add(matrix[i][right]); } right--; // 从右到左 (检查边界) if (top <= bottom) { for (int i = right; i >= left; i--) { result.add(matrix[bottom][i]); } bottom--; } // 从下到上 (检查边界) if (left <= right) { for (int i = bottom; i >= top; i--) { result.add(matrix[i][left]); } left++; } } return result;}

• 经典题目：

  • LeetCode 54: 螺旋矩阵（四个指针，其他方法参考官解）

  • LeetCode 48: 旋转图像（可以找到每一行转换到每一列的坐标变化规则，然后用辅助矩阵解决。 但是题目不允许，可以先水平镜像反转，再按照对角线反转。每个反转需要两个循环，注意指针遍历技巧。）

  • LeetCode 73: 矩阵置零（懂映射，用额外的两个数组记录出现0的行和列，然后用两个数组去更新矩阵。当然，更基础的还是模拟算法。）

  • LeetCode 240：搜索二维矩阵II（由于这个题目时有序的，可以从左上角，当作二叉树，左移变小，下移变大。迟早能找到。
    也可以对每一层使用二分查找。）

    真人心得，矩阵问题常常要考虑边界问题，

7. 链表 (Linked List)

• 核心思想：指针操作、递归、哈希表辅助。

• 常用集合：指针、哈希表。

• 口诀记忆：“虚拟头节点是神器，快慢指针找环中”

• 时间复杂度：通常是O(n)

• 空间复杂度：通常是O(1)，递归解法是O(n)

• 比喻：链表操作就像扯线，注意不要弄断，必要时用安全绳(dummy节点)

• 我的心法与模板：

  • 心法：链表题目的精髓在于指针操作。为了防止指针丢失，经常需要一个 prev 指针来保存前一个节点。对于复杂操作，引入一个**虚拟头节点 (dummy head)** 可以极大地简化边界条件处理（如删除头节点）。
  • 模板 (反转链表)：

    public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; // 1. 保存下一个节点 curr.next = prev; // 2. 反转指针 prev = curr;  // 3. prev 前进 curr = nextTemp;  // 4. curr 前进 } return prev; // 新的头节点是 prev}

  • 万能模板 (虚拟头节点版本)：

    public ListNode universalTemplate(ListNode head) { // 1. 创建虚拟头节点，简化边界处理 ListNode dummy = new ListNode(0); dummy.next = head; // 2. 定义工作指针 ListNode prev = dummy; // 前驱指针 ListNode curr = head; // 当前指针 // 3. 遍历处理 while (curr != null) { // ... 根据具体题目处理 curr 节点 ... // 标准前进步骤 prev = curr; curr = curr.next; } // 4. 返回新的头节点 return dummy.next;}

• 经典题目：

  • LeetCode 206: 反转链表（迭代（使用简单的prev+curr+nextTemp）三个指针代表分别当前节点，当前的前一个和当前的后一个，逻辑就是当前指针指向前一个指针，然后后移到nextTemp。 当然，也可以用递归）
  • LeetCode 141: 环形链表（经典的快慢指针，不解释。）
  • LeetCode 142: 环形链表 II（快慢指针找到相遇点后，再从相遇点和头节点同时出发，直到再次相遇）
  • LeetCode 21: 合并两个有序链表（创建一个虚拟头节点（要有内容）代表是一个合并数组的开始，然后两个指针分别在两个链表上滑动，小的就放在合并链表后面。也可以用递归）
  • LeetCode 160： 相交链表（使用哈希表（set）或双指针）
  • LeetCode 234：回文链表（快慢指针找到中点，然后反转后半部分，最后比较前后两部分是否相同）
  • LeetCode 2：两数相加（==使用虚拟头节点，==两个指针分别在两个链表上滑动，创建虚拟节点，以后每一次节点数值相加都要创建一个新的节点接入返回链表）
  • ==LeetCode 19: 删除链表的倒数第 N 个节点（快慢指针，快指针先走N步，然后两个指针一起走，直到快指针到达末尾，此时慢指针就是要删除的节点的前一个节点，然后删除即可。）
  • LeetCode 24：两两交换链表中的节点（虚拟头节点。要注意指针切换指向时的顺序，确保先切换的不会影响后切换的，注意链表单双情况）
  • LeetCode 25：K 个一组翻转链表（考的是设计能力，先遍历一次判定需要几次反转，然后定义一个反转方法，返回三个节点（用类包装起来），三个节点分别是反转链表的第一个节点，反转链表的最后一个节点，反转链表下一个链表的第一个节点（三个节点的获取参考26题，非常简单。），然后创建一个虚拟头节点（curr指针在上面移动），每次curr指向反转链表的第一个节点，然后移动到反转链表的最后节点，然后用下一个链表的第一个节点继续调用链表反转方法。）
  • LeetCode 138：复制带随机指针的链表（使用哈希表记录原节点和新节点的映射关系，或者使用原地哈希方法，将新节点插入到原节点后面，然后再分离出新链表。）
  • LeetCode 148：排序链表（使用归并排序，分治思想。每次将链表拆分成两个，可以用快慢指针获取中点，然后第二条链表的头节点就是终点的下一个。合并就是简单的对比合并。此题的前提是先弄清除归并数组排序==（建议b站看一个10分钟左右的课）
  • LeetCode 23：合并K个升序链表（分治归并，参考上一题，定义一个排序方法，参数就是两个链表的头节点，然后就是分治，当前数组左右划分递归。）
  • LeetCode 146：LRU缓存机制（定义一个节点类，包括前后指针，key和value，其中key是为了通过链表节点定位哈希节点。
     定义一个哈希map，包括size和capacity，还有虚拟的头尾节点。
     初始化方法。
     get方法：如果没有节点返回-1，否者就获取，然后【移动到链表头部，先删除，后放入】。
     put方法：如果不存在，就创建然后【放到链表头部】，如果链表满了，就【删除尾部节点】。如果key已经存在，更新节点的value值，然后移动到链表头部。）

真人心得：
链表中经常用到双指针，这也导致了快指针会出现两张情况（快指针指向最后一个节点，快指针指向最后一个节点的前一个，也就是链表的节点个数可能是单个，也可能是双数），此时的循环停止条件要是(fast!=null&&fast.next!=null)。
还要注意循环停止条件，while(l1!=null&&l2!=null)表示只要有一个为空就停止，while(l1!=null&||2!=null)，只要有一个不为空就继续。
还要注意边界问题，比如就是两个链表，两个指针分别在上面移动，列如两数之和，可以用三元式处理。

链表题常用的技巧：
1. 快慢指针（双指针）（比如环形链表，相交链表，删除到数第n个节点，需要将链表划分为几个部分，通过数学节点计算出规律。）
2. 虚拟节点（简化边界处理，比如合并两个有序链表，两数相加，两两交换链表中的节点。虚拟节点如果参与原链表的修改，最好先是指向头节点。如果是返回新的，则无所谓。）
3. 三元式处理边界问题（如链表长度不一致时）
4. 反转链表（迭代或递归）
5. 双指针滑动（如合并两个有序链表）
6. 哈希表辅助（如判断是否有环、找相交节点）
7. 递归思想：有时间再看。
8. 归并思想（排序链表）：将每次当前状态当作一个节点，递归左边和右边的时候会派生两个子节点（类似树），当前状态可见的变量和传入到子节点的参数，和子节点返回到当前节点的参数要弄清楚。

8. 二叉树 (Binary Tree)

• 核心思想：递归、迭代（栈/队列）、分治、BFS/DFS。

• 常用集合：栈、队列、哈希表。

• 口诀记忆：“递归三问终止条件，当前处理递归调用”

• 时间复杂度：通常是O(n)，n是节点数

• 空间复杂度：递归O(h)，h是树高，最坏情况O(n)

• 比喻：二叉树遍历就像探索迷宫，有不同的探索策略(前中后序)

• 我的心法与模板：

  • 心法：90% 的二叉树问题都可以用递归解决。写递归代码，只需要思考三件事：
    1. 终止条件：if (root == null) return ...;
    2. 当前层做什么：处理 root 节点。
    3. 递归调用：调用 dfs(root.left) 和 dfs(root.right)，并思考如何利用它们的返回值。
  • 模板 (递归遍历)：

    void traverse(TreeNode root) { if (root == null) { return; } // 前序位置: 在这里处理 root 节点 System.out.println(root.val); traverse(root.left); // 中序位置: 在这里处理 root 节点 traverse(root.right); // 后序位置: 在这里处理 root 节点}

  • 模板 (层序遍历 - BFS)：

    public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); currentLevel.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(currentLevel); } return result;}

• 经典题目：

  • LeetCode 104: 二叉树的最大深度
  • LeetCode 94: 二叉树的中序遍历
  • LeetCode 236: 二叉树的最近公共祖先

9. 图论 (Graph)

• 核心思想：DFS/BFS、拓扑排序、Trie 树。

• 常用集合：邻接表、队列、Trie 节点。

• 时间复杂度：通常是O(V+E)，V是顶点数，E是边数

• 空间复杂度：通常是O(V+E)

• 比喻：图就像社交网络，找朋友用BFS(最少中间人)，找族谱用DFS(完整关系链)

• 我的心法与模板：

  • 心法：图论问题第一步是建图（通常用邻接表 Map<Integer, List>）。然后根据问题选择遍历方式：求最短路径用 BFS，求连通性/所有路径用 DFS。为了防止走回头路，需要一个 visited 集合。
  • 模板 (DFS 遍历图)：

    // visited 集合，防止重复访问Set<Integer> visited = new HashSet<>();void dfs(int startNode, Map<Integer, List<Integer>> graph) { if (visited.contains(startNode)) { return; } visited.add(startNode); // ... 处理 startNode ... for (int neighbor : graph.getOrDefault(startNode, new ArrayList<>())) { dfs(neighbor, graph); }}

  • 模板 (BFS 遍历图)：

    public int bfs(int start, int target, Map<Integer, List<Integer>> graph) { Queue<Integer> queue = new LinkedList<>(); Set<Integer> visited = new HashSet<>(); queue.offer(start); visited.add(start); int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int node = queue.poll(); if (node == target) return steps; for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) { if (!visited.contains(neighbor)) {  visited.add(neighbor);  queue.offer(neighbor); } } } steps++; } return -1; // 未找到路径}

• 经典题目：

  • LeetCode 200: 岛屿数量
  • LeetCode 207: 课程表
  • LeetCode 133: 克隆图

10. 回溯 (Backtracking)

• 核心思想：递归 + 剪枝（“做选择，撤销选择”）。

• 常用集合：栈（路径）、哈希表/数组（标记已用元素）。

• 口诀记忆：“路径选择终止条件，做选择递归撤选择”

• 时间复杂度：O(n!)或O(2^n)，取决于问题

• 空间复杂度：O(n)，递归栈的深度

• 比喻：回溯就像走迷宫，尝试每一条路，遇到死胡同就返回上一个路口继续尝试

• 我的心法与模板：

  • 心法：回溯是\"暴力枚举\"的优雅版，适用于所有\"组合、排列、子集、棋盘\"问题。它的框架是固定的，记住\"路径、选择列表、结束条件\"三要素。
  • 模板 (通用)：

    List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>(); // 记录路径void backtrack(int[] nums, int startIndex) { // 1. 终止条件 (根据题目需求) if (path.size() == k) { result.add(new ArrayList<>(path)); // 注意深拷贝 return; } // 2. 遍历选择列表 for (int i = startIndex; i < nums.length; i++) { // 剪枝操作 (可选，根据题目添加) if (used[i]) continue; // 3. 做选择 path.add(nums[i]); used[i] = true; // 4. 进入下一层决策树 backtrack(nums, i + 1); // 组合问题用i+1，排列问题用0 // 5. 撤销选择 path.removeLast(); used[i] = false; }}

• 经典题目：

  • LeetCode 46: 全排列
  • LeetCode 78: 子集
  • LeetCode 39: 组合总和

11. 二分查找 (Binary Search)

• 核心思想：利用数组有序性，通过二分缩小搜索范围。

• 常用集合：数组。

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

• 空间复杂度：O(1)

• 比喻：就像猜数字游戏，每次都排除一半的可能性

• 我的心法与模板：

  • 心法：只要看到\"有序数组\"中的\"查找\"问题，就用二分法。关键在于循环条件 (left <= right) 和边界收缩 (left = mid + 1 或 right = mid - 1)，写对这两个，就成功了 99%。
  • 模板 (标准二分查找)：

    public int binarySearch(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; } else if (nums[mid] < target) { left = mid + 1; } else { // nums[mid] > target right = mid - 1; } } return -1; // 未找到}

  • 模板 (左边界搜索)：

    public 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是否越界或没找到 if (left >= nums.length || nums[left] != target) return -1; return left;}

• 经典题目：

  • LeetCode 704: 二分查找
  • LeetCode 33: 搜索旋转排序数组
  • LeetCode 34: 在排序数组中查找元素的第一个和最后一个位置

12. 栈 (Stack)

• 核心思想：利用 LIFO 特性（匹配、解码），或维护单调性（单调栈）。

• 常用集合：栈。

• 时间复杂度：O(n)

• 空间复杂度：O(n)

• 比喻：栈就像盘子堆叠，只能从顶部操作，单调栈就像俄罗斯方块中的砖块排列

• 我的心法与模板：

  • 心法：遇到\"括号匹配\"、\"消除相邻重复项\"等具有\"最近相关性\"的问题，用普通栈。遇到\"寻找下一个更大/更小元素\"的问题，用单调栈。
  • 模板 (单调栈，找下一个更大元素)：

    public int[] nextGreaterElement(int[] nums) { int[] result = new int[nums.length]; Stack<Integer> stack = new Stack<>(); // 存索引 for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { int prevIndex = stack.pop(); result[prevIndex] = nums[i]; } stack.push(i); } // 栈里剩下的元素没有下一个更大值 while (!stack.isEmpty()) { result[stack.pop()] = -1; } return result;}

  • 模板 (括号匹配)：

    public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); Map<Character, Character> map = new HashMap<>(); map.put(\')\', \'(\'); map.put(\'}\', \'{\'); map.put(\']\', \'[\'); for (char c : s.toCharArray()) { if (map.containsKey(c)) { // 是右括号 if (stack.isEmpty() || !stack.pop().equals(map.get(c))) { return false; } } else { // 是左括号 stack.push(c); } } return stack.isEmpty();}

• 经典题目：

  • LeetCode 20: 有效的括号
  • LeetCode 739: 每日温度
  • LeetCode 84: 柱状图中最大的矩形

13. 堆 (Heap)

• 核心思想：利用优先级特性处理 Top K 问题、中位数问题。

• 常用集合：优先队列 (PriorityQueue)。

• 时间复杂度：插入O(log n)，取顶O(1)，建堆O(n)

• 空间复杂度：O(n)

• 比喻：堆就像排队，但VIP客户(高优先级)可以插队到前面

• 我的心法与模板：

  • 心法：看到\"Top K\"或\"第 K 大/小\"的问题，立刻想堆。求 Top K 大，用小顶堆；求 Top K 小，用大顶堆。这样可以保证堆的大小始终为 K。
  • 模板 (求 Top K 大元素)：

    public List<Integer> topKLargest(int[] nums, int k) { // 1. 创建一个大小为 K 的小顶堆 PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); // 2. 遍历数组 for (int num : nums) { if (minHeap.size() < k) { minHeap.offer(num); } else if (num > minHeap.peek()) { // 如果当前元素比堆顶大 minHeap.poll(); // 弹出最小的 minHeap.offer(num); // 加入当前元素 } } // 3. 堆中剩下的就是 Top K 大元素 return new ArrayList<>(minHeap);}

  • 模板 (数据流中位数 - 双堆)：

    class MedianFinder { PriorityQueue<Integer> maxHeap; // 左半部分，大顶堆 PriorityQueue<Integer> minHeap; // 右半部分，小顶堆 public MedianFinder() { maxHeap = new PriorityQueue<>((a, b) -> b - a); minHeap = new PriorityQueue<>(); } public void addNum(int num) { if (maxHeap.isEmpty() || num <= maxHeap.peek()) { maxHeap.offer(num); } else { minHeap.offer(num); } // 保持平衡 if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(maxHeap.poll()); } else if (minHeap.size() > maxHeap.size()) { maxHeap.offer(minHeap.poll()); } } public double findMedian() { if (maxHeap.size() == minHeap.size()) { return (maxHeap.peek() + minHeap.peek()) / 2.0; } else { return maxHeap.peek(); } }}

• 经典题目：

  • LeetCode 215: 数组中的第K个最大元素
  • LeetCode 347: 前K个高频元素
  • LeetCode 295: 数据流的中位数

14. 贪心算法 (Greedy)

• 核心思想：局部最优 → 全局最优。

• 常用集合：数组、优先队列。

• 时间复杂度：通常是O(n)或O(nlogn)(如果需要排序)

• 空间复杂度：通常是O(1)或O(n)

• 比喻：就像爬山时总是选择最陡的路径，期望能最快到达山顶

• 我的心法与模板：

  • 心法：贪心没有固定模板，关键是找到贪心策略。思考\"为了让整体结果最优，我当前这一步应该怎么选？\"。通常需要排序来辅助决策。
  • 模板 (思路模板，以\"区间调度\"为例)：
    1. 明确贪心选择：每次都选择结束时间最早的那个区间。
    2. 证明其正确性：选择结束最早的区间，可以为后续的区间留出最多的可用时间，从而容纳更多的区间。
    3. 编码实现：

       public int eraseOverlapIntervals(int[][] intervals) { if (intervals.length == 0) return 0; // 1. 按结束时间升序排序 Arrays.sort(intervals, (a, b) -> a[1] - b[1]); int count = 1; int end = intervals[0][1]; // 第一个区间的结束时间 // 2. 遍历，选择不重叠的区间 for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] >= end) { // 找到了一个不重叠的区间 count++; end = intervals[i][1]; } } return intervals.length - count; // 需要删除的区间数}

• 经典题目：

  • LeetCode 455: 分发饼干
  • LeetCode 435: 无重叠区间
  • LeetCode 55: 跳跃游戏

15. & 16. 动态规划 (DP)

• 核心思想：状态转移，保存子问题结果。

• 常用集合：数组（一维/二维）。

• 时间复杂度：通常是O(n^2)或O(n*m)

• 空间复杂度：通常是O(n)或O(n*m)

• 比喻：“填表格”，每个格子的值依赖于之前计算过的格子

• 我的心法与模板：

  • 心法：DP 是硬骨头，但有套路。记住**“DP五步曲”**：
    1. 定义 dp 数组含义：dp[i] 或 dp[i][j] 代表什么？
    2. 找出状态转移方程：dp[i] 和 dp[i-1], dp[i-2]… 的关系是什么？
    3. 初始化 dp 数组：dp[0], dp[1] 等初始值是什么？
    4. 确定遍历顺序：是从前到后，还是从后到前？
    5. 返回最终结果：通常是 dp[n] 或 dp[n-1]。
  • 模板 (一维 DP，以\"爬楼梯\"为例)：

    public int climbStairs(int n) { if (n <= 1) return 1; // 1. 定义 dp 数组: dp[i] 表示爬到第 i 阶的方法数 int[] dp = new int[n + 1]; // 3. 初始化 dp[0] = 1; dp[1] = 1; // 4. 遍历 for (int i = 2; i <= n; i++) { // 2. 状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]; } // 5. 返回结果 return dp[n];}

  • 模板 (二维 DP，以\"不同路径\"为例)：

    public int uniquePaths(int m, int n) { // 1. 定义 dp 数组: dp[i][j] 表示到达 (i,j) 的路径数 int[][] dp = new int[m][n]; // 3. 初始化第一行和第一列 for (int i = 0; i < m; i++) dp[i][0] = 1; for (int j = 0; j < n; j++) dp[0][j] = 1; // 4. 遍历 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { // 2. 状态转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } // 5. 返回结果 return dp[m-1][n-1];}

• 经典题目：

  • LeetCode 70: 爬楼梯
  • LeetCode 62: 不同路径
  • LeetCode 5: 最长回文子串
  • LeetCode 322: 零钱兑换 (高级)
  • LeetCode 72: 编辑距离 (高级)

17. 技巧 (Tricks)

• 核心思想：位运算、摩尔投票、双指针、数学规律。

• 常用集合：数组、位运算。

• 时间复杂度：通常是O(n)

• 空间复杂度：通常是O(1)

• 我的心法与模板：

  • 心法：这些是\"神来之笔\"，需要专门记忆。位运算的异或 (XOR) 特别好用：a ^ a = 0, a ^ 0 = a。非常适合解决\"只出现一次/两次\"的问题。
  • 模板 (位运算，找只出现一次的数字)：

    public int singleNumber(int[] nums) { int result = 0; for (int num : nums) { result ^= num; // 所有成对的数都抵消为0，剩下那个单独的 } return result;}

  • 模板 (摩尔投票，找众数)：

    public int majorityElement(int[] nums) { int candidate = nums[0]; int count = 1; for (int i = 1; i < nums.length; i++) { if (count == 0) { candidate = nums[i]; count = 1; } else if (nums[i] == candidate) { count++; } else { count--; } } return candidate;}

• 经典题目：

  • LeetCode 136: 只出现一次的数字
  • LeetCode 169: 多数元素
  • LeetCode 338: 比特位计数

18. 字符串算法 (String)

• 核心思想：哈希表、滑动窗口、字符串匹配算法

• 常用集合：哈希表、Trie树

• 时间复杂度：KMP O(m+n)，暴力匹配O(m*n)

• 空间复杂度：通常是O(n)或O(字符集大小)

• 比喻：就像在书中查找特定句子，可以一个字一个字对比，也可以用巧妙的方法快速跳过

• 我的心法与模板：

  • 心法：字符串处理问题通常涉及模式匹配、统计或转换。对于匹配问题，如果是简单匹配用indexOf()，复杂匹配考虑KMP算法；对于统计，用哈希表；对于查找前缀，用Trie树。
  • 模板 (Trie树)：

    class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode node = root; for (char c : word.toCharArray()) { 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 = searchPrefix(word); return node != null && node.isEnd; } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; } private TrieNode searchPrefix(String prefix) { TrieNode node = root; for (char c : prefix.toCharArray()) { if (node.children[c - \'a\'] == null) { return null; } node = node.children[c - \'a\']; } return node; } class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEnd = false; }}

  • 模板 (KMP算法)：

    public int strStr(String haystack, String needle) { if (needle.length() == 0) return 0; // 构建next数组 int[] next = new int[needle.length()]; for (int i = 1, j = 0; i < needle.length(); i++) { while (j > 0 && needle.charAt(i) != needle.charAt(j)) { j = next[j - 1]; } if (needle.charAt(i) == needle.charAt(j)) { j++; } next[i] = j; } // 匹配过程 for (int i = 0, j = 0; i < haystack.length(); i++) { while (j > 0 && haystack.charAt(i) != needle.charAt(j)) { j = next[j - 1]; } if (haystack.charAt(i) == needle.charAt(j)) { j++; } if (j == needle.length()) { return i - needle.length() + 1; } } return -1;}

• 经典题目：

  • LeetCode 208: 实现 Trie (前缀树)
  • LeetCode 28: 实现strStr()
  • LeetCode 14: 最长公共前缀

19. 并查集 (Union Find)

• 核心思想：高效处理元素分组和合并

• 常用集合：数组

• 时间复杂度：几乎O(1)（路径压缩+按秩合并）

• 空间复杂度：O(n)

• 比喻：就像朋友圈，可以快速判断两个人是否属于同一个圈子，或将两个圈子合并

• 我的心法与模板：

  • 心法：并查集适用于动态连通性问题。当需要频繁判断两个元素是否连通，或者合并两个连通分量时，并查集可以做到近乎常数时间复杂度。
  • 模板：

    class UnionFind { private int[] parent; private int[] rank; // 树的高度 private int count; // 连通分量数量 public UnionFind(int n) { parent = new int[n]; rank = new int[n]; count = n; for (int i = 0; i < n; i++) { parent[i] = i; // 初始时每个节点的父节点是自己 } } // 查找根节点，包含路径压缩 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) { // 按秩合并，将较低的树连接到较高的树下 if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; // 高度增加 } count--; // 连通分量减少 } } // 判断两个元素是否连通 public boolean connected(int x, int y) { return find(x) == find(y); } // 获取连通分量数量 public int getCount() { return count; }}

• 经典题目：

  • LeetCode 200: 岛屿数量 (并查集解法)
  • LeetCode 547: 省份数量
  • LeetCode 684: 冗余连接

学习路线图

按照以下顺序学习算法，可以从易到难循序渐进：

第一阶段：基础算法与数据结构

1. 哈希表 - 简单直观，解决查找问题
2. 数组与双指针 - 处理有序数据，解决配对问题
3. 栈与队列 - 处理先进后出和先进先出问题
4. 二分查找 - 学习如何高效查找

第二阶段：链表与树

5. 链表 - 掌握指针操作
6. 二叉树 - 学习树的递归遍历
7. 堆 - Top K问题的解决方案

第三阶段：进阶数据结构

8. 滑动窗口 - 处理子串问题
9. 单调栈/队列 - 解决\"下一个更大\"类问题
10. 并查集 - 解决图的连通性问题

第四阶段：进阶算法

11. 回溯算法 - 组合/排列/子集问题
12. 贪心算法 - 局部最优解问题
13. 动态规划(基础) - 重叠子问题

第五阶段：高级算法

14. 图论算法 - DFS、BFS、拓扑排序
15. 高级动态规划 - 编辑距离、区间DP等
16. 字符串算法 - KMP、Trie树
17. 位运算与数学技巧 - 解决特殊问题

快速学习加速技巧

口诀记忆总结

• 哈希表：“一看配对就哈希，空间换时间是王道”
• 双指针：“有序数组左右夹，原地修改快慢跑”
• 滑动窗口：“连续子串滑窗口，左右指针配哈希”
• 链表：“虚拟头节点是神器，快慢指针找环中”
• 二叉树：“递归三问终止条件，当前处理递归调用”
• 回溯：“路径选择终止条件，做选择递归撤选择”
• 动态规划：“定义状态找转移，初始边界看遍历”
• 二分查找：“左右指针中间点，相等返回小则左”

30秒快速识别表

关键词 立刻想到 模板 “两数之和”、“配对” 哈希表 map.containsKey(target - num) “有序数组”、“target” 双指针/二分 left < right 夹逼 “连续子串”、“最长/最短” 滑动窗口 while (right < n) 扩窗口 “链表环”、“中点” 快慢指针 slow/fast 经典 “二叉树遍历” 递归 dfs(root.left), dfs(root.right) “全排列”、“组合” 回溯 backtrack(path, choices) “第K大”、“Top K” 堆 PriorityQueue “最优解”、“可能性” 动态规划 dp[i] = max(dp[i-1], ...) “判断连通” 并查集/BFS find(), union() “布局/路径” 图论 BFS寻最短路径 “位操作” 异或 a ^ a = 0