算法总览

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

认识 13 个套路

它们从何而来

面试算法题看似千变万化,但按使用的数据结构 + 算法思想可以归为有限的几类。13 个套路节点就是把 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 解法框架)

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

数据规模反推复杂度

数据规模	可接受复杂度	可能套路
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 比写代码更重要
忽略边界条件:空输入 / 单元素 / 溢出
不分析复杂度:必须说时间 + 空间
写出来就不管了:跑个例子验证一遍

轮次	目标	套路
第一轮	建立基础	数组与字符串、链表、栈与队列、哈希表
第二轮	高频必会	二叉树、双指针与滑动窗口、二分查找、排序与堆
第三轮	突破进阶	回溯、动态规划与贪心、图论
补充	专项补全	字典树、位运算、数学

参考资源

labuladong 的算法小抄 — 框架思维集大成者,每个套路都有”模板代码”
LeetCode 官方题解 — 多语言对比,关注 Follow-up
Hello 算法 — 图解数据结构与算法,零基础友好
OI Wiki — 概念查缺补漏(偏竞赛,面试够用即可)

Interview Wiki

探索