LeetCode 热题 100 算法分类与模板总结

LeetCode 热题 100 算法分类与模板总结

1. 哈希 (Hash)

• 核心思想：利用哈希映射快速查找、统计频率或建立键值对应关系。
• 常用集合：哈希表（如 HashMap）。
• 口诀记忆：'一看配对就哈希，空间换时间是王道'
• 时间复杂度：查找 O(1)，构建 O(n)
• 空间复杂度：O(n)
• 我的心法与模板：
  • 心法：一看到题目要求"查找"、"配对"、"计数，分组"，第一反应就是哈希表。它是用空间换时间的利器，能把 O(N²) 的暴力查找降到 O(N)。
• 经典题目：真人心得： 关键概念：哈希的优点就是可以将遍历的当前元素和某个附带信息（比如下标）存起来，供后面的遍历使用（快速查找！）。而后面具体如何使用就是按照某种规则去进行快速查找，比如两数之和就是按照（相加得到预期值），而字母异位词分组就是按照（字母相同，顺序不同，规则就是排序后相同）进行快速查找，而最长连续序列就是按照（是否是某个序列的开头，规则就是没有比当前更加小的值了。）去查找。 可以看得出后面两个规则都要进行简单的推理。
  • LeetCode 1: 两数之和（模板，学会边遍历边检查和 put 入 hashmap。不能直接把数组放入 hashmap 中（比如 put（3，2）会覆盖（3，1）））
  • LeetCode 49: 字母异位词分组（模板，边遍历边检查，字母异位先变为数组，再排序，学会哈希用在分组上（键是有序字母，值分组，是数组））
  • LeetCode 128: 最长连续序列（模板，一边遍历一边检查，找到开头非常关键！）

优化模板 (以"两数之和"为例)：

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];
}

2. 双指针 (Two Pointers)

• 核心思想：通过快慢指针或左右指针缩小搜索范围，降低时间复杂度。
• 常用集合：数组、链表。
• 口诀记忆：'有序数组左右夹，原地修改快慢跑'
• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 比喻：两个人同时在跑道上跑步，速度不同或者从不同位置开始
• 我的心法与模板：
  • 心法：看到有序数组的配对问题，立刻想左右指针。看到需要原地修改数组或链表找环/中点，立刻想快慢指针。
    • 需要注意指针移动是否独立于循环，如果是，考虑 while 循环！
    • 对索引没有要求的，比如求和，可以考虑排序
  • fast 指针：像服务员一样快速在餐厅里巡视
  • slow 指针：像领班一样负责安排顾客就座

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

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++;
        }
    }
}

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

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

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

现在看三数之和：属于我们分析的按照某个规则得到预期值的情况。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
        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] 之间时，可以把数组本身当作哈希表，利用正负号或交换元素到对应索引位置来标记信息。这叫"原地哈希"。
• 经典题目：
  • 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（通过负号判断），就是加入了一个负号，实现了功能复用。对于具体题目可能要遍历几次，因为至少有一次要调整符号。 也就是说通过索引判定一个数值是否存在，而索引是有序的。

模板 (原地哈希，找缺失的第一个正数)：

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;
}

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}} 来简化方向切换。
• 经典题目：
  • LeetCode 54: 螺旋矩阵（四个指针，其他方法参考官解）
  • LeetCode 48: 旋转图像（可以找到每一行转换到每一列的坐标变化规则，然后用辅助矩阵解决。但是题目不允许，可以先水平镜像反转，再按照对角线反转。每个反转需要两个循环，注意指针遍历技巧。）
  • LeetCode 73: 矩阵置零（懂映射，用额外的两个数组记录出现 0 的行和列，然后用两个数组去更新矩阵。当然，更基础的还是模拟算法。）
  • LeetCode 240：搜索二维矩阵 II（由于这个题目时有序的，可以从左上角，当作二叉树，左移变小，下移变大。迟早能找到。也可以对每一层使用二分查找。）真人心得，矩阵问题常常要考虑边界问题

模板 (螺旋矩阵)：

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;
}

7. 链表 (Linked List)

• 核心思想：指针操作、递归、哈希表辅助。
• 常用集合：指针、哈希表。
• 口诀记忆：'虚拟头节点是神器，快慢指针找环中'
• 时间复杂度：通常是 O(n)
• 空间复杂度：通常是 O(1)，递归解法是 O(n)
• 比喻：链表操作就像扯线，注意不要弄断，必要时用安全绳 (dummy 节点)
• 我的心法与模板：
  • 心法：链表题目的精髓在于指针操作。为了防止指针丢失，经常需要一个 prev 指针来保存前一个节点。对于复杂操作，引入一个虚拟头节点 (dummy head) 可以极大地简化边界条件处理（如删除头节点）。
• 经典题目：
  • 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 值，然后移动到链表头部。）

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

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;
}

模板 (反转链表)：

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
}

真人心得： 链表中经常用到双指针，这也导致了快指针会出现两张情况（快指针指向最后一个节点，快指针指向最后一个节点的前一个，也就是链表的节点个数可能是单个，也可能是双数），此时的循环停止条件要是 (fast!=null&&fast.next!=null)。 还要注意循环停止条件，while(l1!=null&&l2!=null) 表示只要有一个为空就停止，while(l1!=null||l2!=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)，并思考如何利用它们的返回值。
• 经典题目：
  • LeetCode 104: 二叉树的最大深度（递归，迭代，注意要用 size 标记每层个数，达到分层效果。建议迭代和递归都写一遍）
  • LeetCode 94: 二叉树的中序遍历（递归，迭代，morris 遍历，建议都写一遍）
  • LeetCode 226：翻转二叉树（简单的递归，秒了）
  • 对称二叉树（递归，自顶向下的递归，也就是不一定要递归到最底层才会得到结果。）
  • LeetCode 543：二叉树的直径（递归，自底向上，每次返回左边和右边的最大深度。由于直径可以不经过根节点，所有要定义一个全局变量记录。计算路径时，最好通过节点计算，也就是这条路径上的节点 -1，方便边界处理。）
  • LeetCode 102：二叉树的层序遍历（BFS，使用队列，两重循环进行分层。）
  • LeetCode 108：将有序数组转换为二叉搜索树（递归，注意中间节点的选择 mid，然后分治 mid-1 和 mid+1，注意停止条件 left>right）
  • LeetCode 98：验证二叉搜索树（递归（自顶向下），记录范围，每次递归检查当前节点是否正常，然后再递归检查。方法 2，中序升序：关键！：'每个节点只需大于它的直接前序节点，就能确保大于所有更早的节点'。）
  • LeetCode 230: 二叉搜索树中第 K 小的元素（递归，中序遍历，每次消耗使得 k-1，也就是当一个节点先用当前 k 去进行左递归，然后处理当前节点逻辑，当前节点 k-1，然后右递归，返回右递归后的 k，用标签记录 k=0 时的节点值，就是找到的。）
  • LeetCode:199：二叉树的右视图（BFS，使用队列，记录每层的最后一个节点，方法 2，递归。）
  • LeetCode 114: 二叉树展开为链表（方法 1：前序递归，根左右，可以看作是自顶向下，也就是创建一个虚拟节点，每次递归时，把当前节点接在虚拟节点的最后面，一定要断开左指针！（这样才符合改造）要注意当前节点左右节点的参数，右递归在左递归后面，右递归的虚拟指针的 curr 要来自于左递归（因为右接在左后面），当前节点要返回右递归后返回的虚拟节点的 curr。方法 2：寻找当前节点的左子树的最底层的右边的节点（前驱节点），然后将左子数接入到前驱节点的右边，然后将左子树接入到右边。当前节点指针后移，如果当前节点没有左节点，就跳过 continue）
  • LeetCode 105：从前序与中序遍历序列构造二叉树（递归方法：中序数组提供范围下标，前序数组进行递归，递归参数包含（前序数组，中序数组，前当前前序数组处理范围，当前中序数组处理范围））
  • LeetCode 437：路径总和 III（方法 1：双重递归，方法 2，前缀和，记得要回溯撤销，而且要先检查前缀和再放入当前前缀和，以免计算自身，还以记得初始化哈希 map，放入（0，1）。）
  • LeetCode 236：二叉树的最近公共祖先（递归，自底向顶，首先判断是公共祖先的两种情况：1 当前节点左右子树包含 p 或者 q；2 当前节点是 p 或者 q，左右子树其中一个树包含另一个。那如何判断最近这个概念呢：自底向上，当前节点如果是公共祖先，那么一定是最近的。由于只要当前节点本身或者某个树包含 p 或者 q 中的一个，就返回 true，第一个公共祖先可以集齐两个 true，而再上面的节点就永远集齐不了两个 true 了。）
  • LeetCode 124 :二叉树中的最大路径和（递归，自底向上，参考题 543，二叉树的直径。用一个全局遍历实时记录最大值，每次递归返回【当前节点和右子树路径的值，当前节点和左子数路径的值，当前节点的值】中的最大值，最大值等于【max，当前节点的值，当前节点和左右全部形成路径，当前节点和左右其中一个形成路径】。）真人心得：递归的两种思想：自顶向下和自下向顶。 自顶向下，就是先判定当前层的条件，再递归处理子问题，当前层的结果依赖子问题的结果。（比如对称二叉树，就是先检查当前节点是否符合条件，再递归检查子节点）

模板 (层序遍历 - 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;
}

模板 (递归遍历)：

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

boolean check(TreeNode p, TreeNode q) {
    // 1. 先判断当前层的基础条件（终止条件）
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    // 2. 再递归处理子问题（左对右，右对左），当前结果依赖子问题结果
    return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}

自下向顶：先递归处理子问题，再根据子问题的结果计算当前层的结果，子问题的结果决定当前层的结果。（比如二叉树的最大深度，==就是先递归到最深处，再逐层向上汇报深度。==）

public int maxDepth(TreeNode root) {
    // 1. 先递归到最底层（叶子节点的子节点为 null）
    if (root == null) return 0;
    // 2. 子问题结果：左子树深度和右子树深度
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    // 3. 当前层结果：子问题结果 + 1（当前节点）
    return Math.max(leftDepth, rightDepth) + 1;
}

两者本质：就是一个可以不用递归到最深有可能就能得到结果，一个必须递归到最深处。差异仅在于'处理节点是在深入时还是回溯' 就参数数量来说，自下向顶一把只要一个方法参数，就是树节点，其他所有的信息可以通过递归返回的结果来获取。而自顶向下通常需要多个参数。

当递归时，附带了 root 节点以外的信息，比如要注意左递归和右递归还有当前节点返回时这个值的变化。特别是当递归需要返回一个值时，要特别考虑叶子节点的情况是返回 null 还是返回其他什么东西。

9. 图论 (Graph)

[[图论前提知识]]

• 核心思想：DFS/BFS、拓扑排序、Trie 树，并查集。
• 常用集合：邻接表、队列、Trie 节点。
• 时间复杂度：通常是 O(V+E)，V 是顶点数，E 是边数
• 空间复杂度：通常是 O(V+E)
• 比喻：图就像社交网络，找朋友用 BFS(最少中间人)，找族谱用 DFS(完整关系链)
• 我的心法与模板：
  • 心法：图论问题第一步是建图（通常用邻接表 Map<Integer, List<Integer>>，有时也可以直接用 List<List<Integer>>）。然后根据问题选择遍历方式：求最短路径用 BFS，求连通性/所有路径用 DFS。为了防止走回头路，需要一个 visited 集合 (比如三色标记法)。

模板 (DFS 遍历图，课程表问题)：

class Solution {
    // 构建邻接表
    List<List<Integer>> edges;
    // 邻接表
    int[] visited; // 0 未访问，1 正在访问，2 访问结束（已入栈）
    boolean valid = true; // 合法标签，用于递归中标记环存在

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 方法 1：深度优先搜索，三色标记法
        // 构建邻接表
        // 用状态标签标记每一个节点的状态：正在访问，未访问，访问结束
        // 对每个节点进行深度优先递归，如果遇到环--检测到状态属于正在访问
        // 就说明不可能完成课表
        edges = new ArrayList<>(numCourses);
        // 初始化空列表
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>()); // 直接在列表中添加元素
        }
        // 初始化邻接表
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]); // 我们以「出度节点的起点」作为当前节点，邻接表中存放的是「该起点指向的出度节点」。
        }
        visited = new int[numCourses]; // 初始化全部为 0
        // 对每个节点进行递归
        for (int i = 0; i < edges.size() && valid; i++) {
            if (visited[i] == ) dfs(i);
        }
         valid;
    }

       {
         (visited[i] == ) {
            valid = ;
            ;
        }
         (visited[i] == ) ; 
        visited[i] = ;
         ( node : edges.get(i)) {
            dfs(node);
        }
        visited[i] = ;
    }
}

• 经典题目：
  • LeetCode 200: 岛屿数量（方法 1，遍历 + 递归（深度优先遍历），遇到 1 就计数，然后将相邻 1 全部变为 0）
  • LeetCode 207: 课程表（方法 1：深度优先遍历，递归。先构建邻接表，构建三色标记数组（未访问，访问中，已经访问）。遍历邻接表，对每个当前元素深度优先搜索（递归），在递归中检测当前节点是否正在访问（出现环），是否已经访问（不能重复递归），然后对当前节点相邻节点进行递归（邻接表循环），然后设置当前节点已经访问。构建邻接表时有规则：依赖关系是（a<-b），也就是 a 依赖 b，想象图中各个节点的箭头指向，以当前出度（箭头指出）节点为节点，邻接链表就是入度（箭头指向）的对象。所有邻接节点都处理完毕后才能标记以完成。方法 2：广度优先搜索，有时间必看。）
  • LeetCode 133: 克隆图
  • LeetCode 994: 腐烂的橘子 (广度优先遍历，开局先遍历一次，将坏句子坐标放入队列，用 size 分层，用数组记录坐标，最后再检查是否有新鲜橘子。))
  • LeetCode 208: 实现 Trie (前缀树)（类似二叉树，每个节点包含两个指针。这里每个节点包含 26 个指针，用一个数组包含这些指针，数组的下标就代表字符，比如下标 1 就代表'b'-'a'=1，代表字符 b）；

模板 (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; // 未找到路径
}

10. 回溯 (Backtracking)

[[回溯前提知识]]

• 核心思想：递归 + 剪枝（'做选择，撤销选择'）。
• 常用集合：栈（路径）、哈希表/数组（标记已用元素）。
• 口诀记忆：'路径选择终止条件，做选择递归撤选择'
• 时间复杂度：O(n!) 或 O(2^n)，取决于问题
• 空间复杂度：O(n)，递归栈的深度
• 比喻：回溯就像走迷宫，尝试每一条路，遇到死胡同就返回上一个路口继续尝试
• 我的心法与模板：
  • 心法：回溯是"暴力枚举"的优雅版，适用于所有"组合、排列、子集、棋盘"问题。它的框架是固定的，记住"路径、选择列表、结束条件"三要素。
• 经典题目：
  • LeetCode 46: 全排列（思想：固定当前位置，处理下一个位置。传入 first（初始化为 0）作为参数，表示从固定第零个位置开始。遍历选择列表，表示第一个位置可以选择当前路径，然后进入下一层递归，处理 first+1 个位置。然后再回溯撤销。这一题用 Collections.swap（固定当前元素）代替了路径。如果不用交换，可以使用路径 + 标记数组法）
  • LeetCode 78: 子集（简单递归回溯，dfs 传入三个个关键参数，最终返回集合，路径集合（用作副本放入最终返回集合，回溯的对象），当前节点下标（从 0 开始，每次递归加 1），递归停止条件就是下标递归到了最后（需要将当前路径集合的副本放入最终返回集合），递归情况分为两种，当前值放入路径或者不放入路径集合，记得回溯哦！也就是移除最后一个值。时间复杂度：O（n*2^n）,其中 n 是复制时间，空间复杂度 O（n）。处理单个起始，不要 for 循环）
  • LeetCode 17: 电话号码的字母组合（回溯递归，依旧模板，三要素：最终返回答案，路径答案，当前处理位置索引。此题用哈希把数字对应字符串存储起来，由于频繁用到字符串拼接，用到 StringBuilder，常用方法，toString，charAt，append，delete【start，end) 左闭右开，insert(int offset, char c)，StringBuilder insert(int offset, String str)。处理多个起始点，要哦用 for 循环。）
  • LeetCode 22: 括号生成（回溯递归，依旧模板。路径集合包含 2*n 个位置，每个位置有两种选择，左括号或者右括号。还要实时记录左括号和右括号的个数，当左括号或者右括大于一半时减枝，由于递归过程中，只肯出现左括号大于等于右括号的情况，所以右括号个数大于左括号个数时也需要减枝。停止条件中还要加上左括号等于右括号的条件。因为我的减枝条件和条件递归是分开的，减枝可能不会减最后一个节点（如果最后一个简单是错的），所以才需要在停止条件多加条件，一个更好的减枝操作就是用判断语句将递归操作（选择可能性）包裹起来，只有满足某个条件才递归。（这个理解对吗？）这就是剪枝与停止条件的关系 复杂度需要好好分析！卡特兰数量级）
  • LeetCode 79: 单词搜索（深度优先搜索 + 减枝回溯。最终返回集合是一个 bollean 标签，没有路径集合，因为是拿自身做比较。有一个 bollean 矩阵标记每个节点的访问情况。先找到第一个字符，然后深度遍历四周的节点，要求四周有节点且没有被访问过，且符合映射，且不超出边界。这三个条件过多，可以不包裹递归语句，单独是减枝操作。如果能访问到最后就说明存在一一映射的情况。）
  • LeetCode:131 分割回文串（动态规划预处理 + 回溯，每个当前字符有拆开和不拆开两个选择，形成决策树。回溯采取枚举分割点，用循环代替选择，）
  • LeetCode:51 N 皇后（回溯，对每一行皇后出现的列号进行枚举。要用三个标记数组，分别标记列，主对角线（行列差值相同）（-（n-1）n-1）,幅对角线（行列相加相同）（02n-2）。注意减枝要用 continue 而不是 return！）

模板 (通用)：

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;
    }
}

关键词：'决策树'，'暴力，剪枝，选择。 真人心得：回溯题的本质就是暴力枚举，而减枝则降低了不必要的枚举。为什么叫减枝，回溯题就是对当前的某个位置或者状态选择一种可能性（比如有两个可能性），当前状态固定后再对下一个位置或者状态选择一种可能性。如果有两种可能性，那么就可以想象出一颗二叉树了，每个状态有两个选择，产生两个子节点，子节点同样如此。说到底就是所有的决策形成了一颗树，这棵树包含了所有可能的决策，所以叫暴力枚举，而减枝就是把不必要的决策分枝减去。

这种题目的固定做法就是传入必要的三个参数，最终返回的集合，路径集合（用作副本放入最终返回集合），当前处理位置索引。当然还要其他参数，比如标记数组等或其他记录（当然你也可以定义'全局变量'就不需要传参数进入递归了）。

每出现一次选择的操作，如果对路径集合进行了修改，就需要加上一个回溯。如果只有两种情况，加入和不加入，就可以不需要两个回溯，因为没有对路径集合进行修改。由此可见回溯不是树的倒走，return 才是到上层的入口。

回溯什么时候触发呢？：停止条件满足时，减枝条件满足时，直接 return 到上层，上层从一个递归操作中出来，可以想象栈顶栈帧被排除，执行当前栈顶栈帧。当前栈帧从一个选择出来后，如果对路径集合进行了修改，就需要回溯。

停止条件：因为我们一般传入当前处理的位置索引，所以停止条件就是当前处理位置索引递归到了最后，然后将路径集合结果放入最终返回集合。如果你发现最终的返回集合中多了许多杂质（不需要的路径），你可以将停止条件加入更多的限制语句，就比如括号生成题目，就需要加入左括号等于右括号的条件。当然，出现这种情况肯定还要考虑减枝是否正确。

有几个选择就要几次回溯，前提是选择对路径集合进行了修改。 但是，也存在选择多个情况但是只要一次回溯的情况（单词搜索，最终返回是一个 boolean 标签，没有路径集合，只有标记访问标签，标记当前元素是否访问过，访问过就把标签置为 false，几个选择对于这个操作都是相同的，所以可以公用。所以只要一个回溯）

减枝：减枝是 continue 还是 return 要分析清除，如果类似 n 皇后，就是 continue。因为不符合条件的选择可能后面还有符合条件的选择，所以要继续循环下去。

对于是否需要循环，就看时单个起始点还是多个起始点 对于每次都要做出相同的选择，需要显示将选择出来，对于类似于枚举分割点（分割回文串，则是用循环代替了选择，因为每次选择是递减的。）

11. 二分查找 (Binary Search)

• 核心思想：利用数组有序性，通过二分缩小搜索范围。
• 常用集合：数组。
• 时间复杂度：O(log n)
• 空间复杂度：O(1)
• 比喻：就像猜数字游戏，每次都排除一半的可能性
• 我的心法与模板：
  • 心法：只要看到"有序数组"中的"查找"问题，就用二分法。关键在于循环条件 (left <= right) 和边界收缩 (left = mid + 1 或 right = mid - 1)，写对这两个，就成功了 99%。

模板 (左边界搜索)：

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;
}

模板 (标准二分查找)：

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

当数组中有多个等于 target 的元素时，标准模板只会返回其中一个位置（不保证是第一个）。 而左边界模板可以精确找到第一个出现的位置，常用于：

• 查找区间的起点（如 lower_bound）
• 统计元素出现次数（配合右边界模板？）
• 经典题目：
  • LeetCode 153：寻找旋转排序数组中的最小值（找边界，每次 mid 如果大于最右边的值，就二分右边（left=mid+1）否者就相反，最后返回 left。）
  • LeetCode 34: 在排序数组中查找元素的第一个和最后一个位置（用两个二分模板，分别找左边界和右边界，理解左/右边界搜索模板，左边界模板就是即使查找到了一个目标，也继续收缩右边界，继续在左边进行二分，最终返回 left，右边界则相反，最终返回 right。）
  • LeetCode 74: 搜索二维矩阵（方法 1：从右上角看，二叉搜索树。方法 2，先二分第一列，得到 left-1，然后对 left-1 行再次二分，涉及到索引加减，注意检测是否越界。）
  • LeetCode 35: 搜索插入位置 (二分查找模板，如果没有找到就返回 left)；
  • LeetCode 33：搜索旋转排序数组（变种二分查找，同样是获得 mid，然后判断哪一边有序，有三种情况：左边有序，右边有序，左右都有序，其中第三种和第一种合并，就是两种情况，如何判断有序就是根据 mid 值和端点的差值。总而言之就是先判断哪一边有序，然后判断寻找值是否在有序区间，否者 就在另一边。）真人心得：重要规则，如果二分查找没有找到目标值，那么最终 left = right + 1，意味着 left 左侧（[0, left-1]）的所有元素都小于target；left 右侧（[left, n-1]）的所有元素都大于target。 总结：用心理解上面两个模板，一个是找 mid，一个是找边界！找值就返回 mid，找边界就返回 left 或者 right。

处理有重复元素的场景

12. 栈 (Stack)

• 核心思想：利用 LIFO 特性（匹配、解码），或维护单调性（单调栈）。
• 常用集合：栈。
• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 比喻：栈就像盘子堆叠，只能从顶部操作，单调栈就像俄罗斯方块中的砖块排列
• 我的心法与模板：
  • 心法：遇到"括号匹配"、"消除相邻重复项"等具有"最近相关性"的问题，用普通栈。遇到"寻找下一个更大/更小元素"的问题，用单调栈。
• 经典题目：
  • LeetCode 20: 有效的括号 (哈希存储括号对应规则，栈存储左括号和右括号。遍历字符串，如果为空就放入第一个字符，接下来就是每次先对栈顶的元素 peek，判断是否与当前遍历的符号符合规则，符合就取出栈顶，并且不放入当前元素，如果不符合就放入当前元素。最后判断栈是否为空。模拟从中心向两边扩展的过程。中心的括号后进先出。)
  • LeetCode:155 最小栈 (包装栈和一个辅助栈（栈顶用来存储当前最小值），为什么要这要呢，因为如果直接用最小值的标签来存储，put 倒是可以记录，但是对于删除呢？如果删除的是最小值，那么就获取不到接下来的最小值了，而辅助栈就是记录【当前最小值】。也就是记录了每个状态的最小值，当同步时，只要删除栈顶元素。注意，Integer 的比较要用 equals 方法。放入辅助栈元素时，要用<=，这样确保最小的状态不止一个。防止不同步。)
  • LeetCode 394：字符串解码 (递归，找到子问题，理解状态。每一层状态包含数字和当前层字符串两部分，而当前字符串由当前字符串 + 数字*递归下一层的字符串组合而成，遇到【就递归获得子层的字符串，然后与当前层的字符串拼接，要循环数字次数。子问题就是处理数字，处理左括号，处理右括号，处理普通字符，其中字符串拼接一定要在获得递归后立即拼接，也就是要放在左括号逻辑中，而不是右括号逻辑中，因为右括号是子层返回用的，主函数不会遇到右括号，如果放在右括号中拼接，那么最总返回空字符串。而主层的结束条件就是遍历字符串结束，那么如何遍历呢？递归需要有一个共享下标变量，需要 int[] 变量，所以参数有字符串和 int[] 变量。用到工具 StringBuilder, append, toString, CharAt，如何记录数字呢？每层状态有数字字符串和字符串，数字字符串记录数字字符，最终要使用的时候，用 Integer.parseInt(StringBuilder.toString()) 转换为数字。) 注意：每次拼接完后，需要使用 StringBuilder.setLength(0) 清空数字字符串。因为数字只用于与他相邻的那个括号中的递归。)
  • LeetCode 739：每日温度 (单调栈，栈内顺序从低到顶为从小到大，遍历数组，如果为空就放入第一个元素的索引，如果不为空。如果当前元素小于等于顶部元素，就正常放入，如果大于等于顶部索引代表的元素，进入循环。依次将小于当前元素的栈帧全部弹出，并且记录答案，最终将当前元素索引放入栈内。)

模板 (括号匹配)：

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();
}

模板 (单调栈，找下一个更大元素)：

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;
}

13. 堆 (Heap)

[[堆前提知识点]]

• 核心思想：利用优先级特性处理 Top K 问题、中位数问题。
• 常用集合：优先队列 (PriorityQueue)。
• 时间复杂度：插入 O(log n)，取顶 O(1)，建堆 O(n)
• 空间复杂度：O(n)
• 比喻：堆就像排队，但 VIP 客户 (高优先级) 可以插队到前面
• 我的心法与模板：
  • 心法：看到"Top K"或"第 K 大/小"的问题，立刻想堆。求 Top K 大，用小顶堆；求 Top K 小，用大顶堆。这样可以保证堆的大小始终为 K。
• 经典题目：
  • LeetCode 215: 数组中的第 K 个最大元素
  • LeetCode 347: 前 K 个高频元素
  • LeetCode 295: 数据流的中位数

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

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();
        }
    }
}

模板 (求 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);
}

14. 贪心算法 (Greedy)

• 核心思想：局部最优 → 全局最优。
• 常用集合：数组、优先队列。
• 时间复杂度：通常是 O(n) 或 O(nlogn)(如果需要排序)
• 空间复杂度：通常是 O(1) 或 O(n)
• 比喻：就像爬山时总是选择最陡的路径，期望能最快到达山顶
• 我的心法与模板：
  • 心法：贪心没有固定模板，关键是找到贪心策略。思考"为了让整体结果最优，我当前这一步应该怎么选？"。通常需要排序来辅助决策。
  • 模板 (思路模板，以"区间调度"为例)：
    1. 明确贪心选择：每次都选择结束时间最早的那个区间。
    2. 证明其正确性：选择结束最早的区间，可以为后续的区间留出最多的可用时间，从而容纳更多的区间。
• 经典题目：
  • LeetCode 121：买卖股票的最佳时机（分别挑选买入点和买出点太麻烦了，分别维护两个遍历，最小买入点，和当前卖出获得的利润。一边遍历一边更新。）
  • LeetCode 55：跳跃游戏（贪心，每次都跳到能跳到的最远位置，如果当前索引超过了能跳到的最远位置就失败了。）
  • LeetCode 45：（跳跃有戏 2）（维护一个当前节点能跳到的最远距离，和一个窗口 end，遍历每一个节点，当达到窗口边缘时，说明需要再跳一次了，就选择之前窗口中的能跳最远的节点的最远位置作为下一个窗口边界。注意要遍历到 n-2，因为避免遍历到最后 path 会多 1，题目保证一定有路径）。
  • LeetCode 763: 划分字母区间（贪心，预处理每个字母最后出现的位置，维护一个最远距离（每个节点最后一次出现的最大值），一边遍历，一边更新最远距离，当遍历到最远记录后，就记录一次。）真人心得：总是维护极值，比如最小的，最大的，最远的，然后一边遍历一边更新。

编码实现：

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; // 需要删除的区间数
}

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

• 核心思想：状态转移，保存子问题结果。
• 常用集合：数组（一维/二维）。
• 时间复杂度：通常是 O(n^2) 或 O(n*m)
• 空间复杂度：通常是 O(n) 或 O(n*m)
• 比喻：'填表格'，每个格子的值依赖于之前计算过的格子
• 前提可以先搞懂 01 背包，完全背包，硬币问题。
• 我的心法与模板：
  • 心法：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，以"完全平方数"为例)：外层决策遍历，内层状态遍历

import java.util.Arrays;

class Solution {
    public int numSquares(int n) {
        // 1. 初始化 dp 数组：dp[j] 表示'和为 j 的完全平方数的最少数量'
        // 初始值设为 Integer.MAX_VALUE（表示'暂时无法组成'），避免后续取 min 时被干扰
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);

        // base case：和为 0 时，不需要任何平方数，数量为 0
        dp[0] = 0;
        // 2. 决策在外层循环：遍历所有'物品'（即所有 ≤n 的完全平方数）
        // i 从 1 开始，i*i 就是当前要考虑的平方数（物品重量）
        for (int i = 1; i * i <= n; i++) {
            int square = i * i; // 当前平方数（物品重量）
            // 3. 内层循环：遍历'背包容量'（从 square 到 n，确保 j - square ≥0）
            // 完全背包允许物品重复选，所以容量从'物品重量'开始递增（与 0-1 背包的倒序区分）
            for (int j = square; j <= n; j++) {
                // 只有'dp[j - square] 不是无穷大'时，才可能更新 dp[j]（避免 +1 后溢出）
                if (dp[j - square] != Integer.MAX_VALUE) {
                    // 状态转移：选当前平方数（数量 +1），或不选（保持原 dp[j]），取最小值
                    dp[j] = Math.min(dp[j], dp[j - square] + 1);
                }
            }
        }
        // 最终 dp[n] 就是'和为 n 的最少平方数个数'
        return dp[n];
    }
}

• 模板（单词拆分为例），以外层状态遍历，内层决策遍历

public boolean wordBreak(String s, List<String> wordDict) {
    // 1. 初始化基础参数
    int n = s.length(); // n 是字符串 s 的长度（比如 s="leetcode"，n=8）
    boolean[] dp = new boolean[n + 1]; // dp 数组长度是 n+1，因为要存 dp[0] 到 dp[n]
    dp[0] = true; // 关键初始值：空字符串（前 0 个字符）能拆分（不用任何单词），是所有子问题的起点
    Set<String> wordSet = new HashSet<>(wordDict); // 字典转集合，优化查询速度
    // 2. 外层循环：遍历所有'状态'（子问题）——判断 s 的前 i 个字符能否拆分
    for (int i = 1; i <= n; i++) {
        // 3. 内层循环：遍历所有'决策'（字典里的每个单词）——尝试用 word 作为 s 前 i 个字符的最后一段
        for (String word : wordSet) {
            int wordLen = word.length(); // 当前单词的长度（比如 word="leet"，wordLen=4）
            // 4. 验证当前决策是否有效（3 个条件必须同时满足）
            // 条件 1：单词长度不能超过当前子问题的长度（比如 i=3 时，wordLen=4 就不可能匹配前 3 个字符）
            // 条件 2：前（i - wordLen）个字符能拆分（dp[i - wordLen] 是 true）
            // 条件 3：s 的第（i - wordLen）到第（i-1）个字符，正好等于当前单词（比如 i=4，wordLen=4，就看 s[0-3] 是不是"leet"）
            if (wordLen <= i && dp[i - wordLen] && s.substring(i - wordLen, i).equals(word)) {
                dp[i] = true; // 只要有一个单词满足条件，当前子问题就有解（dp[i] 设为 true）
                break; // 找到有效决策就不用再试其他单词了，直接下一个子问题（精准止损，提高效率）
            }
        }
    }
    return dp[n]; // 最终答案：s 的前 n 个字符（整个字符串）能否拆分
}

• 经典题目：
  • LeetCode 70: 爬楼梯（定义 dp【i】为爬到 i 层的方法数，找到状态转移方程：dp【i】=dp【i-1】+dp【i-2】，初始化 dp【0】=dp【1】=0。注意要创建的 dp 数组的内存大小为 n+1，遍历时要遍历到 n。）
  • LeetCode 118：杨辉三角（遍历创建二维数组，如果是边缘，就初始化为 1，否者就用动态规划，只需遍历一次，定义 dp[i][j] 为 nums[i][j] 的值，dp[i][j]=dp[i-1][j-1]+dp[i-1][j]//此公式只用于不是边界的情况，边界就为 1。提醒：java 的 List 要用 get（index）获取值。）
  • LeetCode 198：打家劫舍（定义 dp[i] 为偷到 i 家时的最大金额，他有两种情况，偷或者不偷偷就就用当前余额加上之前的余额，不偷就继承之前的余额。dp[i]=max(dp[i-2]+nums[i],dp[i-1]),每个当前问题依赖两个子问题，选择更大的子问题初始化这个当前问题，初始化 dp[0]=0,dp[1]=0,将第一家的下标设为 2。注意下标偏差 nums[i] 应该是 nums[i-2]。）
  • LeetCode：279：完全平方数（拆分子问题，每个 n=x+y，其中 x 是完全数，y 不一定是，就把 y 继续细分，获得子问题，要当何为 n 的完全平方数个数最少，就要子问题的最少。设 dp[i]='给你一个整数 i，返回和为 i 的完全平方数的最少数量'。那么每一个 dp[i]=min(枚举选择每个完全平方数 jj<i 的选择后另一个子问题的结果 +1)，也就是 min(dp[i-jj]+1) j*j<i。注意遍历时初始值，时间复杂度为 o(n 根号 n)。参考模板。采用决策 + 状态思维！）
  • LeetCode 322: 零钱兑换（完全背包，硬币可重复选问题，模板，注意整体初始化和理解状态转移方程，还要注意循环初始值）。
  • LeetCpde 139：单词拆分（外层遍历状态，内层遍历决策。设 dp[i] 为当前问题的子问题，也就是 0-i 的字符串是否可以有字典元素组成。不采取外层决策内层状态的模糊初始化 dp 细化的方案。而是初始化 dp【0】，遍历每个状态，对每个状态采取最好的决策。最好的决策：当前字符串最后某个子字符串在字典中存在，dp【i-子字符串】也为 true。则 dp【i】=true。用到的工具 substring（左闭右开），注意下标偏差，因为 dp[i],i 从 1 开始，却代表字符串 s 从 0 开始。所有取子字符串为（j，i），而不是 i+1。）
  • LeetCode300：最长递增子序列 (动态规划：考虑是决策在外还是状态在外，这一题应该是状态在外，设 dp[i] 是 nums[i] 结尾的最长递增子序列长度。但由于 dp[i-当前决策元素] 不好表示，因为这一题不像硬币问题，决策元素直接有某个权重在 nums 中。这一题的 nums[i] 和 i 代表的价值也就是权重是分开的，所以要状态在外层，决策在里面。考虑初始化，所有 dp[i] 为 1，这样就不需要 dp[0] 的额外初始化了。dp 大小直接为 n。外层遍历 dp[i] 代表的 i，内层决策选什么，遍历 j<i，选择合格的 dp[j]，作为当前 i 的前一个子问题，于是有了 dp[i]=Math.max(dp[j]+1,dp[i])，要注意的是这一题不是返回 dp[n]，而是要找出最大的，所有标记一个标签即可。)
  • LeetCode 152：乘积最大子数组（划分子问题：如果要算当前 dp[i] 的最大非空连续子数组，那么就要先算出之前的 dp[i-1] 的，由于决定状态 dp[i] 的直接来源于决策元素 nums[i],而不像之前最长子序列–dp[i] 间接来源于决策元素–因为是将决策元素本身算为个数，而不是直接参与计算。所以只要单层循环。定义 dp[i] 为 nums[i] 结尾的最长…子问题。所以 dp[i]=max[dp[i],dp[i-1]*nums[i]],但因为存在负负得正的情况，要维持一个最小数组 dp_min[i]=min(dp[i],dp[i-1]*num[i],dp_max[i-1]*nums[i])，那么使得 dp[i]=max(dp[i],dp[i-1]*num[i],dp_min[i-1]*nums[i])。也就是需要两个 dp。）
  • LeetCode 416:：分割等和子集（01 背包问题，求是否存在背包容量为 sum/2 的 dp[i]。决策（j）+ 状态（i），设 dp[i] 为以 i 为背包容量时的最大和，i<=x。状态转移方程 dp[i]=max(dp[i-nums[j]]+nums[j],dp[i])。）
  • LeetCode 32: 最长有效括号（用栈解决，栈放索引。先初始化 -1 放入栈。遍历字符串的每一个字符，如果当前字符是'（'，就正常放入栈，如果当前字符是'）'，且刚好与栈顶元素匹配，就记录当前索引 - 栈顶索引。否者就更新）为栈顶。因为 -1 是模拟）的，出现）不匹配的情况，说明栈内无（，也就是处理初始化的 -1 以外，就是空。）

模板 (二维 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];
}

//以下是二维动态规划，主要模拟循环 i 和 j，求 dp【i】【j】的子问题，单维的是有决策元素，通过最后一个决策元素，挑选更好的子问题。 二维则可以想象是表格，差不多，主要搞清楚 i 和 j 代表得什么，当前状态的子状态和 i 和 j 有什么关系，来自于 i 和 j 代表的什么前置状态。关键是思考从一个状态到状态一个需要做什么操作，这些操作分别执行就是决策，选择最优决策，也就是最好的操作。思考从求什么状态变成求什么状态。

• LeetCode 62：不同路径（二维动态规划，设 dp[i][j] 为到达坐标为 [i][j] 时的路径。状态转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1]。要考虑好边界条件，包括初始化的问题。也就是第一行和第一列都是要初始化为 1.）
• LeetCode 64：最小路径和（二维动态规划，设 dp[i][j] 为到达 grid[i][j] 的最小路径和。先初始化 dp[0][0]，再初始化第一行和第一列。状态转移方程也非常简单。）
• LeetCode 5：最长回文子串（方法 1：二维动态规划，定义 dpi，j，为以 s 的两个左右指针的字串是否是回文字串。回文字串有两种形式，xx 和 xyx，后者产生了子问题。初始化 dp[i][i] 为 true。初始化所有 dp[i][i] 为 true。状态转移方程：如果 j 只比 i 大 1，dp[i][j]=(s[i]==s[j])。否者：dp[i][j]=(s[i]==s[j]&&dp[i+1][j-1]);外层遍历长度，内层遍历起始点。注意遍历的范围。方法 2，中心扩散法，每个元素都有可能是中心，中心扩散法，参照 xx 的形式和 xyx 的形式进行扩散即可。对于每个中心。有情况 1：左右都不和中心元素相同，判断左右是否相同，相同就继续以 xyx 的形式扩展。情况 2：左右有一边和中心相同，以 xx 的形式扩展。情况 3：左右都和中心相同，以 xyx 的情况扩展。）
• 最长公共子序列 1143：（二维动态规划，思考切入点，如果两个字符串有公共子序列，且公共子序列最后字符是 x，那么这两个字符串一定分别有子字符串 ax 和 bx 的形式。找到子问题划分：设 dp【i】【j】代表着字符串 1 和字符串 2 的前 i 和 j 的子字符串的最长公共子序列的长度，那么有情况 1：当有两个子字符串 ax 和 bx 的形式，那么当前 dp【i】【j】=dp【i-1】【j-1】. 情况 2：如果两个子字符串末尾字符不相同，那么当前 dp 一定来自于 max（dp【i-1】【j】，dp【i】【j-1】。思考状态来自于什么前置状态（需要进行什么操作，字串 1 扩展一个还是字串 2 扩展一个。从求什么状态变成求什么状态。）。需要初始化第一行和第一列！）
• LeetCode 72：编辑距离（二维动态规划，设 dp[i][j] 为字符串 1 和字符串前 i 和 j 的子字符串的最少转换操作数（字符串 1 的前 i 个字符变成字符串 2 的前 j 个字符），情况 1：字符串 a 中有 x 结尾的子字符串，那么 dp[i][j]=dp[i-1][j-1]。否者有三种情况（选择最好的决策）：[] [] [x] //[] [y]。1.删除，dp[i][j]=dp[i-1][j]+1 从求 dp[i][j] 到求 dp[i-1][j];。2.添加，dp[i][j]=dp[i][j-1]+1 从求 dp[i][j] 到 dp[i][j-1]。3 更改，dp[i][j]=dp[i-1][j-1]+1 从求 dp[i][j] 到求 dp[i-1][j-1]。创建 dp 大小 n+1，初始化第一行第一列。注意当初始化为 n+1 时，注意下标的偏差。）真人心得：动态规划是子问题相互推导依赖的过程，也就是局部推导出全部，和贪心有些类似。动态规划的'局部最优'，不是随便的'局部'。它有严格定义，就是问题的全局最优解，必然包含了某个子问题的局部最优解。 比如爬楼梯问题：要到第 10 成，假设全局最优为最小步数，那么要求到达第 9 层和第 8 层也是最小步数，这些局部最优解形成了全局最优解。 打家劫舍问题：偷前五家的最大金额（全局最优），要么偷第五家，要么不偷第五家，（依赖偷前 3 家或者偷前 4 家的局部最优）。 总结：问题本身具备'最优子结构'和'无后效性'。

1. 最优子结构：全局最优解里，一定藏着某个子问题的局部最优解（比如到 10 层的最优，藏着到 9 层或 8 层的最优）；
2. 无后效性：局部最优的'来源'不影响后续决策，局部最优解一旦算出来，就固定不变，后续用它的时候不用管它的'出身'，只管用结果。==也就是说状态转移方程需要包含所有信息。 深入理解：动态规划的本质是**'记忆化搜索'，即把递归过程中重复计算的子问题结果存起来，避免重复计算。 假设你面前有 5 棵果树（对应 5 间房），每棵树上有苹果（对应房里的钱），规则是'不能摘相邻果树的苹果'**（对应不能偷相邻房）。 '决策树'就是你'从第一棵树到第五棵树，所有可能的摘苹果路径' 上面就是用递归解决，但是递归后路径太多了，可以采取减枝，如何减枝呢？就是记忆化搜索，把重复路径存储。 比如从树 1 到达树 3，有三条路径，1 摘，2 不摘（路径 1）；1 不摘，2 摘（路径 2）；1 不摘，2 不摘（路径 3）。此时在梳 3 选择，对于路径 1 和路径 3，这两个路径可以剪掉一条。

可以看出一个节点在做决策时，可能依赖保留了两种可能情况，那么在动态规划中，一个 dp[i] 只能存储一个确定的情况？如何解决呢，初始化，dp[0] 或者 dp[i]，也就是添加两个缓存空间，那么对于 dp[2]，做决策开始，它可以选择，由于 dp[i]=max(dp[i-2]+dp[i],dp[i-1])，也就是对于第一个节点 dp[2] 做决策，它的两种情况分别来自于我们初始化的 dp[0] 和 dp[1]. dp[3] 做决策的两种情况来自于 dp[1] 和 dp[2]，也就是一个节点分别当作了两种情况，下一个节点选择的情况，下下个节点不选择的情况。 可以看出由于缓冲后，模拟了树的分支。

由上面的分析，我们对动态规划有了建模思想，就是决策树 + 减枝，模拟树种的分支，就用缓冲空间来实现，也就是初始化 dp，一个节点相当于好几个分支，是下一个决策的前提分支（没选择），又是下下个决策的前提分支（选择）。 相当于'用线性缓存链，替代了树的网状分支'，既没漏掉任何合法选择，又极大提升了效率。 递归回溯 + 记忆化：这个递归其实是回溯。他会递归到最深处，计算最后面的 dp[i]，然后存储起来。相当于存储了这个叶子或者枝条，供其他相同的使用。

上面是属于本质疏通，可以不看，因为有人可能会奇怪为什么线性的数组能完成决策树的功能。如果搞不懂就可能陷入死循环，或者说无法理解动态规划的本质。

接下来是做题疏通，就是怎么做题，以零钱兑换为列： 1.可重复选择，相当于完全背包问题。 划分子问题：要解决这个问题，先思考：'凑 n 的最少硬币数'和'更小金额的硬币数'有什么关系？ 我们的核心目标是：凑出总金额n的最少硬币个数。 要解决这个问题，先思考：'凑n的最少硬币数'和'更小金额的硬币数'有什么关系？ 比如凑11（目标n=11），最后一步选的硬币只能是1、2或5（假设硬币是[1,2,5]）：

• 若最后一步选1，则之前需要凑出11-1=10，此时'凑 11 的个数'='凑 10 的个数 + 1'；
• 若最后一步选2，则之前需要凑出11-2=9，此时'凑 11 的个数'='凑 9 的个数 + 1'；
• 若最后一步选5，则之前需要凑出11-5=6，此时'凑 11 的个数'='凑 6 的个数 + 1'；
• 凑 11 的最少个数，就是这三种情况的最小值。

//遍历每个 i，有选择和不选两个选择，可重复选
//假设 dp[i] 为目标为 i 时的最少硬币个数，也就是子问题。i 为目标钱的金额
//若选择 dp[i]=dp[i-当前硬币的金额]+1，不选择 dp[i]=dp[i]
//dp[i]=min(dp[i-coin]+1,dp[i]);
//初始化 dp[0]=0;
//其他为 amount+1，表示不可达
//具体代码就是遍历硬币 coin，在这个遍历里面处理面额 coin 到 n，因为如果目标小于 coin，就凑不出来
//就是双重遍历，实时更新 dp。在遍历选与不选里面遍历目标，每完成一次外层（遍历选与不选）都会优化一次 dp 数组。
//题外话，假设不可重复选，依旧是 dp[i] = min(dp[i], dp[i - coin] + 1)，仅仅需要倒叙遍历目标金额即可，确保不会重复选。如何理解二重循环呢：原本我们是用二维动态规划，优化成了一维动态规划。这里的双重循环就是模拟二维。二维 DP 的'前 m 枚硬币'维度，被一维 DP 的'外层循环遍历 m 枚硬币'替代；二维 DP 的'金额 j'维度，被一维 DP 的'内层循环遍历 j'直接保留；

理解 2：在遍历最外层的的硬币时，每一个当前硬币纳入可选，就优化一次 dp 数组，因为我们的动态数组初始化了的。 出现一个硬币，就提供了一种选择，讲动态数组优化，可以想象最开始的动态数组是模糊的，每出现一种硬币的选择，就可以清晰一些。

那为什么打家劫舍需要一层循环，而硬币问题需要两层循环呢？ 因为关键是状态和决策，打家劫舍的状态是 dp[i]，偷到 i 房屋的最大金额；决策是每个状态 i 决策只有两个，也来自于当前集合数组，也就是房屋金额数组。 而硬币问题的状态是 dp[i]，抽出金额 i 需要的最少硬币数。 决策是选什么硬币来凑得。 前者问题的状态和决策来自于一个数组，的状态依赖一个外部集合数组。 后者问题的状态来自于一个数组，决策来自于一个外部集合数组。 然而上面的总结不够全面，应该这么说，判断是否需要两层遍历，就通过 dp[i] 当前子问题依赖的是前面固定个数的子问题，还是，依赖前面所有的子问题，从 dp[0i]，比如打家劫舍，需要一层遍历，是因为它的 dp[i] 只依赖固定的 dp[i-1] 和 dp[i-2]，而硬币问题的 dp[i] 依赖于前面所有的子问题，也就是 dp[0i]，因为每个子问题都可能是最优解。 以 dp[j] = min( dp[j - coins[i]] + 1 ,dp[i]) 为例，这是需要两层遍历的，因为 coins[i] 就是决策，需要遍历每个决策元素。 而打家劫舍的状态转移方程： dp[i] = max( dp[i - 2] + nums[i], dp[i - 1])，这里的 nums[i] 是状态 i 的值，并不是决策元素，决策元素是偷或者不偷，而偷或者不偷只有两个选择，不需要遍历决策元素。

对于一维的动态规划，模板非常简单。 对于二维动态规划，有这样的模板，外层遍历决策数组，内层遍历状态数组，内层遍历的内容就是状态转移方程，也就是某种决策的最佳选择。前提是要将 dp 数组初始化好，要整体初始，不是只初始化部分。这个模板的思想就是：每遍历一个决策数组的元素，状态转移方程做出了最佳决策后，就优化一次 dp 数组（从模糊到清晰）。 而对于同一个物体是否可重复选只需调整内层状态遍历的方向 即可。

//选择或者不选择，选择则 dp[i]=dp[i-coin]+1，不选择则 dp[i]=dp[i] 一下是对决策和状态的深度刨析（理解就无敌了！）： dp[i] 是上一论遍历的结果，而 dp[i-coin]+1，是这一轮遍历的结果，选择表示含义 - 由于外层遍历循环比上一轮多得到了一个决策元素，可以优化这一轮的结果。而不选择就表示这一轮多出来的决策元素不影响此次优化

决策 + 状态和状态 + 决策一般都可以互相转换。 如果是状态 + 决策，也就是外层遍历每个状态 dp[i]，内层遍历决策集合或者数组，选择外层状态，内层决策，不用模糊初始化 dp 数组，再一轮一轮的做选择还是不选择的优化；而是对当前状态，遍历所有决策，直接选出最好的决策，进行从前往后的递推。 状态转移公式就不是看选择还是不选择了，而是看这样的思维推导：在最后选择哪一个决策元素后，dp[i-决策元素] 的结果是最优的。虽然思维不同，但通常状态转移公式是一样的，但表现形式不一样，比如 dp[i]=dp[i]+dp[i-jj] 可能会变成这样表现：先遍历每一个 dp[i-jj]，选择最小的作为 dp[i]； 当然还有一个不同之处，就是循环，状态 + 决策的循环是前推导后的，也就是说内层遍历的结束可能只到当前状态，而决策 + 状态的内层遍历就是遍历完整的，因为它是一轮轮优化模糊初始化的 dp 数组。

总结两种思想：选择还是不选择，然后一轮轮优化模糊初始化的 dp 数组；用当前状态遍历每个决策元素，对于每个决策元素都有 dp[i-决策元素]，选择最好的那个。

那这两个思想如何选择呢？ 以 LeetCode 300:最长递增子序列为例：

//划分子问题，s=x+y，x 是枚举的某个最后一个选择，y 是子问题
//设 dp[i] 是 nums[i] 结尾的最长递增子序列长度。
//思想 1：采用外层决策 + 内层状态的思想，因为就是当前选与不选的问题。
//dp[i]=max/min(dp[i-当前决策元素]+1,dp[i])
//先模糊初始化整体 dp 数组，一轮轮根据状态方程优化 dp 数组。
//如果采用外层状态 + 内层决策的思想，就是选择哪一个决策最好的问题。
//思想 2：先初始化 dp 数组，然后每次循环梅每个决策的可能，选择当前最好的决策，然后往后递推。
//但由于 dp[i-当前决策元素] 不好表示，因为这一题不像硬币问题，决策元素直接有某个权重加入了计算。
//所以选用思想 2：当前 dp[i] 如果选定了某个最后的决策元素 j，那么对应的 dp[j] 要是最大.

17. 技巧 (Tricks)

• 核心思想：位运算、摩尔投票、双指针、数学规律。
• 常用集合：数组、位运算。
• 时间复杂度：通常是 O(n)
• 空间复杂度：通常是 O(1)
• 我的心法与模板：
  • 心法：这些是"神来之笔"，需要专门记忆。位运算的异或 (XOR) 特别好用：a ^ a = 0, a ^ 0 = a。非常适合解决"只出现一次/两次"的问题。
• 经典题目：
  • LeetCode 136: 只出现一次的数字（位运算，初始化为 0.(123)2=(13)）;
  • LeetCode 169: 多数元素 (维护一个候选值和计数器，遇到相同元素计数器 +1，否则 -1，计数器为 0 时更新候选值)。)
  • LeetCode 75: 颜色分类 (双指针，采用快速排序的分类的思想。左右指针 left 和 right 维护两个左右窗口，遍历数组每一个元素 nums【i】,选择放入哪一个窗口。重要点：当放入左窗口和不放入任何窗口时，都要 i++,但是放入右创建不需要 i++,因为左窗口扩大了，如果 i 不变大，那么可能会被左窗口包裹，无限循环。循环停止条件 i<=right，可以等于 right 是因为 right 是窗口的右边界，是开口的，也就是右窗口不包含 right 位置的元素。)
  • LeetCode：31: 下一个排列 (从后向前找第一个降序的数 i，然后再从后向前找第一个比 i 大的数 j，交换 i 和 j，然后反转 i 后面的所有数。如果找不到第一降序的，就说明直接反转即可。小提醒：注意循环要 break，注意数组元素和索引不用弄混。)
  • LeetCode 11: 287: 寻找重复数 (有点原地哈希的意思，就是通过值指向的索引连接下一个节点，最终环的入口就是重复元素，因为会有两个元素指向它，形成了环。做法也就是先用快慢指针继续遍历，当重复时停止。接下来从相遇点和开始点用两个速度一样的指针进行遍历，相遇就是入口)

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

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;
}

模板 (位运算，找只出现一次的数字)：

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

18. 字符串算法 (String)

• 核心思想：哈希表、滑动窗口、字符串匹配算法
• 常用集合：哈希表、Trie 树
• 时间复杂度：KMP O(m+n)，暴力匹配 O(m*n)
• 空间复杂度：通常是 O(n) 或 O(字符集大小)
• 比喻：就像在书中查找特定句子，可以一个字一个字对比，也可以用巧妙的方法快速跳过
• 我的心法与模板：
  • 心法：字符串处理问题通常涉及模式匹配、统计或转换。对于匹配问题，如果是简单匹配用 indexOf()，复杂匹配考虑 KMP 算法；对于统计，用哈希表；对于查找前缀，用 Trie 树。
• 经典题目：
  • LeetCode 208: 实现 Trie (前缀树)
  • LeetCode 28: 实现 strStr()
  • LeetCode 14: 最长公共前缀

模板 (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;
}

模板 (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'] == ) {
                 ;
            }
            node = node.children[c - ];
        }
         node;
    }

      {
        TrieNode[] children =  [];
           ;
    }
}

19. 并查集 (Union Find)

• 核心思想：高效处理元素分组和合并
• 常用集合：数组
• 时间复杂度：几乎 O(1)（路径压缩 + 按秩合并）
• 空间复杂度：O(n)
• 比喻：就像朋友圈，可以快速判断两个人是否属于同一个圈子，或将两个圈子合并
• 我的心法与模板：
  • 心法：并查集适用于动态连通性问题。当需要频繁判断两个元素是否连通，或者合并两个连通分量时，并查集可以做到近乎常数时间复杂度。
• 经典题目：
  • LeetCode 200: 岛屿数量 (并查集解法)
  • LeetCode 547: 省份数量
  • LeetCode 684: 冗余连接

模板：

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;
            }  {
                parent[rootY] = rootX;
                rank[rootX]++; 
            }
            count--; 
        }
    }

    
       {
         find(x) == find(y);
    }

    
       {
         count;
    }
}

学习路线图

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

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

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