| layout | page |
|---|---|
| title | 算法与数据结构 |
| permalink | /algorithms-data-structures/ |
这个栏目专门讲算法与数据结构。文章把问题模型、状态定义、不变量、正确性理由、复杂度和可复现实验连起来。每篇文章都说明算法为什么能停在正确答案上、哪些输入会触发边界情况、如何用测试确认实现没有偏离模型。
学习每篇文章时，依次完成下面七件事：
- 问题模型：输入、输出、约束和目标是什么。
- 核心不变量：循环或数据结构在每一步必须保持什么事实。
- 正确性理由：为什么不变量能推出最后答案。
- 复杂度分析：时间、空间，以及复杂度成立的前提。
- C++ 实现：给出可运行实现，避免只写伪代码。
- 测试与边界：固定边界、随机对照、异常输入或可视化 trace。
- 练习：用小改动检验理解。
下面按算法能力组织学习路线：
| 阶段 | 主题 | 已有文章 |
|---|---|---|
| 1. 边界和线性结构 | 二分、前缀和/差分、双指针、归并、单调栈 | 二分查找、前缀和与差分数组、双指针与滑动窗口、归并排序与逆序对、单调栈 |
| 2. 基础数据结构 | 堆/优先队列、哈希表、并查集、Fenwick 树、线段树 | 堆和优先队列、哈希表和哈希集合、并查集、Fenwick 树、线段树懒标记 |
| 3. 图算法 | BFS、DFS、二分图、最短路、生成树、最大流 | BFS 模板、DFS 模板、二分图染色、Dijkstra、最短路路径恢复、Bellman-Ford、最小生成树、Dinic 最大流 |
| 4. 动态规划和复杂度 | 基础 DP、背包、复杂度陷阱、边界测试 | 动态规划入门、基础 DP 题型、复杂度陷阱和边界测试 |
| 5. 字符串 | KMP、Trie/Aho-Corasick、后缀数组 | KMP、Trie 和 Aho-Corasick、后缀数组和 LCP |
| 6. 树上和持久化结构 | LCA、树链剖分、可持久化线段树、Li Chao 树 | 倍增 LCA、树链剖分、可持久化线段树、Li Chao 树 |
| 7. 数学、随机和博弈 | 数论、计算几何、NTT、摊还、随机化、SG | 数论工具箱、计算几何基础、NTT 卷积、摊还分析、随机化 Quickselect、Sprague-Grundy 定理 |
每个阶段完成后确认三件事：能说清核心不变量，能解释复杂度为什么成立，能用边界测试或随机对拍发现实现错误。做到这三点，再进入下一阶段。
{% assign posts = site.posts | where: "column", "algorithms-data-structures" %} {% if posts.size == 0 %} 当前没有匹配到本栏目文章。请先回到栏目地图或全部文章确认导航入口。 {% else %} {% for post in posts %}
- [{{ post.title }}]({{ post.url | relative_url }}) — {{ post.date | date: "%Y-%m-%d" }} {% endfor %} {% endif %}