领悟 DSA

荒流2024年5月19日大约 14 分钟约 4051 字

参考 labuladong 的算法笔记。

1. DS 的存储方式

数据结构的存储方式只有两种：

数组（顺序存储）
链表（链式存储）

对于散列表、栈、队列、堆、树、图等等各种数据结构，都属于「上层建筑」，而数组和链表才是「结构基础」。因为那些多样化的数据结构，究其源头，都是在链表或者数组上的特殊操作，API 不同而已。比如说：

「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。
- 用数组实现，就要处理扩容缩容的问题；
- 用链表实现，没有这个问题，但需要更多的内存空间存储节点指针。
「图」的两种表示方法，邻接矩阵就是二维数组，邻接表就是链表。
- 邻接矩阵判断连通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空间。
- 邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵。
「散列表」就是通过散列函数把键映射到一个大数组里。
- 而且对于解决散列冲突的方法，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；
- 线性探查法就需要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些。
「树」
- 用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；
- 用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

综上，数据结构种类很多，甚至你也可以发明自己的数据结构，但是底层存储无非数组或者链表，二者的优缺点如下：

数组由于是紧凑连续存储，可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 $O(N)$；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 $O(N)$。
链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 $O(1)$。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

2. DS 的基本操作

对于任何数据结构，其基本操作无非遍历 + 访问，再具体一点就是：增删查改。

数据结构种类很多，但它们存在的目的都是在不同的应用场景，尽可能高效地增删查改。话说这不就是数据结构的使命么？

如何遍历 + 访问？我们仍然从最高层来看，各种数据结构的遍历 + 访问无非两种形式：

线性的：for/while 迭代为代表
非线性的：递归为代表

具体而言，无非以下几种框架：

数组遍历框架，典型的线性迭代结构：

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 迭代访问 arr[i]
    }
}

链表遍历框架，兼具迭代和递归结构：

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next);
}

二叉树遍历框架，典型的非线性递归遍历结构：
```
/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    // 这里属于前序位置
    traverse(root.left);
    // 这里属于中序位置
    traverse(root.right);
    // 这里属于后序位置
}
```
- 所谓前序位置，就是刚进入一个节点（元素）的时候；
- 所谓后序位置，就是即将离开一个节点（元素）的时候；
- 所谓中序位置，就是一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候。

二叉树框架可以扩展为 N 叉树的遍历框架：

你看二叉树的递归遍历方式和链表的递归遍历方式，相似不？再看看二叉树结构和单链表结构，相似不？如果再多几条叉，N 叉树你会不会遍历？

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    // 这里属于前序位置
    for (TreeNode child : root.children) {
        traverse(child);
    }
    // 这里属于后序位置
}

图的遍历：N 叉树的遍历又可以扩展为图的遍历，因为图就是好几 N 叉棵树的结合体。你说图是可能出现环的？这个很好办，用个布尔数组 visited 做标记就行了，这里就不写代码了。

所谓框架，无外乎就是套路。不管增删查改，上述这些代码都是永远无法脱离的结构，你可以把这个结构作为大纲，根据具体问题在框架上添加代码就行了。

3. DSA 的学习路径

建议的刷题顺序是：

先学习像数组、链表这种基本数据结构的常用算法，比如单链表翻转，前缀和数组，二分搜索等。
因为这些算法属于会者不难难者不会的类型，难度不大，学习它们不会花费太多时间。而且这些小而美的算法经常让你大呼精妙，能够有效培养你对算法的兴趣。
学会基础算法之后，不要急着上来就刷回溯算法、动态规划这类笔试常考题，而应该先刷二叉树，先刷二叉树，先刷二叉树，重要的事情说三遍。
为什么要先刷二叉树呢，因为二叉树是最容易培养框架思维的，而且所有的递归算法技巧，本质上都是树的遍历问题。
对于一个理解二叉树的人来说，刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理，不妨从二叉树下手，前 10 道也许有点难受；结合框架再做 20 道，也许你就有点自己的理解了；刷完整个专题，再去做什么回溯动规分治专题，你就会发现只要涉及递归的问题，都是树的问题。

综上，对于畏惧算法的你来说，可以先刷树的相关题目，试着从框架上看问题，而不要纠结于细节问题。

何为纠结细节问题？就比如纠结 i 到底应该加到 n 还是加到 n - 1，这个数组的大小到底应该是 n 还是 n + 1。

从框架上看问题，就是像我们这样基于框架进行抽取和扩展，既可以在看别人解法时快速理解核心逻辑，也有助于找到我们自己写解法时的思路方向。当然，如果细节出错，你得不到正确的答案，但是只要有框架，你再错也错不到哪去，因为你的方向是对的。

你要是心中没有框架，那么你根本无法解题，给了你答案，你也不会发现这就是个树的遍历问题。

这种思维是很重要的，动态规划详解中总结的找状态转移方程的几步流程，有时候按照流程写出解法，可能自己都不知道为啥是对的，反正它就是对了......这就是框架的力量，能够保证你在快睡着的时候，依然能写出正确的程序；就算你啥都不会，都能比别人高一个级别。

4. 数学算法 vs 计算机算法

4.1 本质辨析

利用计算机求解问题的方法其实可以分为两类：数学算法、计算机算法。

对前者来说，重点在数学建模和调参经验，计算机真就只是拿来做计算的工具而已；而后者的重点是计算机思维，需要你能够站在计算机的视角，抽象、化简实际问题，然后用合理的数据结构去解决问题。

数学算法：比如一行代码就能解决的算法题，这些题目类似脑筋急转弯，都是通过观察，发现规律，然后找到最优解法。再比如，密码学算法、机器学习算法，它们的本质确实不是穷举，而是数学原理的编程实现，所以这类算法的本质是数学，不在我们所探讨的「数据结构和算法」的范畴之内。
对于软件开发者而言，这类算法问题较少，不必特别纠结。
计算机算法：指「数据结构和算法」中的算法，如果要用一句话总结，那就是这种算法的本质就是「穷举」。对于程序员来说，这种问题真的不需要有多少数学基础，只要学会用计算机思维解决问题就够了。

很多刚入门的人，觉得计算机算法是一个很高大上的东西，每见到一道题，就想着能不能推导出一个什么数学公式，啪的一下就能把答案算出来。比如你和一个没学过计算机算法的人说你写了个计算排列组合的算法，他大概以为你发明了一个公式，可以直接算出所有排列组合。但实际上呢？没什么高大上的公式，文章回溯算法秒杀排列组合子集问题写了，其实就是把排列组合问题抽象成一棵多叉树结构，然后用回溯算法去暴力穷举。

对计算机算法的误解也许是以前学数学留下的「后遗症」，数学题一般都是你仔细观察，找几何关系，列方程，然后算出答案。如果说你需要进行大规模穷举来寻找答案，那大概率是你的解题思路出问题了。

而计算机解决问题的思维恰恰相反：有没有什么数学公式就交给你们人类去推导吧，如果能找到一些巧妙的定理那最好，但如果找不到，那就穷举呗，反正只要复杂度允许，没有什么答案是穷举不出来的。理论上讲只要不断随机打乱一个数组，总有一天能得到有序的结果呢！当然，这绝不是一个好算法，因为鬼知道它要运行多久才有结果。

4.2 计算机算法的难点

然而，千万不要觉得穷举这个事儿很简单，穷举有两个关键难点：无遗漏、无冗余。

遗漏，会直接导致答案出错，比如让你求最小值，你穷举时恰好把那个答案漏掉了，这不就错了嘛；
冗余，会拖慢算法的运行速度，比如你的代码把完全相同的计算流程重复了十遍，那你的算法不就慢了十倍么，就有可能超过判题平台的时间限制。

所以，当看到一道算法题，可以从这两个维度去思考：

如何穷举？ 即无遗漏地穷举所有可能解。
如何聪明地穷举？ 即避免所有冗余的计算，消耗尽可能少的资源求出答案。

不同类型的题目，难点是不同的，有的题目难在「如何穷举」，有的题目难在「如何聪明地穷举」。

如何穷举

什么算法的难点在「如何穷举」呢？一般是递归类问题，最典型的就是动态规划系列问题。

后文动态规划核心套路阐述了动态规划系列问题的核心原理，无非就是先写出暴力穷举解法（状态转移方程），加个备忘录就成自顶向下的递归解法了，再改一改就成自底向上的递推迭代解法了。动态规划的降维打击里也讲过如何分析优化动态规划算法的空间复杂度。

上述过程就是在不断优化算法的时间、空间复杂度，也就是所谓「如何聪明地穷举」。这些技巧一听就会了，但很多读者留言说明白了这些原理，遇到动态规划题目还是不会做，因为想不出状态转移方程，第一步的暴力解法都写不出来。

这很正常，因为动态规划类型的题目可以千奇百怪，找状态转移方程才是难点，所以才有了动态规划设计方法：数学归纳法这篇文章，告诉你递归穷举的核心是数学归纳法，明确函数的定义，然后利用这个定义写递归函数，就可以穷举出所有可行解。

如何聪明地穷举

什么算法的难点在「如何聪明地穷举」呢？一些耳熟能详的非递归算法技巧，都可以归在这一类。

比如后文 Union Find 并查集算法详解告诉你一种高效计算连通分量的技巧，理论上说，想判断两个节点是否连通，我用 DFS/BFS 暴力搜索（穷举）肯定可以做到，但人家 Union Find 算法硬是用数组模拟树结构，给你把连通性相关的操作复杂度给干到 $O(1)$ 了。

这就属于聪明地穷举，大佬们把这些技巧发明出来，你学过就会用，没学过恐怕很难想出这种思路。

再比如贪心算法技巧，后文当老司机学会贪心算法就告诉你，所谓贪心算法就是在题目中发现一些规律（专业点叫贪心选择性质），使得你不用完整穷举所有解就可以得出答案。

人家动态规划好歹是无冗余地穷举所有解，然后找一个最值，你贪心算法可好，都不用穷举所有解就可以找到答案，所以后文贪心算法解决跳跃游戏中贪心算法的效率比动态规划还高。当然，并不是所有问题都存在贪心选择性质让你投机取巧，所以全量穷举虽然朴实无华且枯燥，但真的是任何情况下都可以用的。

再比如大名鼎鼎的 KMP 算法，你写个字符串暴力匹配算法很容易，但你发明个 KMP 算法试试？KMP 算法的本质是聪明地缓存并复用一些信息，减少了冗余计算，前文 KMP 字符匹配算法就是使用状态机的思路实现的 KMP 算法。

领悟 DSA

详情