跳转至

算法总览

算法面试的核心不是刷了多少题,而是有没有框架思维——能快速把陌生题归入已知套路,再用该套路的"标准动作"展开。本页是对 14 个套路节点的总览,解释它们从何而来、彼此如何联系、以及怎样用它们准备面试。

认识 14 个套路

它们从何而来

面试算法题看似千变万化,但按使用的数据结构 + 算法思想可以归为有限的几类。14 个套路节点就是把 LeetCode 上所有高频题按这个标准聚类得到的最小全集。

聚类依据 套路
线性遍历 + 原地操作 数组与字符串、双指针与滑动窗口
特殊线性结构 链表、栈与队列、哈希表
有序性上的查找优化 二分查找、排序与堆
树/图结构 二叉树、图论、字典树
穷举搜索 回溯、动态规划与贪心
位与数学技巧 位运算、数学

套路之间的依赖关系

一部分套路是另一部分套路的基础,认识这种依赖可以制订更合理的学习顺序:

先掌握:数组与字符串、链表、栈与队列、哈希表 —— 它们是最基础的数据结构,几乎所有题都会用到。

再学习:二叉树、双指针与滑动窗口、二分查找、排序与堆 —— 这些是基础结构上的"算法组合",面试高频区。

最后深入:回溯、动态规划与贪心、图论、字典树 —— 这些需要前序基础,也是区分面试水平的关键。

位运算与数学作为独立技巧穿插使用,不依赖前序套路。

从数组到一切

labuladong 的核心洞见:数据结构只有两种基本形态——数组(连续存储)和链表(链式存储),其余全是它们的封装或变种。

栈/队列 = 受限访问的链表或数组
二叉树 = 带有两个 next 指针的链表
图 = 允许有环且允许多父节点的二叉树
哈希表 = 数组 + 哈希函数(解决冲突用链表或树)
堆 = 用数组表示的完全二叉树
字典树 = 多叉树(用数组或哈希表存子节点指针)

理解了这条主线,遇到任何"偏门数据结构"都能快速把它拆回最基本形态来思考。

框架思维

遍历框架:所有算法题的出发点

labulaodng 认为,无论题目多复杂,最终代码形态不外乎两种:

线性遍历(for/while 循环):

// 数组遍历
for (int i = 0; i < arr.length; i++) { ... }

// 链表遍历
while (head != null) { ...; head = head.next; }

递归遍历(树/图/回溯/DP 的通用框架):

void traverse(TreeNode root) {
    // 前序:进入节点时
    traverse(root.left);
    // 中序:左子树返回后
    traverse(root.right);
    // 后序:右子树返回后
}

这个框架稍加变形就覆盖了绝大部分算法题型:

变体 做法
DFS/BFS 二叉树遍历加一个 visited 集合
回溯 前序做选择,后序撤销选择
动态规划 返回值变成子问题的解,加备忘录优化
图遍历 二叉树遍历加 visited 处理环

空间换时间

算法优化的本质几乎都是空间换时间:

  • 哈希表:用 O(n) 空间把查找从 O(n) 降到 O(1)
  • 前缀和:用 O(n) 空间把区间查询从 O(n) 降到 O(1)
  • 动态规划:用 O(n) 或 O(n²) 空间避免指数级重复计算
  • 堆:用 O(n) 空间把 TopK 的排序从 O(n log n) 降到 O(n log k)

面试时先写暴力解,然后问自己"这里能不能用空间换时间",往往就是最优解的入口。

刷题方法论

五步做题法(参考 labuladong 解法框架)

  1. 理解题目:用自己的话复述输入/输出/约束
  2. 举例子:画图推演小规模 case
  3. 暴力解:先写出能运行的版本,说复杂度
  4. 优化:用框架识别套路 → 套用该套路的标准解法
  5. 检查:边界条件(空/单个元素/全相同/极大值)

数据规模反推复杂度

数据规模 可接受复杂度 可能套路
n ≤ 20 O(2ⁿ) / O(n!) 回溯 + 剪枝
n ≤ 10³ O(n²) 双层循环 DP、暴力
n ≤ 10⁵ O(n log n) 排序、二分、分治
n ≤ 10⁶ O(n) 哈希、双指针、单调栈
n ≤ 10⁹ O(log n) 二分、快速幂、跳表

面试常见误区

  • 上来就写最优解(不给面试官递进空间):先讲暴力再优化
  • 不举例子:口头推演 edge case 比写代码更重要
  • 忽略边界条件:空输入 / 单元素 / 溢出
  • 不分析复杂度:必须说时间 + 空间
  • 写出来就不管了:跑个例子验证一遍

BFS vs DFS：一张决策卡

树和图的题，拿到手先自问：答案以什么为单位？ 单位决定遍历方式——这是比"感觉"可靠得多的判断法。

答案的单位 用谁 一句话理由
子树 / 路径 / 结构（深度、平衡、祖先、路径总和） DFS（递归） 递归定义就是"对子树提问"，DFS 把它直译成代码
层（层序、右视图、每层均值/最大、宽度） BFS（队列） 层是 BFS 的天然单位，递归拿不到"同一层"的分组
最短 / 最少步数 / 最先到 BFS 一圈圈扩散，第一次到达即最短；DFS 必须走完全部再取 min
过程本身是答案（所有路径、全排列、回溯） 必须 DFS BFS 的队列会丢掉"怎么走到这里"的过程
同位配对、各位置独立（合并两树、对称） 两者皆可 顺序不影响结果，选写得短的那个
连通性 / 可达性（图上的岛屿、能否到达） 通常 DFS 不关心步数，只关心"到得了"

两个反直觉的锚点：

  • "最短用 BFS"和"最长用 DFS"互为镜像：最小深度（111）用 BFS 可以在第一个叶子处早停；最大深度（104）反正要走完全部，DFS 的 1+max(l,r) 反而最短。
  • 树宽而浅时 BFS 空间大，树斜而深时 DFS 栈深大：最坏都是 O(n)，但形状相反——完美树 BFS 到 O(n/2)，链状树 DFS 也是 O(n)。

图上差别更硬：无权图的最短路径 BFS 独占（二叉树没有环，DFS/BFS 结果相同只是顺序不同；图有环，顺序就影响正确性了）。

具体到二叉树各题的归位，见二叉树的"BFS/DFS 分型表"。

推荐学习路径

具体怎么刷 —— 按什么顺序、每章刷哪些跳哪些、刷几遍、几周刷完 —— 单独成篇：刷题方案。

两页的分工：本页讲"这些套路是什么、为什么这么分类"（概念），刷题方案讲"按什么顺序把它们刷完"（执行）。

一刷和二刷的方法不一样,别用错:上面的「五步做题法」和"卡住 15 分钟再看答案"适用于二刷及以后; 一刷阶段按刷题方案的"直接看答案 → 立刻关掉默写"来 —— 一刷的目标是快速建立模式识别,不是练思考能力。

参考资源