算法刷题系列路线图：从基础结构到动态规划与图论

算法刷题系列路线图：从基础结构到动态规划与图论

算法题目看起来很多，解法却常常建立在少数几种结构和思维方式上。这个系列把一组常见刷题主题重新编排成一条由浅入深的路线：先学会读题和模拟，再掌握线性数据结构与序列技巧，随后进入搜索、树、图、区间结构和动态规划。

本路线不是按题目难度从易到难的排行榜。学习时应先理解“为什么这种状态或结构能解决问题”，再做题验证；如果某一模块的前置概念还不稳，可以先回到前面的模块练习。

系列目标

完成系列后，希望读者能够：

• 将自然语言题意转成输入、状态、操作和输出。
• 根据数据规模估算时间与空间复杂度，排除明显不可行的做法。
• 识别数组、字符串、树、图等问题背后的常见结构。
• 解释所选算法为什么正确，而不只是记住一段模板代码。
• 用 Java 和 Python 分别实现核心思路，并通过边界用例验证。

系列篇次与依赖关系

主线包含 56 篇，并根据目录中的旧笔记扩展出 10 篇基础与应用专题，共 66 篇。主线按“状态建模 → 常用结构 → 搜索与递归 → 图模型 → 区间结构 → 动态规划”组织；补充篇回收复杂度、线性表、查找树、表达式、树编码与经典题型。每篇的“承接”说明建议先掌握的前置概念；可以跳读，但遇到术语不熟时应回到对应篇次。

第一阶段：先把题意变成可执行的算法

这一阶段建立解题的共同语言：状态是什么、如何记录信息、如何缩小候选。

1. 模拟法：从题意到状态更新（已完成草稿）——定义状态，逐条执行规则，先建立正确基线。
2. 哈希表：用空间换查找（已完成草稿）——将历史扫描变成键值查询；承接模拟中的重复查找。
3. 排序：把无序问题变成有序结构（已完成草稿）——学习比较规则、稳定性和排序后可利用的性质；承接数组与查找。
4. 数学：用数与不变量缩小问题（已完成草稿）——整理取模、最大公约数、计数和简单数论；承接复杂度与边界分析。
5. 位运算：用二进制表达状态（已完成草稿）——理解掩码、异或、置位和清位；为子集枚举和状压 DP 做准备。
6. 二进制枚举：遍历小规模集合的所有子集（已完成草稿）——将位掩码映射为选择状态；承接位运算。
7. 打表：预计算换取查询效率（已完成草稿）——识别有限状态空间与重复查询；对比记忆化搜索，明确空间与初始化代价。
8. 表达式计算：从符号串到运算结果（已完成草稿）——处理括号、优先级和操作数；连接栈、递归解析与状态维护。

阶段检查：能为一个新题写出状态定义、操作顺序、终止条件和边界样例。

第二阶段：掌握线性结构与序列技巧

这一阶段从数据组织方式出发，逐步学习扫描、区间统计和字符串处理。

1. 栈：处理后进先出的状态（已完成草稿）——掌握入栈/出栈不变量；为括号、单调栈和表达式计算打基础。
2. 队列：按到达顺序处理任务（已完成草稿）——理解先进先出；为 BFS 和滑动窗口队列打基础。
3. 链表：处理节点引用与局部重连（已完成草稿）——掌握虚拟头节点、删除和反转；对比数组的随机访问。
4. 双指针：让两个位置协同移动（已完成草稿）——根据有序性或区间约束减少重复扫描；承接排序。
5. N 数之和：组合哈希与双指针（已完成草稿）——从两数之和推广到多元素组合，并正确去重；承接哈希表、排序和双指针。
6. 移除元素：用读写指针原地筛选（已完成草稿）——维护有效前缀，理解覆盖顺序和返回长度；承接双指针。
7. 前缀和：把区间和变成前缀差（已完成草稿）——支持静态区间查询；承接数组遍历和哈希计数。
8. 差分：把区间修改变成边界变化（已完成草稿）——用差分数组处理批量区间更新；承接前缀和的逆向关系。
9. 滑动窗口：维护满足条件的连续区间（已完成草稿）——学习窗口不变量和左右边界的单调移动；承接双指针、前缀和。
10. 回文串问题：利用对称性减少比较（已完成草稿）——从中心扩展到字符串区间判断；承接双指针和字符串索引。
11. 括号问题：用栈和前缀约束检查合法性（已完成草稿）——区分匹配、最长有效段和多类型括号；承接栈。
12. 子串匹配：在文本中高效寻找模式（已完成草稿）——理解朴素匹配与利用已知前缀信息的优化；承接字符串与前缀思想。
13. 字典树：按公共前缀组织字符串（已完成草稿）——支持前缀查询、插入和搜索；承接哈希表，同时比较空间取舍。

阶段检查：能够解释每种结构维持的不变量，并说明它解决了哪类重复工作。

第三阶段：搜索、候选维护与贪心

这一阶段学习如何利用单调性缩小范围、维护动态候选，以及证明局部策略可行。

1. 二分查找：在单调条件中定位边界（已完成草稿）——明确闭区间/半开区间、循环不变量和边界返回；承接排序。
2. 三分搜索：在单峰函数中定位极值（已完成草稿）——说明单峰前提与精度/整数域处理；承接二分的区间收缩思想。
3. 堆：动态维护最值与 Top-K（已完成草稿）——理解优先队列操作和复杂度；承接排序、队列。
4. 多路归并：用小顶堆合并多个有序流（已完成草稿）——每次只维护各路当前候选；承接堆和排序。
5. 贪心算法：从局部选择到正确性证明（已完成草稿）——用交换论证、反证或不变量验证策略；承接排序、堆和区间思维。

阶段检查（已完成草稿）：二分能说清单调条件，贪心能给出证明而非只凭样例。

第四阶段：树、递归与组合搜索

树结构、遍历和回溯共享递归思维；本阶段从树的定义推进到一般搜索。

1. 二叉树：从节点关系建立递归模型（已完成草稿）——理解左右子树、空节点和递归返回值。
2. 树的搜索：前序、中序、后序与层序（已完成草稿）——依据问题选择遍历顺序；承接二叉树与栈/队列。
3. DFS：沿路径深入并维护访问状态（已完成草稿）——区分树递归与图搜索中的 visited；承接树的递归遍历。
4. BFS：按层扩展状态空间（已完成草稿）——用队列处理无权最短步数；承接队列和树的层序遍历。
5. 回溯算法：做选择、递归、撤销选择（已完成草稿）——定义路径、候选集和剪枝条件；承接 DFS。
6. 组合总和：在回溯中处理复用与去重（已完成草稿）——通过起始下标和排序剪枝控制组合枚举；承接回溯、排序。
7. 数独问题：把约束满足转成搜索（已完成草稿）——用行、列、宫约束剪枝；承接回溯与位掩码。
8. 分治：拆分子问题并合并结果（已完成草稿）——明确子问题规模、独立性和合并过程；承接递归。
9. 启发式搜索：用估价信息引导探索（已完成草稿）——讨论搜索策略、启发函数和最优性前提；承接 BFS/DFS 与状态建模。

阶段检查（已完成草稿）：能明确搜索状态、选择集合、终止条件、剪枝条件和回退动作。

第五阶段：把关系建模为图

树可以看作特殊图。本阶段从连通性和图遍历开始，再处理依赖、连通网络和最短路径。

1. 并查集：维护动态连通分量（已完成草稿）——用路径压缩与按秩合并回答连通性；承接树形结构。
2. 图论 BFS：在无权图中求最少边数（已完成草稿）——把普通 BFS 推广到邻接表和多源起点；承接队列、BFS。
3. 图论 DFS：遍历连通分量和结构（已完成草稿）——处理访问标记、环检测和连通块；承接 DFS。
4. 拓扑排序：安排有向无环图的依赖顺序（已完成草稿）——用入度队列或 DFS 序检测有向环；承接图遍历和队列。
5. 最小生成树：用最低代价连接所有顶点（已完成草稿）——比较 Kruskal 与 Prim，并说明何时使用并查集/堆；承接排序、并查集和堆。
6. 最短路：按边权条件选择算法（已完成草稿）——区分无权、非负权和含负权场景，避免算法误用；承接图 BFS、堆和松弛思想。

阶段检查（已完成草稿）：给定一张图，能说明它有向/无向、带权/无权、是否可能有环，并据此选算法。

第六阶段：用专门结构处理区间与事件

当前缀统计和普通扫描不足以应付频繁查询时，引入维护候选或区间信息的数据结构。

1. 单调栈：维护最近的更大/更小候选（已完成草稿）——理解弹出条件和每个元素至多入栈/出栈一次；承接栈与排序。
2. 单调队列：维护滑动区间中的极值（已完成草稿）——按索引过期并维护单调性；承接队列、滑动窗口。
3. 树状数组：维护前缀聚合与单点更新（已完成草稿）——掌握 lowbit、下标转换及区间查询；承接前缀和、差分。
4. 线段树：维护区间查询与更新（已完成草稿）——定义节点信息、合并规则和懒标记；承接树状数组与分治。
5. 扫描线：按事件顺序维护动态状态（已完成草稿）——把几何或区间问题转成排序后的事件处理；承接排序、堆、线段树。

阶段检查（已完成草稿）：能写清数据结构保存的摘要信息、更新规则、查询规则和单次复杂度。

第七阶段：动态规划与状态压缩

最后把“搜索状态”升级为可复用的子问题结果，逐步覆盖一维、序列、区间和高维状态。

1. 记忆化搜索：缓存重复递归状态（已完成草稿）——从搜索树中识别重叠子问题；承接 DFS、回溯。
2. 线性 DP：从前缀状态递推当前位置（已完成草稿）——明确状态定义、初始化、转移和遍历顺序；承接记忆化搜索。
3. 序列 DP：描述序列之间的选择关系（已完成草稿）——处理子序列、最长上升子序列或两个序列的匹配；承接线性 DP。
4. 背包 DP：在容量约束下做选择（已完成草稿）——区分 0/1、完全和多重背包，并说明循环方向；承接线性 DP。
5. 状态机 DP：用有限状态表达阶段变化（已完成草稿）——把持有/未持有等状态及合法转移显式化；承接序列 DP、背包思维。
6. 区间 DP：按区间长度逐步合并子问题（已完成草稿）——枚举分割点或最后操作；承接分治与线性 DP。
7. 数位 DP：按数字位统计受上界约束的方案（已完成草稿）——处理前导零、上界标记和限制状态；承接状态 DP 与记忆化搜索。
8. 状压 DP：用位掩码表示集合状态（已完成草稿）——将小规模集合的选择与 DP 结合；承接位运算、二进制枚举、背包 DP。
9. 博弈论：从可达后继判断胜负状态（已完成草稿）——建立必胜/必败状态和转移；承接状态 DP 与图搜索。
10. 矩阵快速幂：加速线性递推的多步转移（已完成草稿）——把状态转移写成矩阵并用快速幂处理大步数；承接线性 DP、矩阵乘法。

阶段检查与系列目标（已完成草稿）：能够从暴力递归识别重叠子问题，定义状态、写出转移，并以初始化、遍历顺序和复杂度分析验证设计。

补充专题：回收旧笔记并贯通经典应用

以下篇目将目录中的零散基础笔记、旧题记录和图示扩展为可独立学习的原创教程。它们补充主线概念，不改变前 56 篇的学习顺序。

1. 算法复杂度与数据结构：如何衡量和组织（已完成草稿）——整理算法定义、时间/空间复杂度及逻辑结构与存储结构的关系；承接全系列。
2. 线性表：数组与链表如何选择（已完成草稿）——比较顺序存储和链式存储的访问、插入、删除成本；承接第 11 篇。
3. 二叉搜索树：查找、插入与删除（已完成草稿）——补全 BST 的操作、删除三种情况和高度退化问题；承接第 27–28 篇。
4. 平衡搜索树：从 AVL 到 B 树与 B+ 树（已完成草稿）——理解旋转、多路分支和外存索引的设计目标；承接第 24、59 篇。
5. 最大子数组和：从枚举到 Kadane 算法（已完成草稿）——把最大子列和推导为线性 DP，并恢复区间边界；承接第 15、48 篇。
6. 二叉树序列化：用遍历结果保存结构（已完成草稿）——使用空节点标记实现可逆编码，验证损坏输入；承接第 10、27–28 篇。
7. 滑动窗口三道题：从定长统计到动态维护（已完成草稿）——整合最大平均数、可挽回收益和有限值域次序统计；承接第 17、43 篇。
8. 二进制子串覆盖：滚动位掩码与可行性判断（已完成草稿）——结合固定窗口与位掩码枚举状态；承接第 5–6、17 篇。
9. 中缀、前缀与后缀表达式：转换和求值（已完成草稿）——用运算符栈转换中缀表达式并用操作数栈求值；承接第 8–9 篇。
10. 哈夫曼树：用贪心构造最优前缀码（已完成草稿）——用最小堆合并低频节点，连接堆、贪心与树遍历；承接第 24、26、28 篇。

目录中的 epoll 笔记讨论 Linux I/O 多路复用，属于操作系统专题而非算法刷题主线；保留为独立笔记，不将其内容改写或并入本系列。

当前进度

篇次	主题	状态
1–3	模拟法、哈希表、排序	草稿已完成
4–8	数学、位运算、二进制枚举、打表、表达式计算	草稿已完成
9–21	线性结构、序列技巧与字符串	草稿已完成
22–26	二分、三分、堆、多路归并与贪心	草稿已完成
27–35	树、遍历、搜索、回溯、分治与启发式搜索	草稿已完成
36–41	并查集、图遍历、拓扑排序、生成树与最短路	草稿已完成
42–46	单调结构、树状数组、线段树与扫描线	草稿已完成
47–56	记忆化搜索、动态规划、博弈与矩阵快速幂	草稿已完成
57–66	复杂度与数据结构基础、经典树专题、DP/窗口/表达式应用	草稿已完成

66 篇教程均已完成初稿，接下来进入全系列的统一优化与逐篇校订阶段。

篇次按学习依赖组织，不要求按日历连续发布。每篇正式发布前都应独立验证示例代码，并按统一文章结构补足推导、复杂度、测试和易错点。

每篇文章的统一结构

为了让系列不变成“代码合集”，每篇教程尽量按同一条推理路径展开：

1. 问题信号：题目出现哪些特征时可以考虑该方法。
2. 朴素做法：先建立正确但可能低效的基线。
3. 关键观察：指出重复工作、可维护的不变量或状态关系。
4. 算法推导：说明如何从观察得到解法，并解释正确性。
5. Java 与 Python 实现：保持两种语言的变量含义和边界处理一致。
6. 复杂度分析：明确时间复杂度、额外空间和适用前提。
7. 边界测试：覆盖空输入、单元素、重复值、最大规模等相关情况。
8. 易错点与相邻题型：帮助读者决定下一步练习什么。

选题与版权说明

本系列的主题清单参考本地资料目录中可见的算法主题名称；文章正文、例题、推导和代码将独立撰写，不转录或改写源 PDF 的正文。源资料及其原文权利归原作者或相应版权方所有；本系列不表示获得原文转载授权。

从哪里开始

建议按模块顺序学习。本文之后先从“模拟”开始，因为它能训练把题意拆成状态和操作；有了这个习惯，再学习哈希、指针、搜索和动态规划时，会更容易解释算法为什么正确。