Interview Wiki

算法题索引

40分钟阅读

本页由 scripts/gen_topics.py 生成，勿手编。 改题解的 topics:/techniques:/元数据行后跑一次脚本即可。

结构:套路(为什么这些题是同一类) → 题目(技术词以标签形式标注)。一题可以横跨多个套路(如「接雨水」同时是数组、双指针、单调栈),各处指向的是同一份物理题解。

频次:★★★★★ 几乎必考 / ★★★★ 高频 / ★★★ 常见 / ★★ 偶考。难度:🟢 易 / 🟡 中 / 🔴 难。 难度/频次/公司以题解元数据行为权威源,本页是它的视图。公司标注为大致倾向,以实际面试为准。

相关:高频题目索引(按热度排序,跨套路)。 总览:算法总览(框架思维 + 方法论)。 路线:刷题方案(两阶段打法:随想录筑基 → Hot100 验收,每章标了刷哪些跳哪些)。

怎么用这份索引

  1. 按套路刷,不按题号刷。每个套路先做代表题建立模式,再横向扩展变式——套路页里「为什么这些题是同一个套路」才是主线。
  2. 技术词以标签形式标注在题目行尾(如 #对撞指针),同一个套路下的技术词彼此不可替代,搞混了就会硬套模板。
  3. 高频题(★★★★★)优先,见 高频算法题 Top 40。
  4. 每题留 Java 解 + 复杂度 + 一句变式;难题写关联题互链,## 关联题 是知识图谱的边。
  5. 不知道从哪开始就别自己排顺序,照 刷题方案 走:一阶段按随想录顺序筑基 94 题(每章标了必刷/跳过),二阶段用 Hot100 验收。本页是「按套路查题」的视图,那页是「按什么顺序刷完」的执行手册。

套路速查

共 14 个套路、265 篇题解。

套路题数
数组与字符串42
链表22
栈与队列13
哈希表13
双指针与滑动窗口13
二分查找11
二叉树39
图论22
回溯17
动态规划与贪心61
排序与堆12
字典树6
位运算6
数学4

数组与字符串

数组题的大部分”技巧”其实只有两类——用下标/原地交换省掉额外空间，或者用一次预处理把重复计算的区间查询/更新降到 O(1)。认出属于哪一类，思路就定了一半。

详解见 数组与字符串。

链表

链表题几乎都是指针操作的模式化组合，真正的武器只有两件——虚拟头节点（dummy）消灭”头节点要不要特判”的分支，和快慢指针。认出该用哪件武器，代码本身反而是最不费脑子的部分。

详解见 链表。

栈与队列

栈解决”最近的还没处理完”（括号匹配、表达式求值、函数调用），队列解决”先来的先处理”（层序遍历、BFS）。单调栈/单调队列是在此之上加了一条淘汰规则——不是谁都留在栈/队列里，而是只留下”未来还可能有用”的那些。

详解见 栈与队列。

哈希表

哈希表把”这个东西之前见过吗/出现过几次/对应什么”这类查询降到 O(1)。凡是暴力解法里有一层”遍历前面所有元素，看有没有满足条件的”，几乎都能用哈希表把那层遍历换成一次查表。

详解见 哈希表。

双指针与滑动窗口

两个指针能把很多 O(n²) 的暴力枚举降到 O(n)，前提是移动指针时能保证不会漏掉正确答案——这个前提是否成立，取决于指针是”对撞”还是”同向”，而滑动窗口只是”同向双指针”的一种特殊形态。

详解见 双指针与滑动窗口。

二分查找

二分查找的必要条件不是”数组有序”，而是**“答案空间上存在一个单调的判定条件”**——能把问题转化成”在一段区间里找到条件由假变真的那个分界点”，就能二分，哪怕数组本身看起来是”无序”的。

详解见 二分查找。

二叉树

几乎所有二叉树题都能套进同一个框架——“整棵树的答案 = 用根节点的信息，组合左右子树各自的答案”。想清楚”子树需要返回什么信息给父节点”，代码基本就写出来了；唯一的例外是层序遍历，它天生是迭代（BFS）而非递归的活。

详解见 二叉树。

图论

图是”允许有环、允许多个父节点”的树，所以树的 DFS/BFS 在图上全部适用，只是多了一件必须做的事——记录访问过的节点，否则会在环里死循环。图论题的额外技巧（拓扑排序、并查集）都是为了处理树没有的两个新问题：依赖顺序和动态连通性。

详解见 图论。

回溯

回溯就是 DFS 加上一句”撤销现场”——穷举所有可能解的通用框架是「做选择 → 递归进入下一层 → 撤销选择」，三步缺一不可。写不出撤销那一步，是这类题最常见的翻车原因。

详解见 回溯。

动态规划与贪心

动态规划和贪心都是”不穷举所有解，靠某个性质剪掉大部分选择”，区别在于动态规划把每一步的所有候选都存下来供后面复用，贪心直接证明”每一步只保留一个候选就够了”。判断一道题该用哪个，比写出代码本身更考验功力，也是这一页真正的价值所在。

详解见 动态规划与贪心。

排序与堆

需要”全部有序”就用排序；只需要”前 K 个”或”动态维护当前最值”，用堆——堆的本质是一棵只保证”父节点比子节点更优”、不要求兄弟节点之间有序的弱化二叉树，正是这个弱化换来了 O(log n) 的插入/取出，比维护整体有序便宜得多。

详解见 排序与堆。

字典树

字典树（Trie）是”用公共前缀换空间和查询效率”的哈希表替代品——当查询模式是”前缀匹配”而不是”精确匹配”时，哈希表无能为力（它只能判断整个字符串是否存在），字典树天然适合。

详解见 字典树。

位运算

位运算题的价值几乎都来自异或（XOR）的两条性质——自反性（a^a=0）让”找落单元素”不需要额外空间，无进位加法的特性让它能模拟加法。认出题目在利用哪一条，解法基本就出来了。

详解见 位运算。

数学

数学题在算法面试中的考察点往往不是高深的数论，而是如何把现实问题抽象成数学模型，再用程序表达——拒绝采样、概率均等、模运算性质是最高频的三个工具。

详解见 数学。

关系图谱

反向链接