回溯与图论高频 - 面试题

#

★★★

1. 全排列（含重复元素去重）的回溯模板中 used 数组与同层剪枝的原理？

问题

全排列（含重复元素去重）的回溯模板，说明 used 数组与同层剪枝的原理？

考察点

回溯模板：choose/explore/unchoose
used 数组标记已选
同层剪枝去重

答案

全排列回溯：递归选择每个位置，用 used 数组标记元素是否已被选。每层尝试所有未选元素，加入当前排列，递归下一层，返回后撤销（remove 最后 + used 置 false）。去重（含重复元素）：先排序，同层剪枝——若当前元素与前一个元素相同，且前一个元素未被使用（说明前一个已被本层尝试过/或本层刚移除），则跳过，避免产生相同排列。即 if(i>0 && nums[i]==nums[i-1] && !used[i-1]) continue。原理：排序后相同元素相邻，同层只允许第一个相同元素进入，后续相同元素因"前已用"被剪枝，保证每个值只在该层出现一次。used 数组标记"跨层"的已选，同层剪枝标记"同层"的去重，两者配合。

解析

used 数组管"深度"（每层不重复选同一元素），同层剪枝管"宽度"（同层不重复枚举相同值）。排序是去重前提。掌握"used + 同层剪枝"是含重复全排列/组合/子集去重的通用模板。

示例代码

List<List<Integer>> res = new ArrayList<>();
void permute(int[] nums, int[] used, List<Integer> cur) {
    if (cur.size() == nums.length) { res.add(new ArrayList<>(cur)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i] == 1) continue;
        if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue; // 同层剪枝
        used[i] = 1; cur.add(nums[i]);
        permute(nums, used, cur);
        cur.remove(cur.size() - 1); used[i] = 0; // 撤销
    }
}

#

★★★

2. 组合总和系列（可重复选/不可重复/固定个数）的剪枝与去重差异？

问题

组合总和系列（可重复选/不可重复/固定个数），说明剪枝与去重差异？

考察点

可重复选：start 不递增
不可重复：start=i+1
固定个数：增加 k 限制

答案

组合总和系列：① 可重复选（39）：每层从 start 开始，可重复选当前元素，参数传 i（不递增），即 start=i 允许重复；剪枝：排序后若当前元素已超过剩余目标则 break。② 不可重复选（40）：每个元素只用一次，参数传 i+1；去重：同层跳过相同元素（i>start && nums[i]==nums[i-1] 跳过）。③ 固定个数（77）：限制组合长度 k，达到 k 时结束。剪枝：剩余元素不足 k-cur.size() 时提前剪枝。差异：可重复用 start=i，不可重复用 start=i+1 且同层去重；固定个数加 k 限制。去重前提都是排序。

解析

组合题的差异在"start 的推进"与"同层去重"：可重复 start=i，不可重复 start=i+1，重复值去重靠"排序+同层跳过"。固定个数是加约束。掌握"start 参数 + 剪枝"即可覆盖组合系列。

示例代码

// 可重复选（39）：start 不递增
void dfs(int[] c, int start, int target, List<Integer> cur) {
    if (target == 0) { res.add(new ArrayList<>(cur)); return; }
    for (int i = start; i < c.length; i++) {
        if (c[i] > target) break; // 剪枝
        cur.add(c[i]);
        dfs(c, i, target - c[i], cur); // start=i 可重复
        cur.remove(cur.size() - 1);
    }
}

#

★★★

3. Dijkstra 算法的堆优化实现中为什么不能处理负权边？与 Bellman-Ford/SPFA 的适用边界？

问题

Dijkstra 的堆优化实现，说明为何不能处理负权边，以及与 Bellman-Ford/SPFA 的适用边界？

考察点

堆优化 Dijkstra 的贪心
不能处理负权的原因
与 Bellman-Ford/SPFA 边界

答案

Dijkstra 堆优化：用优先队列，每次取当前距离最小的节点，松弛其边，标记已确定。贪心正确性依赖"已确定最短距离的节点不会再被更新"，这要求边权非负。若存在负权边，一个已确定节点的距离可能被后续更远节点经负权边再次更新，破坏贪心，导致错误。故 Dijkstra 不能处理负权。Bellman-Ford：对所有边做 V-1 轮松弛，O(VE)，能处理负权并检测负环（第 V 轮仍可松弛则有负环）。SPFA：基于队列的 Bellman-Ford 优化，平均快，最坏 O(VE)。适用边界：非负权用 Dijkstra（最快 O(E log V)）；负权无负环用 Bellman-Ford/SPFA；有负环则无最短路（Bellman-Ford 可检测）。

解析

Dijkstra 的"贪心选定"成立需非负权（否则已定节点可能被负权更新）。Bellman-Ford 用"多轮松弛"容忍负权并检测负环，SPFA 是队列优化。选型看是否含负权、是否需检测负环。

示例代码

int[] dijkstra(int src, List<List<int[]>> adj) {
    int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{src, 0});
    while (!pq.isEmpty()) {
        int[] top = pq.poll(); int u = top[0], d = top[1];
        if (d > dist[u]) continue; // 惰性删除
        for (int[] e : adj.get(u)) {
            int nd = d + e[1];
            if (nd < dist[e[0]]) { dist[e[0]] = nd; pq.offer(new int[]{e[0], nd}); }
        }
    }
    return dist;
}

#

★★★

4. 回溯算法的模板中路径-选择-约束（choose/explore/unchoose）三要素，剪枝如何加速？

问题

回溯算法的模板，说明路径-选择-约束三要素，以及剪枝如何加速？

考察点

回溯三要素：choose/explore/unchoose
剪枝原理
复杂度与剪枝

答案

回溯模板：① 路径（path）：当前已构造的解；② 选择（choices）：当前可选的候选；③ 约束（constraints）/终止条件：何时停止（如达到目标长度或满足条件）。三要素结构：递归函数维护 path 与 choices，每层做出选择加入 path，递归 explore，返回后撤销选择（unchoose）。步骤如下：先判断终止条件（是否记录解），再遍历候选，检查可用性（剪枝），做选择→递归→撤销。剪枝加速：在 explore 前用约束排除不可能的分支（如已超目标、剩余不足、非法候选），避免深入无效子树，大幅减少搜索空间。剪枝是回溯的性能关键，复杂度从指数级（全枚举）降到可行范围。

解析

回溯是"带剪枝的 DFS"，三要素（path/choices/result）是统一框架。剪枝通过"提前判断约束"跳过无效分支，常把指数复杂度降到可接受。掌握"choose/explore/unchoose"与剪枝是回溯题的标准解法。

示例代码

void backtrack(List<Integer> path, List<Integer> choices) {
    if (isSolution(path)) { result.add(new ArrayList<>(path)); return; }
    for (int c : choices) {
        if (!isValid(c, path)) continue; // 剪枝
        path.add(c);                     // choose
        backtrack(path, choices);        // explore
        path.remove(path.size() - 1);    // unchoose
    }
}

#

★★★

5. 无向图的割点与桥（Tarjan）中 low 与 dfn 数组如何判定割点或桥，根节点为何要特判？

问题

无向图的割点与桥（Tarjan），说明 low 与 dfn 数组如何判定割点或桥，以及根节点为何要特判？

考察点

dfn（访问序）与 low（可回溯最小编号）
割点判定：子树无法回溯到父之上
桥判定：low[子] > dfn[父]

答案

Tarjan 算法用 dfn[u]（DFS 访问序）与 low[u]（u 能通过树边/回边回溯到的最早 dfn）。DFS 时，对树边 u→v：low[u]=min(low[u], low[v])；对回边 u→v（v 已访问非父）：low[u]=min(low[u], dfn[v])。割点判定：非根节点 u 是割点当且仅当存在子节点 v 使 low[v] ≥ dfn[u]（v 的子树无法回溯到 u 之上，去掉 u 后该子树断开）。桥判定：边 u→v 是桥当且仅当 low[v] > dfn[u]（v 子树无法回溯到 u 或更上）。根节点特判：根是割点当且仅当它有 ≥2 个孩子（DFS 树中），因为根去掉后每个孩子子树独立成连通块；若根只有一个孩子，去掉根后仍连通，不是割点。所以根节点不能套用"low[child]≥dfn[root]"的判定（根没有父之上），需单独统计孩子数。

解析

割点与桥的判定都基于 low 与 dfn 的关系：割点看"子树能否回退到父之上"（low≥dfn[u]），桥看"子树能否回退到父或更早"（low>dfn[u]）。根节点无"父之上"，故用孩子数特判。low 的更新（树边 vs 回边）是算法核心。

示例代码

int[] dfn, low; int time = 0;
void dfs(int u, int parent) {
    dfn[u] = low[u] = ++time;
    int children = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        if (dfn[v] == 0) { // 树边
            dfs(v, u); children++;
            low[u] = Math.min(low[u], low[v]);
            if (parent != -1 && low[v] >= dfn[u]) isArticulation[u] = true; // 非根割点
            if (low[v] > dfn[u]) // 桥 u-v
        } else low[u] = Math.min(low[u], dfn[v]); // 回边
    }
    if (parent == -1 && children >= 2) isArticulation[u] = true; // 根特判
}

#

★★★

6. 最小生成树 Kruskal（并查集）与 Prim（堆）的复杂度对比及稠密/稀疏图选型？

问题

最小生成树 Kruskal（并查集）与 Prim（堆）的复杂度对比，及稠密/稀疏图选型？

考察点

Kruskal：排序边 + 并查集
Prim：优先队列贪心
稠密/稀疏选型

答案

Kruskal：把边按权排序，用并查集逐一加入不会成环的边，直到 V-1 条。复杂度 O(E log E)（排序）+ O(E α(V))（并查集）。Prim：从某点开始，用堆维护边权，每次取最小边加入树，访问新顶点并扩展。复杂度 O(E log V)（堆优化）。选型：稀疏图（E 接近 V）用 Kruskal（排序 E log E，E 小）；稠密图（E 接近 V²）用 Prim（E log V，E 大时 log V 更省）。Kruskal 适合边少、实现简单（排序+并查集）；Prim 适合边多、需从某点出发的场景。两者都 O(E log V) 级，但 Kruskal 的排序在边少时更好，Prim 的堆在边多时避免全排序。

解析

Kruskal 代价集中在"排序边"（E log E），Prim 代价在"每边堆操作"（E log V）。稀疏图 E 小，Kruskal 的排序便宜；稠密图 E 大，Prim 的堆操作更省。选型看 E 与 V 的关系。

示例代码

// Kruskal：排序边 + 并查集
Arrays.sort(edges, (a, b) -> a.w - b.w);
int cost = 0, cnt = 0;
for (Edge e : edges) {
    if (union(e.u, e.v)) { cost += e.w; cnt++; if (cnt == V - 1) break; }
}

#

★★★

7. 全排列/组合/子集的去重中 used 数组与排序后跳过相邻重复值的写法？

问题

全排列/组合/子集的去重，说明 used 数组与排序后跳过相邻重复值的写法？

考察点

全排列去重：used + 同层剪枝
组合/子集去重：start + 跳过相邻重复
去重原理

答案

全排列去重：排序后，用 used 数组 + 同层剪枝，if(i>0 && nums[i]==nums[i-1] && !used[i-1]) continue（跳过同层重复值，保证每层每个值只枚举一次）。组合/子集去重：排序后，用 start 索引 + 跳过相邻重复，if(i>start && nums[i]==nums[i-1]) continue（在同一层跳过与前一个相同且 start 之后的重复值，避免重复组合）。两者都需要"排序"使相同值相邻，然后用"跳过相邻重复"剪枝。区别：全排列靠 used 判断"是否同层"，组合/子集靠 start 判断"是否同层"。去重原理：排序后相同值聚在一起，同层只取第一个，后续相同值因"前一个已用/已枚举"被跳过，保证每个值组合只出现一次。

解析

去重统一为"排序 + 同层跳过相邻重复"。全排列用 used 数组区分层，组合/子集用 start 区分层。掌握"跳过相邻重复"的两种写法（used 版与 start 版）即可覆盖所有去重回溯。

示例代码

// 子集去重：start 版
for (int i = start; i < nums.length; i++) {
    if (i > start && nums[i] == nums[i - 1]) continue; // 跳过相邻重复
    cur.add(nums[i]);
    dfs(nums, i + 1, cur);
    cur.remove(cur.size() - 1);
}

#

★★★

8. 单词搜索（矩阵 DFS + 回溯标记）的原地标记与恢复技巧？

问题

单词搜索，说明矩阵 DFS + 回溯标记的原地标记与恢复技巧？

考察点

矩阵 DFS 匹配单词
原地标记已访问（避免重复）
回溯恢复

答案

单词搜索：从每个格子出发 DFS 匹配单词前缀。DFS 时若当前字符与单词对应字符相同则继续向四个方向扩展。已访问标记：把当前格子标记（如改成 '#' 或临时改值），避免在单词内重复访问同一格子。回溯恢复：DFS 返回后恢复原字符，因为该路径失败后其他路径可能再次经过此格子。原地标记与恢复：用特殊字符（如 '*'）标记访问中，递归返回时改回原值，无需额外 visited 数组。复杂度 O(n·m·4^L)（L 为单词长度）。要点：边界检查、字符匹配、标记-恢复。

解析

"原地标记 + 回溯恢复"是矩阵 DFS 的通用技巧：用特殊值标记"访问中"，返回时恢复，避免额外空间。标记必须在递归前设置、返回后恢复，保证不同路径互不干扰。这是"棋盘 DFS + 回溯"的核心。

示例代码

boolean dfs(char[][] b, int i, int j, String word, int k) {
    if (i < 0 || j < 0 || i >= b.length || j >= b[0].length || b[i][j] != word.charAt(k)) return false;
    if (k == word.length() - 1) return true;
    char tmp = b[i][j]; b[i][j] = '#'; // 标记
    boolean found = dfs(b, i + 1, j, word, k + 1) || dfs(b, i - 1, j, word, k + 1)
                 || dfs(b, i, j + 1, word, k + 1) || dfs(b, i, j - 1, word, k + 1);
    b[i][j] = tmp; // 恢复
    return found;
}

#

★★★

9. 图的遍历中 BFS 求最短路径与 DFS 求连通分量的应用？

问题

说明图的遍历中 BFS 求最短路径与 DFS 求连通分量的应用？

考察点

BFS 层序求最短路
DFS 连通分量
各自适用场景

答案

BFS 求最短路径：无权图（或边权相等）的最短路用 BFS，从源点层序扩展，第一次到达某节点即最短距离。适用：无权图最短路、迷宫最短步数、层序扩展类问题。DFS 求连通分量：DFS 遍历标记整个连通分量，对每个未访问节点启动 DFS 计一个连通分量。适用：连通块计数、岛屿数量、有向图强连通分量（Tarjan）、拓扑排序（DFS 后序）。BFS 用队列（按层），DFS 用栈/递归（深度优先）。选型：求最短路用 BFS，求连通性/拓扑用 DFS。两者都 O(V+E)。

解析

BFS 与 DFS 是图和网格的两大遍历。BFS 的"层序"天然匹配最短路，DFS 的"深度优先"天然匹配连通分量探测与拓扑序。理解"按层 vs 按深"的差异决定适用场景。

示例代码

// DFS 连通分量计数
int count;
for (int i = 0; i < n; i++) if (!visited[i]) { count++; dfs(i); }
void dfs(int u) { visited[u] = true; for (int v : adj[u]) if (!visited[v]) dfs(v); }

#

★★★

10. 电话号码的字母组合（LeetCode 17）中回溯模板如何按 digits 逐位展开，与组合问题“选择列表动态生成”的差异？

问题

电话号码的字母组合，说明回溯如何按 digits 逐位展开，以及与组合问题"选择列表动态生成"的差异？

考察点

按 digits 逐位回溯
每位的选择列表由数字决定
与组合问题选择列表差异

答案

电话号码字母组合：回溯递归按 digits 的位推进，每层对应一个数字，该数字的选择列表是它映射的字母（如 '2'→abc）。递归函数携带"当前处理的位 index"，到 index==digits.length() 时记录结果。每层从 map[digit] 中选一个字母加入，递归 index+1，返回后撤销。与组合问题的差异：组合/全排列的"选择列表"通常是全局候选集（从整体中选），选择列表固定（或随 start 变化）；本问题每层的选择列表由"当前数字"动态生成（不同数字列表不同），且每个位置必须选一个（不选则无法继续），是"逐位枚举"而非"从集合中选"。选择列表是"每层独立由输入决定"。

解析

本问题的回溯是"逐位展开"：每层绑定一个数字，选择列表来自该数字的映射。与组合题的"从全局候选集选"不同，这里每层必须选一个且列表因数字而异。理解"每层选择列表的来源"是区分回溯变体的关键。

示例代码

String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
void dfs(String digits, int idx, StringBuilder cur, List<String> res) {
    if (idx == digits.length()) { res.add(cur.toString()); return; }
    String letters = map[digits.charAt(idx) - '0']; // 每层选择列表由数字决定
    for (char c : letters.toCharArray()) {
        cur.append(c); dfs(digits, idx + 1, cur, res);
        cur.deleteCharAt(cur.length() - 1); // 撤销
    }
}

#

★★

11. N 皇后问题中按行回溯 + 列/两对角线占用标记的实现要点？

问题

N 皇后问题，说明按行回溯 + 列/两对角线占用标记的实现要点？

考察点

按行回溯
列、主对角线、副对角线占用标记
对角线下标映射

答案

N 皇后：在 n×n 棋盘放 n 个皇后互不攻击。按行回溯：每行放一个皇后，递归处理第 i 行，尝试该行每列，若该列与两条对角线都未被占用则放置并标记，递归下一行，返回后撤销。占用标记：列用 col[c]；主对角线（\）用 d1[i-c] 或 d1[i-c+n]（下标差 i-c 恒定）；副对角线（/）用 d2[i+c]（下标和恒定）。要点：对角线的下标映射（i-c 与 i+c 恒定），用数组或布尔标记冲突。放置后标记、递归、撤销（回溯）。终止条件：处理完最后一行。

解析

N 皇后是"按行回溯 + 冲突标记"的经典。关键是对角线的标记：主对角线 i-c 恒定、副对角线 i+c 恒定（或加偏移避免负下标）。按行保证每行一个皇后，列/对角线标记保证不冲突。回溯撤销保证每行换列。

示例代码

boolean[] col, d1, d2; List<List<String>> res;
void dfs(int row, int n, List<String> cur) {
    if (row == n) { res.add(new ArrayList<>(cur)); return; }
    for (int c = 0; c < n; c++) {
        if (col[c] || d1[row - c + n] || d2[row + c]) continue;
        col[c] = d1[row - c + n] = d2[row + c] = true;
        cur.add(makeRow(c, n));
        dfs(row + 1, n, cur);
        col[c] = d1[row - c + n] = d2[row + c] = false;
        cur.remove(cur.size() - 1);
    }
}

#

★★

12. 括号生成与复原 IP 地址中约束传播式剪枝如何减少无效分支？

问题

括号生成与复原 IP 地址，说明约束传播式剪枝如何减少无效分支？

考察点

括号生成：左右括号计数约束
复原 IP：段长度与范围约束
剪枝减少无效分支

答案

括号生成：回溯生成括号序列，用约束剪枝——左括号数 < n 时可加 '('，右括号数 < 左括号数时可加 ')'（保证有效）。约束传播：每步只生成合法前缀，剪掉"右括号超过左括号"或"超过 n"的无效分支。复原 IP 地址：回溯分割，每段 1-3 位、范围 0-255、无前导零（除非段为 0），且已用段数 ≤4。剪枝：段长超 3、开头的 0 后不能跟数字、段值超 255、段数超 4 都提前剪枝。两者都用"约束传播"——在做选择的每一步检查约束，非法分支立即放弃，避免生成后再判断，大幅减少无效分支。

解析

约束传播式剪枝是"边生成边约束"：每步只扩展合法前缀，而非"生成全部再过滤"。括号生成用计数约束，IP 用段约束。这比"生成后判断"更高效，是回溯剪枝的典型应用。

示例代码

// 括号生成：左括号数 < n 可加 '('，右括号数 < 左括号数可加 ')'
void dfs(int l, int r, int n, StringBuilder cur) {
    if (cur.length() == 2 * n) { res.add(cur.toString()); return; }
    if (l < n) { cur.append('('); dfs(l + 1, r, n, cur); cur.deleteCharAt(cur.length() - 1); }
    if (r < l) { cur.append(')'); dfs(l, r + 1, n, cur); cur.deleteCharAt(cur.length() - 1); }
}

#

★★

13. 欧拉路径与回路（Hierholzer 算法）中用栈逆序输出，奇度顶点数量如何决定路径是否存在？

问题

欧拉路径与回路（Hierholzer 算法），说明为何用栈逆序输出，以及奇度顶点数量如何决定路径是否存在？

考察点

欧拉路径/回路存在条件
Hierholzer 算法
栈逆序输出

答案

欧拉路径存在条件（无向图）：恰有 0 或 2 个奇度顶点；0 个奇度（全偶）存在欧拉回路，2 个奇度存在欧拉路径（起点为奇度顶点）。有向图：入度=出度则回路，恰一个入度=出度+1 与一个出度=入度+1 则路径。Hierholzer 算法：递归/迭代 DFS，每访问一条边就删除（避免重复），当某节点无路可走时把它"入栈"（或加入结果），最后逆序输出即欧拉路径。为什么用栈逆序输出：DFS 会先深入一条路径抵达死路，此时该节点是欧拉序的"尾部"，后入栈；回溯时其他分支的节点后访问，先入栈。逆序（栈的弹出顺序）恰好把"先到死路的后输出"调整为正确的欧拉路径顺序。即"递归返回时记录"得到逆序，再反转。

解析

存在条件看奇度顶点数（0 或 2）。Hierholzer 用"删边 + 栈逆序"：DFS 死路时入栈，逆序输出得到欧拉路径。栈逆序是因为"先访问的路径段应后输出"（欧拉路径的段序与 DFS 深入顺序相反）。这是"图论构造 + 栈"的经典题。

示例代码

// Hierholzer（有向图）
Deque<Integer> stack = new ArrayDeque<>();
void dfs(int u) {
    while (!adj[u].isEmpty()) {
        int v = adj[u].poll(); // 删边
        dfs(v);
    }
    stack.push(u); // 死路入栈
}
// 欧拉路径 = 逆序弹出 stack

#

★★

14. 单词接龙（LeetCode 127）中如何把词转换建模为无权图 BFS，双向 BFS 为何能把搜索空间从 b^d 降到 b^(d/2)？

问题

单词接龙，说明如何把词转换建模为无权图 BFS，以及双向 BFS 为何把搜索空间从 b^d 降到 b^(d/2)？

考察点

词转换建模为无权图 BFS
双向 BFS 从两端扩展
搜索空间 b^d → b^(d/2)

答案

单词接龙：把每个单词看作节点，两个单词仅一个字符不同则连边（无权图）。求从 beginWord 到 endWord 的最短路径长度用 BFS。构图/扩展：对每个单词，尝试替换每个位置的字符为 'a'-'z'，若变换后的词在字典中则加入下一层，避免了显式建图（O(26×L) 每词）。双向 BFS：同时从 beginWord 与 endWord 两端 BFS，每层扩展较窄的一端，两端的搜索树相遇时即最短路径。复杂度：单向 BFS 搜索空间为 b^d（b 为每层分支数，d 为深度）；双向 BFS 两端各扩展深度 d/2，总空间 2×b^(d/2) ≈ b^(d/2)，因 b^(d/2) 远小于 b^d。双向 BFS 大幅减少中间层爆炸。

解析

建模为无权图后 BFS 求最短路。双向 BFS 的关键是"两端同时扩展，相遇即最短"，把指数搜索空间从 b^d 降到 b^(d/2)。这是"搜索空间剪枝"的经典优化，因为中间层是指数最大的部分。

示例代码

// 双向 BFS
    Set<String> beginSet = new HashSet<>(), endSet = new HashSet<>();
    beginSet.add(beginWord); endSet.add(endWord);
int len = 1;
while (!beginSet.isEmpty()) {
    if (beginSet.size() > endSet.size()) { Set<String> t = beginSet; beginSet = endSet; endSet = t; } // 扩展小的
    Set<String> next = new HashSet<>();
    for (String w : beginSet) for (int i = 0; i < L; i++) {
        char[] c = w.toCharArray();
        for (char ch = 'a'; ch <= 'z'; ch++) { c[i] = ch; String n = new String(c);
            if (endSet.contains(n)) return len + 1;
            if (dict.contains(n)) { next.add(n); dict.remove(n); } } }
    beginSet = next; len++;
}

#

★★

15. 二分图判定与最大匹配中染色法 DFS 与匈牙利算法的原理？

问题

二分图判定与最大匹配，说明染色法 DFS 与匈牙利算法的原理？

考察点

染色法二分图判定
匈牙利算法最大匹配
增广路

答案

二分图判定：用染色法 DFS——把节点染成两种颜色，相邻节点必须异色；DFS 时若发现相邻节点同色则不是二分图。遍历所有节点，若成环由奇数长度则染色冲突。二分图当且仅当可二染色（无奇环）。最大匹配（匈牙利算法）：二分图匹配是选边使无公共顶点，最大匹配匈牙利算法用"增广路"——对每个未匹配左节点，尝试找增广路（从它出发，交替经过未匹配边/匹配边，终止于未匹配节点），找到则把增广路上的边翻转（匹配边变未匹配、未匹配变匹配），匹配数+1。反复找增广路直到无增广路，即最大匹配。匈牙利算法 O(VE)。

解析

染色法判定二分图（无奇环），匈牙利算法求最大匹配（增广路）。两者是二分图的基础理论。染色法用 DFS 二染色看冲突，匈牙利用增广路翻转匹配。理解"二染色"与"增广路"是关键。

示例代码

// 染色法判定
int[] color;
boolean dfsColor(int u, int c) {
    color[u] = c;
    for (int v : adj[u]) {
        if (color[v] == c) return false; // 同色冲突
        if (color[v] == 0 && !dfsColor(v, 3 - c)) return false;
    }
    return true;
}

#

★★

16. 最短路径的选型中 Dijkstra 堆优化、SPFA 的适用边界与负权环检测？

问题

最短路径的选型，说明 Dijkstra 堆优化、SPFA 的适用边界与负权环检测？

考察点

Dijkstra：非负权
SPFA：负权、判负环
选型

答案

Dijkstra 堆优化：O(E log V)，只适用于非负权边，是正权图的最快标准算法。SPFA：基于队列的 Bellman-Ford 优化，能处理负权边，且能用"入队次数"检测负环——若某节点入队次数超过 V 次，则存在负环（负环会使最短路径无限减小）。SPFA 平均快（O(E) 期望）但最坏 O(VE)。选型：① 非负权且无负环 → Dijkstra（最快）；② 有负权但无负环 → Bellman-Ford/SPFA；③ 可能负环 → SPFA 检测入队次数或 Bellman-Ford 第 V 轮松弛。SPFA 的优势是处理负权与检测负环，劣势是可能被构造卡成 O(VE)。工程上非负权优先 Dijkstra。

解析

Dijkstra 快但限非负权，SPFA 慢但能负权+判负环。选型看"是否含负权"。负环检测：SPFA 看入队次数超 V，Bellman-Ford 看第 V 轮是否仍松弛。这是"最短路算法选型"的完整图景。

示例代码

// SPFA 负环检测
int[] cnt = new int[n]; boolean[] inq = new boolean[n];
Deque<Integer> q = new ArrayDeque<>(); q.offer(src); inq[src] = true;
while (!q.isEmpty()) {
    int u = q.poll(); inq[u] = false;
    for (Edge e : adj[u]) {
        if (dist[u] + e.w < dist[e.to]) {
            dist[e.to] = dist[u] + e.w;
            if (!inq[e.to]) { q.offer(e.to); inq[e.to] = true; if (++cnt[e.to] > n) return "负环"; }
        }
    }
}

#

★★

17. CLRS 第 25 章所有节点对最短路径的 Johnson 算法 vs Floyd-Warshall 的工程取舍？

问题

所有节点对最短路径，对比 Johnson 算法 vs Floyd-Warshall 的工程取舍？

考察点

Floyd-Warshall：O(V³) 动态规划
Johnson：重标定 + Dijkstra
复杂度与选型

答案

Floyd-Warshall：动态规划 dp[k][i][j] 表示经前 k 个节点的最短路径，三重循环 O(V³)，实现简单、适合稠密图（V 较小），能处理负权（无负环）。Johnson：① 加虚拟源点、用 Bellman-Ford 求每个节点的势能 h（重标定，消除负权）；② 用新权 w' = w + h[u] - h[v]（非负）跑 V 次 Dijkstra，最后还原。复杂度 O(V E log V)，适合稀疏图（E 小）。工程取舍：稠密图或 V 小用 Floyd-Warshall（实现简单、O(V³) 恒定）；稀疏图且 V 大用 Johnson（O(V E log V)，E 小则远优于 V³）。Johnson 能处理负权（重标定后 Dijkstra），Floyd 也能负权但无负环。选型看图密度与规模。

解析

Floyd 是"密度无关的 O(V³)"，Johnson 是"O(V E log V)"依赖 E。稠密图（E≈V²）两者都 O(V³)，Floyd 更简单；稀疏图 Johnson 的 E log V 远小于 V³。重标定（势能法）是 Johnson 消除负权、复用 Dijkstra 的关键。

示例代码

// Floyd-Warshall
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
    if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];

#

★★

18. 子集（LeetCode 78）与组合（LeetCode 77）中“选或不选”与“start 索引”两种回溯写法的等价性？

问题

子集与组合，说明"选或不选"与"start 索引"两种回溯写法的等价性？

考察点

选或不选：每个元素二分支
start 索引：按序枚举
两者等价

答案

子集（78）：两种写法。① 选或不选：对每个元素递归二分支（选进 or 不选），到达末尾时记录。② start 索引：从 start 开始枚举，每层选择当前元素并递归 start+1。组合（77）：从 start 枚举，选 k 个。等价性：子集的"每个元素要么选要么不选"本质上与"按 start 顺序枚举、每个元素作为某层的起点"产生的子集集合相同——因为每个子集对应一个唯一的"按升序选择"的 start 序列。"选或不选"是"每位独立决策"，"start 索引"是"按序枚举组合"，两者生成的子集/组合集合完全一致（去重后）。复杂度都 O(2^n)（子集）或 O(C(n,k))（组合）。

解析

"选或不选"是"位决策"视角（每个元素独立），"start 索引"是"组合枚举"视角（按序选择）。两者对同一问题的两种自然表述，结果幂等。理解等价性有助于灵活切换写法。

示例代码

// 子集：选或不选
void dfs(int i, int[] nums, List<Integer> cur) {
    if (i == nums.length) { res.add(new ArrayList<>(cur)); return; }
    dfs(i + 1, nums, cur);            // 不选
    cur.add(nums[i]); dfs(i + 1, nums, cur); cur.remove(cur.size() - 1); // 选
}
// 子集：start 索引
void dfs(int start, int[] nums, List<Integer> cur) {
    res.add(new ArrayList<>(cur));
    for (int i = start; i < nums.length; i++) { cur.add(nums[i]); dfs(i + 1, nums, cur); cur.remove(cur.size() - 1); }
}

#

★★

19. 腐烂的橘子（LeetCode 994）中多源 BFS 如何按层记录分钟数，最后如何检查是否还有新鲜橘子？

问题

腐烂的橘子，说明多源 BFS 如何按层记录分钟数，以及最后如何检查是否还有新鲜橘子？

考察点

多源 BFS（所有腐烂橘子同时入队）
按层记录分钟数
最后检查新鲜橘子

答案

腐烂的橘子：多源 BFS——把所有初始腐烂的橘子同时入队（作为起点），按层扩展，每层代表 1 分钟。BFS 时把相邻的新鲜橘子变腐烂并入队，记录层数（分钟数）。最后检查：遍历网格，若还有 '1'（新鲜橘子）未被感染，则返回 -1（无法全部腐烂）；否则返回分钟数（层数-1，因为初始腐烂是第 0 分钟）。多源 BFS 的关键是"所有源同时入队、按层扩展"，保证最短时间（所有腐烂同步扩散）。变量：用 queue 存腐烂位置，层循环用 size 分隔。

解析

多源 BFS 是"多源同时扩散"的最短时间模型，所有源统一入队后按层扩展。层数即分钟数。最后检查新鲜橘子决定是否 -1。这是"多源 BFS + 层计数"的经典题。

示例代码

int orangesRotting(int[][] grid) {
    Deque<int[]> q = new ArrayDeque<>();
    int fresh = 0;
    for (int i = 0; i < grid.length; i++) for (int j = 0; j < grid[0].length; j++) {
        if (grid[i][j] == 2) q.offer(new int[]{i, j});
        else if (grid[i][j] == 1) fresh++;
    }
    int minutes = 0;
    int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.isEmpty() && fresh > 0) {
        int size = q.size();
        for (int k = 0; k < size; k++) {
            int[] top = q.poll();
            for (int[] d : dir) {
                int ni = top[0] + d[0], nj = top[1] + d[1];
                if (ni >= 0 && nj >= 0 && ni < grid.length && nj < grid[0].length && grid[ni][nj] == 1) {
                    grid[ni][nj] = 2; fresh--; q.offer(new int[]{ni, nj});
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

#

★★

20. 单词搜索 II（LeetCode 212）中 Trie + 回溯如何共享前缀剪枝，与单词搜索（79）单次 DFS 的差异？

问题

单词搜索 II，说明 Trie + 回溯如何共享前缀剪枝，以及与单词搜索（79）单次 DFS 的差异？

考察点

Trie 存储所有单词
回溯时共享前缀剪枝
与单次 DFS 的差异

答案

单词搜索 II：把所有单词建成 Trie，DFS 网格时沿 Trie 的路径走，若当前字符不在 Trie 中则剪枝（无需继续）。这样多个单词共享前缀，一次 DFS 同时搜索所有单词。回溯时：从每个格子出发，匹配 Trie 前缀，到达单词终点则记录，继续探索更长的匹配。剪枝：① 当前字符不在 Trie 子节点则退回；② 找到单词后从 Trie 移除（避免重复）；③ 用已访问标记。与单词搜索（79）单次 DFS 的差异：79 只搜一个单词，每次 DFS 独立匹配；212 搜多个单词，用 Trie 共享前缀，一次遍历网格即可匹配所有单词，避免为每个单词单独 DFS。Trie 是"空间换时间"：共享前缀减少重复搜索。

解析

Trie 的核心优势是"前缀共享"：多个单词共享前缀，DFS 时一次走到共同前缀即可匹配所有共享该前缀的单词，避免逐词 DFS。这是"单词搜索"从单次到多词的最优解。

示例代码

// Trie 节点：children[26], word(终点存单词)
void dfs(char[][] b, int i, int j, TrieNode node, List<String> res) {
    if (i < 0 || j < 0 || i >= b.length || j >= b[0].length) return;
    char c = b[i][j];
    if (c == '#' || node.children[c - 'a'] == null) return; // 剪枝
    node = node.children[c - 'a'];
    if (node.word != null) { res.add(node.word); node.word = null; } // 去重
    b[i][j] = '#';
    dfs(b, i + 1, j, node, res); dfs(b, i - 1, j, node, res);
    dfs(b, i, j + 1, node, res); dfs(b, i, j - 1, node, res);
    b[i][j] = c;
}

#

★

21. DLX 在 dancing links X 算法的双向十字链表工程实现。

问题

说明 Dancing Links X（DLX）算法的双向十字链表工程实现？

考察点

精确覆盖问题
双向十字链表
覆盖与回溯

答案

DLX（Dancing Links X）解决精确覆盖问题（每列恰好被一个行覆盖）。工程实现用双向十字链表：每个节点有上、下、左、右四个指针，形成行循环链表与列循环链表；列头节点记录列信息。核心操作：① 覆盖某行——删除该行 row 覆盖的所有列（从列中移除该行节点），递归；② 回溯——逆操作恢复。用"dancing"（删除/恢复链表节点）实现高效的回溯，复杂度 O(精确覆盖问题规模)。工程要点：① 节点数组预分配；② 删除列时把该列所有行节点从行链中移除、把该列从列链中移除；③ 恢复按逆序。DLX 用于数独、N 皇后、集合覆盖等精确覆盖问题。

解析

DLX 是"精确覆盖回溯 + 双向链表快速删除恢复"的优化。双向链表使删除/恢复 O(1)（dancing），回溯时逆序恢复。这是"高效回溯"的工程实现，算法选最短列（MRV 启发式）加速。

示例代码

// 删除列 c：从列链移除，并移除该列所有行节点
void remove(int c) {
    L[R[c]] = L[c]; R[L[c]] = R[c];
    for (int i = D[c]; i != c; i = D[i]) for (int j = R[i]; j != i; j = R[j]) { U[D[j]] = U[j]; D[U[j]] = D[j]; }
}
// 恢复列：逆序
void restore(int c) {
    for (int i = U[c]; i != c; i = U[i]) for (int j = L[i]; j != i; j = L[j]) { U[D[j]] = j; D[U[j]] = j; }
    L[R[c]] = c; R[L[c]] = c;
}

#

★

22. Dancing Links（DLX）精确覆盖在数独、N 皇后、集合覆盖的工程实现。

问题

说明 Dancing Links（DLX）精确覆盖在数独、N 皇后、集合覆盖的工程实现？

考察点

精确覆盖建模
数独/皇后/集合覆盖的约束转矩阵
工程实现

答案

DLX 解决精确覆盖：把问题转化为"0-1 矩阵，选行使每列恰好被覆盖一次"。工程实现：① 数独：把每个格子"填某个数"建模为行，约束（每行每列每宫每格不重复）建模为列，选中填数行使所有约束列恰好覆盖一次；② N 皇后：每行放一个皇后 + 列/两对角线约束，建模为行（放置位置）与列（行/列/对角约束），选 N 个放置使每行每列每对角恰好覆盖；③ 集合覆盖：把每个元素建模为列，每个集合建模为行（覆盖其元素），选子集使每元素恰好覆盖一次。实现共用 DLX 框架：构建双向十字链表、递归选列（MRV 选最少候选列）、覆盖/回溯。DLX 比普通回溯快得多，适合约束密集的精确覆盖问题。

解析

DLX 的威力在于"精确覆盖"的统一建模：把业务约束（数独行宫格、皇后行列对角、集合元素）转成"列"，把候选解转成"行"，用 DLX 求解。掌握"约束→列、候选→行"的建模是关键，DLX 框架本身通用。

示例代码

// 数独 → 精确覆盖：每填数 (r,c,v) 为一行，覆盖 4 类约束列
// 1) 格 (r,c) 已填 2) 行 r 有 v 3) 列 c 有 v 4) 宫 block 有 v
// 用 DLX 选行使所有约束列恰好覆盖一次