算法篇：从思想到题型实践
先建立算法学习路线，覆盖复杂度、递归、二分、双指针、滑动窗口、排序、回溯、字符串、动态规划、贪心与图算法。
文章目录
知识目录数据结构与算法：从基础到工程实践5 / 77
我最开始接触“算法篇：从思想到题型实践”时，先遇到的是这个问题：我把二分、回溯、动态规划分别背成了几套模板，题目稍微换一种问法就不知道该套哪一个。我没有继续硬记结论，而是把过程画出来，再用一两个最小例子亲手跑通。这篇留下的，就是那次重新梳理后真正帮我想明白的东西。
算法篇解决的问题是：面对一个具体任务，应该用什么步骤，在可接受的时间和空间内得到正确答案。
如果数据结构是“状态如何组织”，算法就是“状态如何变化”。很多算法看起来像模板，其实背后都有共同的思维：缩小搜索范围、复用历史结果、维护单调性、拆分问题、剪枝无效路径、选择局部最优、在图上扩散状态。
这一篇先作为算法篇总览，不急着写完所有细节。后续每个方向会拆成独立文章，配图、代码、复杂度、场景和面试题。
我后来补上的前置基础
算法不是从动态规划开始的，也不是从刷题数量开始的。
更稳的前置基础是：
- 会分析时间复杂度和空间复杂度。
- 理解递归调用栈。
- 熟悉数组、链表、栈、队列、哈希表、树、图这些基础结构。
- 能写清楚边界条件。
- 能用测试样例证明自己的理解。
很多算法题做不出来，不是因为缺一个神奇模板，而是因为没有先把状态、边界和数据结构关系想清楚。
第一组：边界移动类算法
这一组最常出现在数组和字符串里。
二分查找
二分的本质不是“在有序数组里找数”这么窄，而是不断缩小答案区间。
常见类型：
- 查找某个目标值。
- 查找左边界或右边界。
- 查找第一个满足条件的位置。
- 答案二分，例如最小可行速度、最大可行容量。
二分最容易错在：
- 区间定义不清楚。
left、right更新后没有收敛。mid计算溢出。- 返回值到底是
left还是right没想明白。
双指针
双指针用两个位置描述当前处理范围。
常见类型：
- 相向双指针：两数之和、反转数组、回文判断。
- 同向双指针：原地去重、快慢指针。
- 快慢指针：链表环检测、找中点。
双指针的关键不是指针数量，而是每次移动哪个指针，以及为什么不会漏答案。
滑动窗口
滑动窗口是双指针的一种常见形式，用于维护一个连续区间。
典型问题：
- 最长无重复子串。
- 最小覆盖子串。
- 固定长度窗口最大值。
- 满足某个条件的最长/最短区间。
滑动窗口最重要的是两个判断：
什么时候扩大窗口？
什么时候收缩窗口？
如果这两个条件没写清楚，代码看起来像模板，实际很容易错。
第二组：预处理与差量维护
前缀和
前缀和把重复区间求和变成一次预处理和 O(1) 查询。
核心公式：
sum(l, r) = prefix[r + 1] - prefix[l]
它适合频繁查询区间和，但不适合频繁单点修改或区间修改。
差分数组
差分数组把区间修改变成两个端点变化。
对区间 [l, r] 加 delta：
diff[l] += delta
diff[r + 1] -= delta
最后再通过前缀和还原数组。
它适合“多次区间修改，最后统一查询结果”的场景。
第三组：排序与分治
排序不是为了背十几个算法，而是理解比较、交换、分区、合并和稳定性。
需要掌握：
- 冒泡、选择、插入：用于理解基础交换和局部有序。
- 快速排序：理解分区、随机化和最坏情况。
- 归并排序：理解分治、合并和稳定性。
- 堆排序：理解堆不变量和原地排序。
- 计数、桶、基数排序：理解非比较排序的适用条件。
排序算法要比较：
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(k) | 可稳定 |
我的判断是：排序的重点不是“哪个最快”，而是输入规模、数据分布、稳定性、额外空间和工程库实现。
第四组：搜索与回溯
搜索是在状态空间中找答案。
DFS 更适合沿一条路径深入；BFS 更适合按层扩散；回溯则是在 DFS 基础上加入选择、撤销和剪枝。
回溯常见结构：
选择一个候选
↓
进入下一层
↓
如果不合适就回退
↓
撤销选择
典型问题：
- 子集
- 组合
- 排列
- N 皇后
- 括号生成
- 单词搜索
- 岛屿数量
回溯不是暴力的代名词，它的关键是剪枝。真正好的回溯代码应该能说明：哪些分支没有必要继续走。
第五组：字符串算法
字符串算法现在分成基础和进阶两层：基础先理解暴力匹配、KMP 和哈希；进阶再进入 AC 自动机、Manacher、Z 函数和后缀数组。
需要覆盖：
- 暴力匹配。
- Rabin-Karp 与滚动哈希。
- 字符串哈希和冲突处理。
- KMP 与前缀函数。
- Z 函数。
- Manacher 回文算法。
- Trie 与 AC 自动机。
- 后缀数组入门。
字符串算法最容易画错图，所以阅读时要重点观察：
- 模式串和文本串上下对齐。
- 失配跳转方向清晰。
- 前缀、后缀、公共前缀不要混用。
- 自动机失败指针不能和 Trie 边混在一起。
第六组：动态规划
动态规划不是背公式，而是设计状态。
一篇 DP 文章必须回答：
- 状态是什么？
- 选择是什么？
- 转移从哪里来？
- base case 是什么？
- 遍历顺序为什么这样？
- 是否可以空间压缩？
常见类型：
- 线性 DP：爬楼梯、打家劫舍、最大子数组。
- 子序列 DP：LIS、LCS。
- 背包 DP：0-1 背包、完全背包、多重背包。
- 区间 DP：合并石子、回文区间。
- 树形 DP：树上选择和路径状态。
- 状态压缩 DP：集合状态和位掩码。
- 编辑距离：插入、删除、替换。
DP 的图解重点应该是状态表填充方向。读者要能看出来每个格子依赖哪些格子，而不是只看到一个公式。
第七组：贪心
贪心的难点不是写代码，而是证明为什么局部选择不会破坏全局最优。
适合贪心的题通常有：
- 区间调度。
- 跳跃游戏。
- 分发糖果。
- 最少箭射气球。
- 合并区间。
- Huffman 编码。
贪心最危险的地方是：样例能过，不代表策略正确。后续写贪心文章时，必须加入反例和证明思路。
第八组：图算法
图算法依赖图结构，但它的重点是求解问题。
需要独立成文：
- DFS 与 BFS 框架。
- 拓扑排序与有向图判环。
- Dijkstra 非负权最短路。
- Bellman-Ford 与负权边。
- Floyd 多源最短路。
- Prim 与 Kruskal 最小生成树。
- 二分图判断。
- 强连通分量。
- 网络流入门。
图算法的第一步永远是建模。边方向、权重含义、重复边、自环、稀疏/稠密程度，都会影响算法选择。
第九组：工程算法与海量数据
算法学到最后，要能回到真实系统里。很多工程问题不是单纯刷题，但背后仍然是数据结构与算法组合。
需要掌握：
- Top K 海量数据：分桶、哈希统计、小顶堆。
- 海量去重：Bitmap、Bloom Filter、分治分桶。
- 外部排序：分块排序、多路归并。
- 倒排索引：从词找到文档，是搜索系统的核心。
- 一致性哈希：节点扩缩容时减少数据迁移。
- LRU：哈希表和双向链表组合维护缓存淘汰。
这一组的重点不是手写多复杂的代码，而是学会问约束：内存够不够、结果是否必须精确、是否需要实时、是否需要排序、能不能接受误判。
算法篇的学习顺序
推荐路线：
复杂度、递归
↓
二分、双指针、滑动窗口
↓
前缀和、差分
↓
排序、分治
↓
搜索、回溯
↓
树算法、图算法
↓
字符串算法
↓
动态规划
↓
贪心、图论进阶
↓
海量数据、倒排索引、工程迁移
这不是唯一顺序，但它比较适合从“理解原理”走向“能做题、能解释、能应用”。
我后来这样检查自己是否真的理解
- 二分查找的区间到底是左闭右闭，还是左闭右开？
- 双指针为什么移动一个指针不会漏掉答案？
- 滑动窗口什么时候扩大，什么时候收缩？
- 前缀和适合什么查询，不适合什么修改？
- 快速排序为什么平均快，但最坏可能退化？
- 回溯为什么要撤销选择？
- 动态规划和记忆化搜索是什么关系？
- KMP 的 next 数组到底保存什么？
- Dijkstra 为什么要求边权非负？
- 贪心算法为什么必须证明正确性？
- AC 自动机为什么适合多模式匹配？
- 海量数据题为什么不能只回答 HashMap？
有哪里没看懂？可以只问这篇。
Jarvis 会限定在《算法篇：从思想到题型实践》及其公开关联内容中检索，并把引用定位回原文章节。