《labuladong 的算法小抄》学习笔记：刷题先学框架，算法本质是穷举

方糖猫 方糖猫
- 约 33 分钟读完 - 全文 13171 字

《labuladong 的算法小抄》学习笔记：刷题先学框架，算法本质是穷举

目标读者：正在刷 LeetCode（或准备刷）、刷过几十题但换个马甲就认不出来的程序员；面试季突击者尤佳。
参考书籍：labuladong（付东来）《labuladong 的算法小抄》（电子工业出版社，2020），内容源自其开源项目（GitHub 上的算法教程仓库）。
阅读目标：提炼全书的"框架思维"——不背题，只背框架；认清每类题目的本质穷举结构，剩下的都是填空。本文在笔记之外补充了每个框架的典型原题、解题思路和关键代码（Java），代码均按书里的框架写法整理。

0. 写在前面：一本"反算法书"的算法书

这本书的出身就不同寻常：它不是教授写的教科书，而是一个刷过几百道 LeetCode 的工程师，把自己"打怪升级"的套路整理成的实战手册。先在网上开源（当年以 repo 名的粗口出圈），火了之后才出的书。

所以它跟《图解算法》正好互补（本站的《图解算法》读书笔记可以对照着看）：

  • 《图解算法》是科普：让你知道世界上有哪些工具，各自干什么；
  • 《算法小抄》是教练手册：假设你已经知道工具，教你"看到一道新题，30 秒内判断它属于哪个框架，然后往里填"。

全书的核心主张，用作者自己的话说：算法的本质就是穷举，所有的算法技巧都是"如何聪明地穷举"。动态规划靠备忘录消除重复穷举，回溯靠剪枝砍掉无效穷举，双指针靠单调性跳过不可能的穷举。

这句话是理解全书的钥匙。下面的每一节，都是在回答同一个问题：“这一类题，穷举的结构长什么样？”

1. 全书总纲：数据结构只有两种，算法就是遍历

开篇第一章是全书的"世界观"，作者把纷繁复杂的数据结构和算法压成两句话。

第一句：数据结构只有两种底层存储方式——数组（顺序存储）和链表（链式存储）。

散列表、栈、队列、堆、树、图，全是这两者的排列组合：散列表是"数组 + 散列函数"（拉链法还叠加链表），队列/栈用数组或链表都能实现，图用邻接表就是"数组套链表"，二叉树是链表的升级（一个节点带两个指针）。所以数据结构没有新东西，只有新组合。

第二句：数据结构的基本操作只有"遍历 + 访问"，而遍历只有两种形式——线性的（for/while 迭代）和非线性的（递归）。

flowchart TD
    A["所有算法题"] --> B["本质是穷举"]
    B --> C["线性结构<br/>用迭代遍历<br/>双指针 滑动窗口 前缀和"]
    B --> D["非线性结构<br/>用递归遍历<br/>DFS 回溯 动态规划"]
    B --> E["图与树<br/>层序遍历<br/>BFS"]

由此推出全书最重要的暗线：一切递归皆树遍历。你写的任何递归函数，其执行过程都等价于在遍历一棵隐形的树——调用关系构成树，函数体里的代码位置对应树的前序/中序/后序位置。动态规划、回溯、分治，全是这棵"递归树"上的不同走法。

这个视角的威力在于：它把"动态规划好难"这种情绪问题，降级成"这棵树怎么遍历"的技术问题。

2. 动态规划：带备忘录的穷举

全书篇幅最重的部分，作者也自认是招牌。动态规划在书里被还原成一句话：求最值的问题，穷举所有可行解找最优，发现有重叠子问题，就加备忘录或 DP 表消除重复。

三要素（判断一个问题能不能用 DP）：

  1. 重叠子问题：暴力递归会反复计算同一个子问题。这是"值得优化"的信号。
  2. 最优子结构：大问题的最优解能由子问题的最优解推出。这是"能够分解"的依据。
  3. 状态转移方程：子问题之间的数学关系，是 DP 的"最难也唯一难"的部分。

书里给的标准解题流程，值得背下来：

flowchart LR
    A["明确 状态<br/>原问题和子问题中<br/>会变化的量"] --> B["定义 dp 数组或函数<br/>它的返回值是什么含义"]
    B --> C["明确 选择<br/>每个状态有哪些岔路"]
    C --> D["明确 base case<br/>最小的子问题直接给答案"]

2.1 入门例题：斐波那契——重叠子问题长什么样

暴力递归的 fib(n) = fib(n-1) + fib(n-2) 人人会写，但它的执行过程是一棵二叉树，同一棵子树被反复展开：

flowchart TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3)<br/>重复计算"]
    B --> E["fib(2)"]
    C --> F["fib(2)<br/>重复计算"]
    C --> G["fib(1)"]
    D -.->|"本子树 C 已经算过"| C

节点数是指数级的，时间复杂度 O(2^n)。优化思路朴素得惊人：算过的子问题存起来，下次直接查表——这就是备忘录：

int[] memo; // memo[n] 缓存 fib(n)，0 表示未计算

int fib(int n) {
    if (n <= 1) return n;          // base case
    if (memo[n] != 0) return memo[n]; // 查表，砍掉整棵重复子树
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

加了一个数组，复杂度从 O(2^n) 降到 O(n)。动态规划的一切技巧，都是这个"备忘录"思想的变体——备忘录是自顶向下查表，DP 表是自底向上填表，两者是同一棵递归树的两条遍历顺序。

术语澄清：什么是 DP 表？ “DP” 是 Dynamic Programming（动态规划）的缩写，DP 表就是存子问题答案的那个数组——每个格子对应一个子问题，格子的值就是它的答案。它和备忘录（memo）存的内容完全一样，区别只在计算顺序：

  • 备忘录：自顶向下写递归时用的缓存。递归过程中算出一个子问题就顺手存进去，下次遇到直接查——“用到才算”；
  • DP 表：自底向上迭代时填的数组。从最小的 base case 出发，按依赖顺序把每个格子提前算好——“按顺序全算好”。

所以下文凡说"dp 数组"“dp 表”，指的都是这张存答案的表；定义 dp 含义，就是回答"这张表的每个格子代表哪个子问题的答案"——这是 DP 四步流程里最关键的一步。

2.2 招牌例题：凑零钱（LeetCode 322）

给你面额数组 coins 和总金额 amount，求凑出该金额的最少硬币数，凑不出返回 -1。

按四步走：

  • 状态：目标金额 n（唯一会变的量）；
  • dp 定义：dp(n) 是凑出金额 n 需要的最少硬币数；
  • 选择：遍历每种面额，选一枚，问题规模缩小为 n - coin；
  • base case：dp(0) = 0，n < 0 返回 -1 表示凑不出。

先写带备忘录的自顶向下版本（好写、不易错）：

int[] memo;

int coinChange(int[] coins, int amount) {
    memo = new int[amount + 1];
    Arrays.fill(memo, -2); // -2 表示"未计算"
    return dp(coins, amount);
}

int dp(int[] coins, int n) {
    if (n == 0) return 0;              // base case
    if (n < 0) return -1;              // 凑不出
    if (memo[n] != -2) return memo[n]; // 查备忘录，消除重复穷举

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {           // 选择：每种面额的硬币
        int sub = dp(coins, n - coin);
        if (sub == -1) continue;
        res = Math.min(res, sub + 1);
    }
    memo[n] = (res == Integer.MAX_VALUE) ? -1 : res;
    return memo[n];
}

再改自底向上的 DP 表（省递归栈空间）：

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // 初始化为"不可能的大值"充当正无穷
    dp[0] = 0;                   // base case
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i - coin < 0) continue;
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

两个版本一一对照：递归的 base case 就是 dp[0] 的初值，递归的"选择"循环就是填表的内层循环，备忘录就是 dp 数组本身。

2.3 系列一：0-1 背包（状态升维）

有 n 件物品，第 i 件重 wt[i]、值 val[i]，背包容量 W，每件只能选一次，求能装的最大价值。

关键在于：这里会变化的量有两个——“还剩哪些物品可选"和"背包还剩多少容量”，所以状态是二维的，dp 表自然是二维的：

  • dp[i][w]：只考虑前 i 件物品、容量为 w 时的最大价值；
  • 对第 i 件物品，选择只有两种：装或不装。
int knapsack(int[] wt, int[] val, int W) {
    int n = wt.length;
    int[][] dp = new int[n + 1][W + 1]; // 第 0 行第 0 列全为 0，即 base case
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i - 1] < 0) {
                dp[i][w] = dp[i - 1][w];  // 装不下，只能不选
            } else {
                dp[i][w] = Math.max(
                    dp[i - 1][w],                          // 不选第 i 件
                    dp[i - 1][w - wt[i - 1]] + val[i - 1]  // 选第 i 件
                );
            }
        }
    }
    return dp[n][W];
}

拿 wt = [1, 3, 4]、val = [15, 20, 30]、W = 4 填一遍表，状态转移就一目了然（每格 = “不选它” 与 “选它” 的较大者）：

dp w=0 w=1 w=2 w=3 w=4
i=0（无物品） 0 0 0 0 0
i=1（重1值15） 0 15 15 15 15
i=2（重3值20） 0 15 15 20 35
i=3（重4值30） 0 15 15 20 35

压缩成一维数组时，容量必须倒序遍历（w 从 W 往小走），保证 dp[w - wt[i]] 取到的还是"上一行"的旧值——每件物品只被选一次。这是 01 背包最常考的实现细节。

2.4 系列二：子序列问题（双指针撞在表上）

编辑距离、最长公共子序列、最长回文子序列，套路一致：两个指针分别从两个字符串的尾部往前走，dp 表二维，指针的每种走法对应表里的一个相邻格子。

以**编辑距离（LeetCode 72：给两个字符串 s1、s2，允许插入、删除、替换三种操作，求把 s1 变成 s2 的最少操作次数）**为例：dp[i][j] 表示 s1 的前 i 个字符变成 s2 的前 j 个字符所需的最少操作数。指针在 i, j 处时，如果字符相同就白走一步（dp[i-1][j-1]），否则三种操作对应三个相邻格子：

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) dp[i][0] = i; // base case：s2 为空，删光
    for (int j = 1; j <= n; j++) dp[0][j] = j; // base case：s1 为空，插满
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];        // 字符相同，什么都不做
            } else {
                dp[i][j] = Math.min(
                    Math.min(dp[i - 1][j] + 1,      // 删：i 指针前移
                             dp[i][j - 1] + 1),     // 插：j 指针前移
                    dp[i - 1][j - 1] + 1            // 改：两个指针都前移
                );
            }
        }
    }
    return dp[m][n];
}

**最长公共子序列（LeetCode 1143：给两个字符串，求它们最长公共子序列的长度，子序列不要求连续）**是同一框架的另一个变体：字符相同时 dp[i][j] = dp[i-1][j-1] + 1，不同时取 max(dp[i-1][j], dp[i][j-1])——表的形状和编辑距离完全一样，只是"不匹配"时的转移规则不同。

最长递增子序列（LeetCode 300：给一个整数数组，求最长严格递增子序列的长度，子序列不要求连续） 则是单序列的代表：dp[i] 表示"以 nums[i] 结尾"的最长递增子序列长度，状态转移是回头看所有比它小的元素：

int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1); // 每个元素自己就是长度 1 的递增子序列
    int res = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

书里还给了 O(n log n) 的二分优化，视角很妙：递增子序列问题等价于玩纸牌游戏"耐心排序"——维护若干牌堆顶，每张牌放到第一个不小于它的堆顶，堆数就是 LIS 长度，堆顶数组天然单调递增所以可二分。一题多解，但起点都是那个 O(n^2) 的 dp 定义。

2.5 系列三：股票买卖——状态机是 DP 的特例

股票系列六题，书里用一个状态机统一吃掉：状态是三元组"第几天、手里有没有股票、还能交易几次"，每天的选择只有买、卖、不动三种。

stateDiagram-v2
    state "手里无股票" as s0
    state "手里有股票" as s1
    [*] --> s0
    s0 --> s1 : 买入
    s1 --> s0 : 卖出
    s0 --> s0 : 不动
    s1 --> s1 : 不动

以**含冷冻期（LeetCode 309：给一个每日股价数组，可多次买卖但同一时刻最多持有一股，且卖出后第二天不能买入，求最大利润）**为例——只需让"买入"依赖前天的状态：

int maxProfit(int[] prices) {
    int dp_i_0 = 0;                  // 今天结束时手里无股票的最大利润
    int dp_i_1 = Integer.MIN_VALUE;  // 今天结束时手里有股票的最大利润
    int dp_pre_0 = 0;                // dp[i-2][0]，前天的无股票利润（冷冻期用）
    for (int i = 0; i < prices.length; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);    // 昨天就无 / 今天卖出
        dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);  // 昨天就有 / 前天无、冷冻后今天买入
        dp_pre_0 = temp;
    }
    return dp_i_0; // 最后一天还持有股票没有意义，答案必在"无股票"状态
}

限交易次数就再加一维 k，“买卖一次"是 k = 1，“不限次数"是 k 等于无穷大从而可以省略——六题全是同一套状态机的参数变化。

2.6 系列四：打家劫舍——偷或不偷

原题（LeetCode 198）：一排房屋，每间藏有一定现金，相邻两间不能同时偷（否则触发警报），求最多能偷多少。状态是"当前到第几间房”，选择是"偷或不偷”：偷了第 i 间就不能偷第 i - 1 间。环形版（LeetCode 213：房屋围成一圈，首尾不能同时偷）拆成"去掉首"和"去掉尾"两个普通版各跑一遍取最大；树上版（LeetCode 337：房屋被组织成一棵二叉树，直接相连的父子节点不能同时偷）把 dp 挂到二叉树的后序遍历上——又回到第 3 节的递归框架。

书里那句大实话：状态转移方程不是想出来的，是把"状态、选择、base case"三步老老实实走完，它自己浮出水面的。

3. 二叉树：所有递归的练兵场

作者反复强调：递归的所有技巧都可以在二叉树上练，因为二叉树的遍历框架是最小、最干净的递归模板。

void traverse(TreeNode root) {
    // 前序位置：进入节点时执行
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置：离开节点时执行
}

框架里注释掉的那三个位置，是全书树题的题眼：

  • 前序位置的代码在"刚进入节点"时执行，此时只能利用父节点传下来的信息；
  • 后序位置的代码在"离开节点"时执行，此时已经拿到左右子树的计算结果——凡是要"汇总子树信息"的题（直径、最大路径和、判断是否平衡），答案一定在后序位置；
  • 中序位置在 BST 里等于升序遍历，BST 的题大多围绕这个性质。

一个前序位置的最简例子是翻转二叉树（LeetCode 226：给一棵二叉树，交换每个节点的左右子树）——交换只用当前节点自身的信息，天然属于前序位置：

TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    // 前序位置：先交换当前节点的左右孩子，再递归下去
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

书里给递归定了一条纪律，专治"递归想不清楚"：写递归函数时，只定义"这个函数对当前节点做什么"，绝不在脑子里跳进递归里追细节——递归树天然存在，你跳进一层就会跳进无数层。

3.1 例题：二叉树的直径（LeetCode 543）——后序位置的教科书用法

直径是任意两节点间最长路径的边数。关键观察：经过某个节点的最长路径 = 左子树深度 + 右子树深度。要拿到左右子树的深度，代码必须放在后序位置：

int maxDiameter = 0;

int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int left = maxDepth(root.left);   // 先递归拿到子树结果
    int right = maxDepth(root.right);
    // 后序位置：此刻已掌握左右子树的全部信息
    maxDiameter = Math.max(maxDiameter, left + right);
    return 1 + Math.max(left, right); // 向父节点汇报自己的深度
}

注意这个函数的"双重身份"：返回值是"深度"（给父节点用），全局变量维护的是"直径"（答案本身）。想清楚函数向上一级汇报什么，后序位置的题就通了。

3.2 例题：最近公共祖先（LeetCode 236）

给一棵二叉树和两个节点 p、q，求它们的最近公共祖先——即同时是两者祖先、且深度最大的那个节点：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    if (root == p || root == q) return root; // base case：当前就是目标之一
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 后序位置：左右各找到一个，说明当前节点就是分叉点
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

短短五行，能写对的前提是把函数定义想死：“返回以 root 为根的树里 p、q 的最近公共祖先，找不到就返回 null”，然后只处理当前节点这一层，剩下的交给递归。

3.3 BST：把二分查找搬到树上

BST 的中序遍历是升序序列，这一条性质撑起一族题。**第 K 小元素（LeetCode 230：给一棵 BST 和整数 k，求第 k 小的节点值）**就是中序遍历数到第 k 个：

int count = 0, res = 0;

int kthSmallest(TreeNode root, int k) {
    traverse(root, k);
    return res;
}

void traverse(TreeNode root, int k) {
    if (root == null) return;
    traverse(root.left, k);
    count++;                    // 中序位置：按升序被访问
    if (count == k) { res = root.val; return; }
    traverse(root.right, k);
}

BST 的增删查改则演示了另一个套路：利用"中序有序"的特性，每一步都是"和当前节点比大小，决定进左子树还是右子树"——查（LeetCode 700）、插（LeetCode 701）、删（LeetCode 450）都是这个模式，本质是把二分查找的"区间折半"换成了"子树取舍"。删除节点时唯一麻烦的是目标节点有两个孩子：用右子树的最小节点（或左子树的最大节点）替位，保证 BST 性质不被破坏。

4. 回溯：决策树的 DFS

回溯算法在书里的定位非常干脆：回溯就是暴力穷举一棵决策树，外加撤销选择。它和动态规划是亲兄弟——都是穷举，区别是回溯解决的问题没有重叠子问题（或者指数级的解空间本身就是你要的输出），所以备忘录帮不上忙，只能老老实实走完整棵树。

框架就五行伪代码：

result = []
void backtrack(路径, 选择列表) {
    if (满足结束条件) { result.add(路径); return; }
    for (选择 : 选择列表) {
        做选择（把选择加进路径）
        backtrack(路径, 更新后的选择列表)
        撤销选择（把选择从路径里删掉）
    }
}

三个要素：路径（已做的选择）、选择列表（当前可做的选择）、结束条件（到达决策树叶子）。

flowchart TD
    A["全排列问题<br/>选择列表 1 2 3"] --> B["选1<br/>列表剩 2 3"]
    A --> C["选2<br/>列表剩 1 3"]
    B --> D["选2 列表剩3<br/>到达叶子 收集结果"]
    D -.->|"撤销选择<br/>回到父节点"| B
    B -.->|"撤销选择"| A

4.1 例题：全排列（LeetCode 46）——框架的标准照

给一个不含重复数字的数组，返回它的所有可能排列。每层的选择列表是"还没用过的数字"，结束条件是路径长度等于 n：

List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>(); // 路径
boolean[] used;                                  // 标记哪些数字已进路径

List<List<Integer>> permute(int[] nums) {
    used = new boolean[nums.length];
    backtrack(nums);
    return res;
}

void backtrack(int[] nums) {
    if (track.size() == nums.length) {  // 结束条件：到达叶子
        res.add(new LinkedList<>(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;      // 已在路径里的跳过
        track.add(nums[i]);         // 做选择
        used[i] = true;
        backtrack(nums);
        track.removeLast();         // 撤销选择：关键一步，漏了就错
        used[i] = false;
    }
}

4.2 例题：子集（LeetCode 78）——结束条件藏在收集时机里

给一个不含重复元素的数组，返回它的全部子集（幂集，共 2^n 个）。子集和排列的差别很小，却体现回溯的精髓：每个节点（不只叶子）都是一个子集，所以一进函数就先收集；再用 start 参数剪掉"回头路"，避免 [1,2] 和 [2,1] 算重：

List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();

List<List<Integer>> subsets(int[] nums) {
    backtrack(nums, 0);
    return res;
}

void backtrack(int[] nums, int start) {
    res.add(new LinkedList<>(track));   // 前序位置收集：每个节点都是答案
    for (int i = start; i < nums.length; i++) {
        track.add(nums[i]);
        backtrack(nums, i + 1);         // start 保证只往后选，组合不重复
        track.removeLast();
    }
}

组合（LeetCode 77：从 1 到 n 中选出 k 个数的所有组合）、组合总和（LeetCode 39：数组元素可重复选用，求所有凑成目标和的组合）全是这个模板的微调：改一下结束条件、允许不允许重复选同一个元素而已。

4.3 例题：N 皇后（LeetCode 51）——剪枝的价值

在 n×n 的棋盘上放置 n 个皇后，要求任意两个不互相攻击（不同行、不同列、不同对角线），返回所有合法摆法。逐行放皇后是"做选择"，列和两条对角线的冲突检测是"剪枝"——回溯的效率全靠剪枝，剪掉一个不合法的分支就是砍掉一整棵子树：

List<List<String>> res = new ArrayList<>();

List<List<String>> solveNQueens(int n) {
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(board, 0);
    return res;
}

void backtrack(char[][] board, int row) {
    if (row == board.length) {      // 结束条件：最后一行也放好了
        List<String> snapshot = new ArrayList<>();
        for (char[] r : board) snapshot.add(new String(r));
        res.add(snapshot);
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (!isValid(board, row, col)) continue; // 剪枝：冲突直接跳过
        board[row][col] = 'Q';      // 做选择
        backtrack(board, row + 1);  // 逐行放，行内天然不冲突
        board[row][col] = '.';      // 撤销选择
    }
}

boolean isValid(char[][] board, int row, int col) {
    // 只需检查上方：同列、左上对角、右上对角（下面的行还没放）
    for (int i = 0; i < row; i++)
        if (board[i][col] == 'Q') return false;
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        if (board[i][j] == 'Q') return false;
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++)
        if (board[i][j] == 'Q') return false;
    return true;
}

“做选择 → 递归 → 撤销选择"这三板斧练熟，排列、组合、子集、括号生成（LeetCode 22：生成 n 对合法括号的所有组合）、解数独（LeetCode 37：填充 9×9 数独的空格，使每行、每列、每宫都合法），全是换皮。

5. BFS：最短路径的层序穷举

DFS 遍历到叶子才回头，BFS 则是一层一层往外扩——这个"齐头并进"的性质，决定了它的招牌场景：无权图的最短路径。因为第 k 层就是"距离起点 k 步"的所有节点，第一次撞到终点时，步数必然最少。

框架：队列 + visited 集合（防止走回头路死循环）：

Queue q;  q.offer(起点);  visited.add(起点);
int step = 0;
while (q 非空) {
    把当前层的所有节点一次性取出，向四周扩散;
    未访问过的邻居入队并标记 visited;
    step++;
}

5.1 例题：二叉树的最小深度（LeetCode 111）

给一棵二叉树，求从根节点到最近叶子节点的最短路径上的节点数。框架的"一次性取出当前层"用 sz = q.size() 实现，这是 BFS 分层的关键手法：

int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int depth = 1; // 起点算第 1 层
    while (!q.isEmpty()) {
        int sz = q.size();          // 锁定当前层的节点数
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            if (cur.left == null && cur.right == null)
                return depth;       // 第一个遇到的叶子必是最浅的
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        depth++;
    }
    return depth;
}

为什么这题 BFS 优于 DFS？如果树很深但答案很浅（比如链式树、第二层就有叶子），DFS 会把最深的分支走完才回头，BFS 到第二层就收工。最短问题想 BFS，全部/存在性问题想 DFS，大体不会错。

5.2 例题：打开转盘锁（LeetCode 752）——什么都能抽象成图

从 “0000” 出发，每次只能把某一位向上或向下拨一格，不能经过 deadends 里的死亡组合，求到 target 的最少拨动次数。

抽象的一步最见功力：每个四位组合是一个节点，拨一下是一条边，“最少几次"就是无权图最短路径。每个节点固定有 8 个邻居（4 位 × 上下两个方向）：

int openLock(String[] deadends, String target) {
    Set<String> deads = new HashSet<>(Arrays.asList(deadends));
    Set<String> visited = new HashSet<>(); // 走过的组合，防死循环
    Queue<String> q = new LinkedList<>();
    q.offer("0000");
    visited.add("0000");
    int step = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            String cur = q.poll();
            if (deads.contains(cur)) continue; // 死亡组合，掐断分支
            if (cur.equals(target)) return step;
            for (int j = 0; j < 4; j++) {      // 四个转盘
                String up = plusOne(cur, j);   // 第 j 位向上拨
                if (!visited.contains(up)) { visited.add(up); q.offer(up); }
                String down = minusOne(cur, j); // 第 j 位向下拨
                if (!visited.contains(down)) { visited.add(down); q.offer(down); }
            }
        }
        step++;
    }
    return -1;
}

作者还提了双向 BFS：从起点和终点同时扩散，两军会师即收兵，搜索空间从 O(b^d) 降到 O(b^(d/2))——但前提是终点明确。这种"优化只在特定前提成立时可用"的提醒，比优化本身更值钱。

同构的练习题是单词接龙（LeetCode 127：给起始词、结束词和词典，每次只能改一个字母且中间词必须在词典里，求最短转换序列的长度）——每个单词是节点、只差一个字母即连边，抽象完就是转盘锁换皮，双向 BFS 在此同样适用。

6. 双指针、滑动窗口与二分查找：线性结构的剪刀

线性结构（数组、链表、字符串）上的套路，全书归纳成三组"剪刀”。

6.1 快慢指针：链表的三板斧

例题一：删除链表的倒数第 N 个节点（LeetCode 19：给一个链表，删除倒数第 n 个节点并返回头节点）。 快指针先走 n 步，然后快慢同步走；快指针停在末尾时，慢指针正好落在待删节点的前一个：

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1, head); // 虚拟头节点，统一"删第一个"的情况
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) fast = fast.next; // 快指针先走 n 步
    while (fast.next != null) {   // 快慢同步，快指针停在最后一个节点
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;   // 慢指针恰好是待删节点的前驱
    return dummy.next;
}

例题二：环形链表 II（LeetCode 142：给一个链表，判断是否有环，有则返回环的入口节点）。 快指针走两步、慢指针走一步，能相遇则有环；相遇后让一个指针回到起点、两指针各走一步，再次相遇处就是环入口：

flowchart LR
    H["head"] --> A["..."] --> C["环入口"]
    C --> D["..."] --> E["第一次相遇点"]
    E --> F["..."] --> C
ListNode detectCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;   // 快两步
        slow = slow.next;        // 慢一步
        if (fast == slow) break; // 相遇，证明有环
    }
    if (fast == null || fast.next == null) return null; // 走到头，无环
    slow = head;                 // 慢指针回起点
    while (slow != fast) {       // 各走一步再相遇，即环入口
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

为什么回起点后同步走能定位环入口？设起点到环入口 k 步，相遇时慢指针走了 s 步、快指针走了 2s 步，多走的 s 步必在环里绕了整数圈——所以相遇点再前进 k 步就回到环入口，而起点前进 k 步也到环入口，二者必在那里碰头。书里用这张图把这个"巧合"讲成了算术。

同理，快指针到头时慢指针恰在链表中点（LeetCode 876：返回链表的中间节点），中点又是归并排序链表、回文链表判断（LeetCode 234：判断链表是否为回文——先找中点、反转后半段、再逐位比对）的入口。

6.2 左右指针：从两头夹逼

从数组两端向中间走，每步都能排除一批不可能解——有序数组两数之和（LeetCode 167：在升序数组中找出和为 target 的两个数的下标）、反转数组、回文判断、二分查找都是它。以两数之和为例：left 指小端、right 指大端，和偏小就 left++，偏大就 right--，数组的有序性保证每次移动都不会错过答案。

6.3 滑动窗口：最小覆盖子串（LeetCode 76）

本质是一个维护"窗口内某种状态"的左右指针：右指针负责扩张找可行解，左指针负责收缩找最优解。书里把最小覆盖子串当模板题——在 s 中找包含 t 全部字符的最短子串：

String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);

    int left = 0, right = 0, valid = 0;     // valid：计数已满足的字符种类数
    int start = 0, len = Integer.MAX_VALUE; // 最优解的起点和长度
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;                            // 右指针扩张窗口
        if (need.containsKey(c)) {
            window.merge(c, 1, Integer::sum);
            if (window.get(c).equals(need.get(c))) valid++;
        }
        while (valid == need.size()) {      // 窗口已覆盖 t，开始收缩
            if (right - left < len) { start = left; len = right - left; }
            char d = s.charAt(left);
            left++;
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--;
                window.merge(d, -1, Integer::sum);
            }
        }
    }
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}

need 和 window 两张计数表就是窗口的"状态”，valid 是"状态达标"的开关。这套写法一字不改地能套到无重复字符的最长子串（LeetCode 3：求不含重复字符的最长子串长度）、字符串的排列（LeetCode 567：判断 s2 的子串中是否存在 s1 的某个排列）、**找所有字母异位词（LeetCode 438：找出 s 中所有与 p 互为字母异位词的子串起点）**上，区别只在收缩条件和更新答案的时机。

6.4 二分查找：区间定义是一切的源头

单独成章，因为"细节是魔鬼"：while 条件带不带等号、mid 加一还是减一、right 初值是 n 还是 n - 1，网上答案互相矛盾。作者的解法是先声明你维护的搜索区间，其余全部推出，绝不靠记忆。以左闭右闭 [left, right] 为例：

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; // 区间 [left, right] 两端都可能命中
    while (left <= right) {                // 区间为空（left == right + 1）才停
        int mid = left + (right - left) / 2; // 防溢出写法
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1; // 新区间 [mid+1, right]
        else right = mid - 1;                        // 新区间 [left, mid-1]
    }
    return -1;
}

因为区间两端都"闭"，mid 已经查过就必须排除出新区间（所以 ± 1），循环条件就是 left <= right——每一行都能从区间定义推出来。

找左侧边界的变体（LeetCode 34：在含重复元素的升序数组中，找 target 第一次和最后一次出现的位置），只差"命中后不返回、继续向左收缩"：

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) right = mid - 1; // 锁定左侧，继续搜 [left, mid-1]
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    if (left >= nums.length || nums[left] != target) return -1;
    return left;
}

这三组剪刀的共同思想：利用有序性或单调性，让指针每走一步都排除掉一批不可能解——这正是"聪明地穷举"在线性结构上的样子。

7. 其他套路速览：每个都记一句"什么时候用"

书的剩余部分是一批"小而锋利"的工具，先记一句话定位，再给两个最常用的补上关键代码：

  • 前缀和：需要反复查询"某段区间的和"时，先花 O(n) 预处理，之后每次查询 O(1)；
  • 差分数组：需要对区间反复做"整体加减"时，只改区间的两个端点，最后一次性重建（LeetCode 370：区间加法；LeetCode 1094：拼车——上下车区间叠加后不能超过座位数）；
  • 单调栈：解决"下一个更大元素"——栈里维护递减序列，新元素把比它小的全弹出去，被弹者的答案就是它；
  • 并查集：处理"连通性"问题，union 合并、find 查询，路径压缩后接近 O(1)（LeetCode 200：数网格中岛屿数量——逐格合并相邻陆地，或直接 DFS/BFS"沉岛"计数）；
  • LRU 缓存：哈希表 + 双向链表——哈希表负责 O(1) 查找，双向链表负责 O(1) 维护访问顺序，满了从尾部淘汰（LeetCode 146：实现一个 get/put 都是 O(1) 的缓存）；
  • 洗牌算法（Fisher-Yates）：从后往前，每一位和它之前（含自己）的随机位交换，保证每种排列等概率（LeetCode 384：打乱数组）；
  • 区间调度（贪心）：安排最多互不冲突的区间，按结束时间排序、每步选结束最早的（LeetCode 435：最少删除多少区间使剩余互不重叠——正是此题的反面）。

7.1 例题：每日温度（LeetCode 739）——单调栈

给一个温度数组，对每一天回答"还要等几天才会更热"。倒序入栈，栈内维护单调递减：

int[] dailyTemperatures(int[] T) {
    int[] res = new int[T.length];
    Deque<Integer> stack = new ArrayDeque<>(); // 存索引，对应温度单调递减
    for (int i = T.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && T[stack.peek()] <= T[i])
            stack.pop();              // 弹出不如我热的：它们已被"我"挡住
        res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
        stack.push(i);
    }
    return res;
}

每个元素最多入栈出栈各一次，O(n) 搞定 O(n^2) 的暴力。“下一个更大/更小元素"这类字眼一出现，条件反射想单调栈。

7.2 例题：和为 K 的子数组（LeetCode 560）——前缀和 + 哈希表

朴素前缀和只能回答"从 0 到 i 的和”，配合哈希表记录每个前缀和的出现次数，就能 O(n) 数出所有和为 k 的连续子数组：

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> preSum = new HashMap<>(); // 前缀和 -> 出现次数
    preSum.put(0, 1); // 空前缀：和为 0 出现 1 次，处理从索引 0 开始的子数组
    int sum = 0, res = 0;
    for (int num : nums) {
        sum += num;                             // 当前前缀和
        res += preSum.getOrDefault(sum - k, 0); // 有几个前缀和等于 sum-k，就有几个合法子数组
        preSum.merge(sum, 1, Integer::sum);
    }
    return res;
}

核心等式：若 preSum[j] - preSum[i] = k，则 (i, j] 是一段合法子数组。把"枚举所有区间"变成"查一次哈希表"，又是给穷举减肥的典型。

8. 带走的清单

把全书压成一张刷题前的检查清单：

拿到题先分类

  • 求最值、问"最少/最多/最长"？十有八九是动态规划——走"状态 → dp 定义 → 选择 → base case"四步（参考凑零钱、背包、编辑距离）。
  • 要列出"所有可行解"（排列、组合、棋盘）？回溯——写"路径、选择列表、结束条件"，再想剪枝（参考全排列、子集、N 皇后）。
  • 无权图里问"最短/最少几步"？BFS——队列加 visited，层序扩散（参考转盘锁）。
  • 线性结构上找子串、配对、倒数第 k 个？先想双指针和滑动窗口，别急着上重型武器（参考最小覆盖子串、倒数第 N 个节点）。
  • 有序数组里查找？二分——先声明搜索区间的开闭，再写代码。

写递归时的纪律

  • 默念"一切递归皆树遍历"，画出那棵隐形的递归树。
  • 只定义当前节点做什么，不跳进递归追细节（参考最近公共祖先的五行代码）。
  • 想清代码该放前序、中序还是后序位置：用父节点信息放前序，汇总子树结果放后序（参考二叉树直径）。
  • 递归树有大量重复子树？这就是重叠子问题，上备忘录或 DP 表（参考斐波那契）。

优化时的方向感

  • 先写"暴力穷举但正确"的版本，再谈优化——备忘录、剪枝、指针单调性，全是给穷举减肥。
  • 反复查区间和 → 前缀和；反复改区间 → 差分；问"下一个更大" → 单调栈；问连通性 → 并查集。
  • 双向 BFS 这类优化有前提条件，用之前先确认前提成立。

心态上

  • 不背题，背框架；题目是无穷的，框架是有限的。
  • 刷题量在框架之后：框架不熟时刷 300 题，不如框架熟了刷 100 题。

这本书的最大价值不是哪个具体算法，而是它把刷题从"背答案的体力活"变成了"识别穷举结构的智力活"——看透每个技巧都只是在给穷举减肥，算法题就从玄学变回了工程。

参考书籍：labuladong（付东来）《labuladong 的算法小抄》，电子工业出版社（博文视点），2020；配套开源项目见其 GitHub 算法教程仓库。文中代码按书中框架用 Java 整理，对应 LeetCode 题号已标注。

方糖猫
方糖猫（大可）

18 年后端架构，现在独立做 AI 产品。这里记录 AI 视频、AI Agent 与工程实践。

本文阅读量 次