用算法打败算法

经常有读者问我学算法有什么用，我觉得算法是一种抽象的思维能力。现实中的很多问题只要稍加抽象，就能联想到算法题中的编程技巧，然后得心应手地解决它们。

就比如说我的刷题三件套吧，从去年年底到目前已经有 20 多万次的下载：

这套 PDF 教程里不仅沉淀了我这些年学算法的心得体会，而且还把算法的思维运用到了制作过程中。本文简单介绍一下我制作教程以及插件时用到的算法，看看算法如何辅助大家更顺畅地学习。

计算相关文章/题目

我在前文 近期的大更新 说到了近期我对网站、PDF 以及插件功能的更新，其中有几个很实用的功能：

每篇文章的末尾添加了「相关文章」和「相关题目」的功能：

每道题目的解法思路底下也添加了「相关题目」的功能：

如果要实现上述这几个功能，我要维护三个映射：

1、文章到相关题目列表的映射。

2、文章到相关文章列表的映射。

3、题目到相关题目列表的映射。

我手动维护了一个文章到相关题目的映射：

Map<Article, List<Question>> map;

所以第 1 个功能可以直接实现，但其他两个功能怎么实现呢？

文章之间直接的引用肯定是一种相关关系，但如果多篇文章能够同时解决同一道题目，也可以说明这些文章之间存在相关关系。

因为我一般会在一篇文章里讲解多道题目，那么同一篇文章讲解的题目肯定有相关关系。同时，如果两篇文章相关，那么这两篇文章涉及的题目之间也应该是相关的。

想把上述思路写成代码，我们可以把上述的map转化成 图模型：

把「文章」和「题目」理解成一幅图中的两种节点，关联关系理解成图中的边，那么「文章」节点的相邻节点一定都是「题目」节点，「题目」节点的相邻节点一定都是「文章」节点，不可能有两个相同类型的节点相邻，这是一幅典型的二分图。

一旦把问题抽象成图模型，就可以运用所有图论算法，我随便举几个例子：

1、「文章」节点的邻居节点就是相关题目，「题目」节点的相邻节点就是能够解决该题目的文章，这是 二分图 的特性。

2、可以利用 Union Find 并查集算法 判断图中的两个节点是否连通。

具体来说，可以在 O(1) 时间判断两道题是否相关、两篇文章是否相关、某道题目和某篇文章是否相关。

3、可以把图中的某个节点作为起点执行 DFS/BFS 遍历算法，所有可达的节点即为相关节点，且距离越近，相关性越高。

具体来说，给一个「题目」节点，我用 DFS/BFS 算法计算所有可达的节点中的「题目」节点就是相关题目；类似的，「文章」节点周围所有可达节点中的「文章」节点就是相关文章。

这样，之前提出的三个相关关系的映射就能算出来了。

计算合理的目录顺序

很多读者反馈我的 PDF 教程的难度设计由浅入深，读起来酣畅淋漓，那是因为我在目录的设计上也使用了算法辅助，让学习曲线变得尽可能平滑。

首先，我给每道题目都打了 tag，这样只需把对应 tag 的题目丢到对应的章节里就行了。比如我可以把「基本二分搜索」「二分搜索运用」等多个 tag 的题目都丢到二分搜索的章节。

但是同一章节的题目难度也应该循序渐进。所以，我维护了题目之间的依赖关系，并根据这个依赖关系生成了一幅以题目为节点，依赖关系为边的 有向图，并在这幅有向图中进行了 环检测和拓扑排序算法，保证做每道题之前已经具备相关的前置知识。

接下来遇到一个新问题：

之前我的插件和 PDF 支持了 手把手刷《剑指 offer》的功能，所以算法笔记中包含很多《剑指 offer》的题目。

但《剑指 offer》的一些题目和力扣主站的题目有重复，力扣本身也有一些题目是重复的，所以现在需要对每个章节的题目进行去重。

由于章节中题目的顺序是经过拓扑排序的，所以我们希望去重时不改变题目之间的相对顺序。

我们可以用简单直接的方法，不过既然是一套算法教程，那当然要秀一下算法技巧喽。所以这里可以用前文 数组双指针技巧 中的快慢指针进行数组的原地去重。

另外，我希望《剑指 offer》的题目和原题有所区分，比如对于同一 tag 下的题目，让主站的题目排在前面，《剑指 offer》的题目排在后面。

类似去重需求，因为已经进行了拓扑排序，所以重排不应该不改变主站和剑指 offer 题目之间的相对顺序。

这里可以用前文 链表双指针技巧 讲到的分解链表的技巧，把剑指 offer的题目分解出来再合并到末尾：

到这里，题目的顺序就定下来了。但由于目录包含章节、小节、文章等多个层级，需要一个算法来为章节名、小节名、题目名生成正确的缩进。

实际上目录是一个树形结构，叶子节点是每道题目的内容和思路，非叶子结点是章节、小节的名称：

从树的角度来看，节点的层数可以区别章节、小节和题目，而且注意这棵树的前序遍历结果就是生成目录的顺序：

但既然咱学了这么久算法，直接用前序遍历就显得格局低了。这里可以使用前文 嵌套迭代器 的思路，用迭代器的形式遍历多叉树：

迭代器中的元素可能是一个单独的元素（题目），也可能是一个迭代器（章节、小节）。初始迭代器中只有 5 个元素（因为共有 5 个章节），然后迭代器可以自动处理和展开每个列表元素，进而生成完整的 PDF 目录。