LeetCode 热题 100 快速通关指南（附模板） | 极客日志

Javajava算法

LeetCode 热题 100 快速通关指南（附模板）

LeetCode 热题 100 算法通关指南涵盖哈希、双指针、滑动窗口、动态规划等核心模块。提供 Java 代码模板及解题心法，通过分类总结经典题目与技巧，帮助开发者系统掌握数据结构与算法，提升刷题效率。

并发大师发布于 2026/3/21更新于 2026/4/232 浏览

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

前提要点：此文本提供了基本完善的模块，可用于刷题记录，总结教训等。建议复制下来粘贴进自己的 md 笔记软件，每个章节包含模板，题目记录和真人心得部分。可以自行个性化更改，每个人都有自己的节奏，经验，教训，总结，方法。系统的记录可以进行系统化。

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];
        
         (map.containsKey(complement)) {
            
            
              []{map.get(complement), i};
        }
        
        map.put(nums[i], i);
    }
    
      [];
}

更多推荐文章

查看全部

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) {
        // 左右指针需要用 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 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;
}

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

核心思想：贪心、排序、双指针、数学推导，动态规划。
常用集合：数组（原地修改）。
时间复杂度：取决于具体算法，通常为 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;
}

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

核心思想：指针操作、递归、哈希表辅助。
常用集合：指针、哈希表。
口诀记忆：'虚拟头节点是神器，快慢指针找环中'
时间复杂度：通常是 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：排序链表（使用归并排序，分治思想。每次将链表拆分成两个，可以用快慢指针获取中点，然后第二条链表的头节点就是终点的下一个。合并就是简单的对比合并。此题的前提是先弄清除归并数组排序（建议观看相关视频课程）
- 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
}

核心思想：递归、迭代（栈/队列）、分治、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，当前节点的值，当前节点和左右全部形成路径，当前节点和左右其中一个形成路径】。）真人心得：递归的两种思想：自顶向下和自下向顶。自顶向下，就是先判定当前层的条件，再递归处理子问题，当前层的结果依赖子问题的结果。（比如对称二叉树，就是先检查当前节点是否符合条件，再递归检查子节点）

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

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] == 0) dfs(i);
        }
        return valid;
    }

    private void dfs(int i) {
        if (visited[i] == 1) {
            valid = false;
            return;
        }
        if (visited[i] == 2) return; // 必须加上，防止重复递归
        visited[i] = 1;
        for (int node : edges.get(i)) {
            dfs(node);
        }
        visited[i] = 2;
    }
}

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

核心思想：递归 + 剪枝（'做选择，撤销选择'）。
常用集合：栈（路径）、哈希表/数组（标记已用元素）。
口诀记忆：'路径选择终止条件，做选择递归撤选择'
时间复杂度：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;
    }
}

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

核心思想：利用 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;
}

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

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

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

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 以外，就是空。）

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 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，这两个路径可以剪掉一条。 ! ![Pasted image 20250902205841.png] 可以看出一个节点在做决策时，可能依赖保留了两种可能情况，那么在动态规划中，一个 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】，也就是一个节点分别当作了两种情况，下一个节点选择的情况，下下个节点不选择的情况。可以看出由于缓冲后，模拟了树的分支。

//遍历每个 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'直接保留；

//划分子问题，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] 要是最大.

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

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

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

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

关键词	立刻想到	模板
'两数之和'、'配对'	哈希表	`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`

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. & 16. 动态规划 (DP)

17. 技巧 (Tricks)

18. 字符串算法 (String)

19. 并查集 (Union Find)

学习路线图

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

第二阶段：链表与树

第三阶段：进阶数据结构

第四阶段：进阶算法

第五阶段：高级算法

快速学习加速技巧

口诀记忆总结

30 秒快速识别表

更多推荐文章

相关免费在线工具

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. & 16. 动态规划 (DP)

17. 技巧 (Tricks)

18. 字符串算法 (String)

19. 并查集 (Union Find)

学习路线图

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

第二阶段：链表与树

第三阶段：进阶数据结构

第四阶段：进阶算法

第五阶段：高级算法

快速学习加速技巧

口诀记忆总结

30 秒快速识别表

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具