《拉钩课程 — 重学数据结构与算法》学习笔记

一、代码效率优化方法论

1、数据结构，从名字上来看是数据的结构，也就是数据的组织方式。

2、复杂度是衡量代码运行效率的重要度量因素。

3、复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n)，那么就用个大写字母 O 和括号，把 f(n) 括起来就可以了，即 O(f(n))。

4、复杂度通常包括时间复杂度和空间复杂度。在具体计算复杂度时需要注意以下几点：

• 它与具体的常系数无关，O(n) 和 O(2n) 表示的是同样的复杂度；
• 复杂度相加的时候，选择高者作为结果，也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度；
• O(1) 也是表示一个特殊复杂度，即任务与算例个数 n 无关；

5、关于时间复杂度，有一些经验性的结论：

• 一个顺序结构的代码，时间复杂度是 O(1)；
• 二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn)；
• 一个简单的 for 循环，时间复杂度是 O(n)；
• 两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)；
• 两个嵌套的 for 循环，时间复杂度是 O(n²)；

6、时间复杂度与代码的结构设计高度相关，空间复杂度与代码中数据结构的选择高度相关。而空间是廉价的，时间是昂贵的。

7、常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等；而降低空间复杂度的核心思路就是，能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

8、在实际的工作中，如果你不知道该用什么数据结构的时候，就一定要回归问题本源。从数据需要被处理的动作出发。只有明确了会有什么动作，才能找到最合适的解决方法。

9、在实际开发中，经过工程师验证并且能有效解决问题的高效率数据结构就比较有限了。事实上，只要我们把这些能真正解决问题的数据结构学会，就足以成为一名合格的软件工程师了。

二、数据结构基础

1、经过我们的分析，数据处理的基本操作只有 3 个，分别是增、删、查。其中，增和删又可以细分为在数据结构中间的增和删，以及在数据结构最后的增和删。区别就在于原数据的位置是否发生改变。查找又可以细分为按照位置条件的查找和按照数据数值特征的查找。几乎所有的数据处理，都是这些基本操作的组合和叠加。

2. 线性表

2.1、线性表是 n 个数据元素的有限序列，最常用的是链式表达，通常也叫作线性链表或者链表。在链表中存储的数据元素也叫作结点，一个结点存储的就是一条数据记录。每个结点的结构包括两个部分：

• 第一是具体的数据值；
• 第二是指向下一个结点的指针。

在链表的最前面，通常会有个头指针用来指向第一个结点，称为头结点。对于链表的最后一个结点，由于在它之后没有下一个结点，因此它的指针是个空指针。

2.2、有时候为了弥补单向链表的不足，我们可以对结点的结构进行改造：

• 对于一个单向链表，让最后一个元素的指针指向第一个元素，就得到了循环链表；
• 或者把结点的结构进行改造，除了有指向下一个结点的指针以外，再增加一个指向上一个结点的指针。这样就得到了双向链表。

2.3、链表在新增、删除数据都比较容易，可以在 O(1) 的时间复杂度内完成。但对于查找，不管是按照位置的查找还是按照数值条件的查找，都需要对全部数据进行遍历。这显然就是 O(n) 的时间复杂度。

tips：虽然链表在新增和删除数据上有优势，但仔细思考就会发现，这个优势并不实用。这主要是因为，在新增数据时，通常会伴随一个查找的动作。

2.4、如果数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合适。如果数据元素大小确定，删除插入的操作并不多，那么数组可能更适合些。

3. 栈

3.1 栈是一种特殊的线性表。 栈与线性表的不同，体现在增和删的操作。具体而言，栈的数据结点必须后进先出。后进的意思是，栈的数据新增操作只能在末端进行，不允许在栈的中间某个结点后新增数据。先出的意思是，栈的数据删除操作也只能在末端进行，不允许在栈的中间某个结点后删除数据。

3.2 单纯从功能上讲，数组或者链表都可以替代栈。然而问题是，数组或者链表的操作过于灵活，这意味着，它们过多暴露了可操作的接口。这些没有意义的接口过多，当数据量很大的时候就会出现一些隐藏的风险。

3.3 跟线性表一样，栈也有顺序表示和链式表示，分别称作顺序栈和链栈。

3.4 栈继承了线性表的优点与不足，是个限制版的线性表。限制的功能是，只允许数据从栈顶进出，这也就是栈后进先出的性质。不管是顺序栈还是链式栈，它们对于数据的新增操作和删除操作的时间复杂度都是 O(1）。而在查找操作中，栈和线性表一样只能通过全局遍历的方式进行，也就是需要 O(n) 的时间复杂度。

3.5 栈具有后进先出的特性，当你面对的问题需要高频使用新增、删除操作，且新增和删除操作的数据执行顺序具备后来居上的相反关系时，栈就是个不错的选择。

4. 队列

4.1 与栈相似，队列也是一种特殊的线性表，与线性表的不同之处也是体现在对数据的增和删的操作上。队列的特点是先进先出。先进，表示队列的数据新增操作只能在末端进行，不允许在队列的中间某个结点后新增数据；先出，队列的数据删除操作只能在始端进行，不允许在队列的中间某个结点后删除数据。

4.2 队列中队头的指针称为 front 指针，队尾的指针称为 rear 指针；与线性表、栈一样，队列也存在两种存储方式，即顺序队列和链式队列；顺序队列依赖数组来实现，需要解决数组越界问题，我们通过队列的一种特殊变种来解决，叫作循环队列。

4.3 特别值得一提的是，如果链表删除仅剩的一个元素后，rear 指针就变成野指针了。这时候，需要让 rear 指针指向头结点。也许你会对头结点存在的意义产生怀疑，似乎没有它也不影响增删的操作。那么为何队列还特被强调要有头结点呢？这主要是为了防止删除最后一个有效数据结点后， front 指针和 rear 指针变成野指针，导致队列没有意义了。有了头结点后，哪怕队列为空，头结点依然存在，能让 front 指针和 rear 指针依然有意义。

4.4 在时间复杂度上，循环队列和链式队列的新增、删除操作都为 O(1)。而在查找操作中，队列和线性表一样只能通过全局遍历的方式进行，也就是需要 O(n) 的时间复杂度。在空间性能方面，循环队列必须有一个固定的长度，因此存在存储元素数量和空间的浪费问题，而链式队列不存在这种问题，所以在空间上，链式队列更为灵活一些。

4.5 通常情况下，在可以确定队列长度最大值时，建议使用循环队列。无法确定队列长度时，应考虑使用链式队列。队列具有先进先出的特点，很像现实中人们排队买票的场景。在面对数据处理顺序非常敏感的问题时，队列一定是个不错的技术选型。

5. 数组

5.1 数组是数据结构中的最基本结构，几乎所有的程序设计语言都把数组类型设定为固定的基础变量类型。我们可以把数组理解为一种容器，它可以用来存放若干个相同类型的数据元素。

5.2 接下来，我们来归纳一下数组增删查的时间复杂度。

• 增加：若插入数据在最后，则时间复杂度为 O(1)；如果中间某处插入数据，则时间复杂度为 O(n)。
• 删除：对应位置的删除，扫描全数组，时间复杂度为 O(n)。
• 查找：如果只需根据索引值进行一次查找，时间复杂度是 O(1)。但是要在数组中查找一个数值满足指定条件的数据，则时间复杂度是 O(n)。

5.3 相对而言，数组更适合在数据数量确定，即较少甚至不需要使用新增数据、删除数据操作的场景下使用，这样就有效地规避了数组天然的劣势。在数据对位置敏感的场景下，比如需要高频根据索引位置查找数据时，数组就是个很好的选择了。

5.4 实际上数组是一种相当简单的数据结构，其增删查的时间复杂度相对于链表来说整体上是更优的。那么链表存在的价值又是什么呢？首先，链表的长度是可变的，数组的长度是固定的，如果没有引用 ArrayList 时，数组申请的空间永远是我们在估计了数据的大小后才执行，所以在后期维护中也相当麻烦。其次，链表不会根据有序位置存储，进行插入数据元素时，可以用指针来充分利用内存空间。数组是有序存储的，如果想充分利用内存的空间就只能选择顺序存储，而且需要在不取数据、不删除数据的情况下才能实现。

6、为什么字符串是用数组结构实现，而不是用链表？在链式存储中，每个结点设置字符数量的多少，与串的长度、可以占用的存储空间以及程序实现的功能相关。如果字符串中包含的数据量很大，但是可用的存储空间有限，那么就需要提高空间利用率，相应地减少结点数量。而如果程序中需要大量地插入或者删除数据，如果每个节点包含的字符过多，操作字符就会变得很麻烦，为实现功能增加了障碍。因此，串的链式存储结构除了在连接串与串操作时有一定的方便之外，总的来说，不如顺序存储灵活，在性能方面也不如顺序存储结构好。

7. 树和二叉树

7.1、树是由结点和边组成的，不存在环的一种数据结构。树满足递归定义的特性。也就是说，如果一个数据结构是树结构，那么剔除掉根结点后，得到的若干个子结构也是树，通常称作子树。

7.2、二叉树是一种被高频使用的特殊树，在二叉树中，每个结点最多有两个分支，即每个结点最多有两个子结点，分别称作左子结点和右子结点。在二叉树中，有下面两个特殊的类型：

• 满二叉树，定义为只有最后一层无任何子结点，其他所有层上的所有结点都有两个子结点的二叉树。
• 完全二叉树，定义为除了最后一层以外，其他层的结点个数都达到最大，并且最后一层的叶子结点都靠左排列。

7.3、对于没有任何特殊性质的二叉树而言，抛开遍历的时间复杂度以外，真正执行增加和删除操作的时间复杂度是 O(1)。

7.4、遍历一棵树，有非常经典的三种方法，分别是前序遍历、中序遍历、后序遍历。这里的序指的是父结点的遍历顺序，前序就是先遍历父结点，中序就是中间遍历父结点，后序就是最后遍历父结点。不管哪种遍历，都是通过递归调用完成的。时间复杂度都是 O(n);

7.5、二叉查找树（也称作二叉搜索树）具备以下几个的特性：

• 在二叉查找树中的任意一个结点，其左子树中的每个结点的值，都要小于这个结点的值；
• 在二叉查找树中的任意一个结点，其右子树中每个结点的值，都要大于这个结点的值；
• 在二叉查找树中，会尽可能规避两个结点数值相等的情况；
• 对二叉查找树进行中序遍历，就可以输出一个从小到大的有序数据队列；
• “二分查找” 所消耗的时间复杂度可以降低为 O(logn)；
• 二叉查找树插入动作的时间复杂度仍然是 O(1)。
• 二叉查找树的删除操作会比较复杂，这是因为删除完某个结点后的树，仍然要满足二叉查找树的性质。

8. 哈希表

8.1 如何设计哈希函数？我们先看一些常用的设计哈希函数的方法：

• 直接定制法。哈希函数为关键字到地址的线性函数。如，H (key) = a*key + b。 这里，a 和 b 是设置好的常数。
• 数字分析法。假设关键字集合中的每个关键字 key 都是由 s 位数字组成（k1,k2,…,Ks），并从中提取分布均匀的若干位组成哈希地址。
• 平方取中法。如果关键字的每一位都有某些数字重复出现，并且频率很高，我们就可以先求关键字的平方值，通过平方扩大差异，然后取中间几位作为最终存储地址。
• 折叠法。如果关键字的位数很多，可以将关键字分割为几个等长的部分，取它们的叠加和的值（舍去进位）作为哈希地址。
• 除留余数法。预先设置一个数 p，然后对关键字进行取余运算。即地址为 key mod p。

8.2 如何解决哈希冲突？上面这些常用方法都有可能会出现哈希冲突。那么一旦发生冲突，我们该如何解决呢？

• 开放定址法。即当一个关键字和另一个关键字发生冲突时，使用某种探测技术在哈希表中形成一个探测序列，然后沿着这个探测序列依次查找下去。当碰到一个空的单元时，则插入其中。
• 链地址法。将哈希地址相同的记录存储在一张线性链表中。

8.3 哈希表在我们平时的数据处理操作中有着很多独特的优点，不论哈希表中有多少数据，查找、插入、删除只需要接近常量的时间，即 O(1）的时间级。.

8.4 哈希表也有一些不足。哈希表中的数据是没有顺序概念的，所以不能以一种固定的方式（比如从小到大）来遍历其中的元素。在数据处理顺序敏感的问题时，选择哈希表并不是个好的处理方法。同时，哈希表中的 key 是不允许重复的，在重复性非常高的数据中，哈希表也不是个好的选择。

三、算法思维基础

1、递归的基本思想就是把规模大的问题转化为规模小的相同的子问题来解决。这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。总结起来，递归的实现包含了两个部分，一个是递归主体，另一个是终止条件。

2、分治法的使用必须满足 4 个条件：

1. 问题的解决难度与数据规模有关；
2. 原问题可被分解；
3. 子问题的解可以合并为原问题的解；
4. 所有的子问题相互独立。

3、面对一个实际的算法问题，我们需要从以下几个步骤思考如何解决问题：

1. 复杂度分析。估算问题中复杂度的上限和下限。
2. 定位问题。根据问题类型，确定采用何种算法思维。
3. 数据操作分析。根据增、删、查和数据顺序关系去选择合适的数据结构，利用空间换取时间。
4. 编码实现。