2020-4-28，今天开始阅读数据结构与算法之美系列的文章了，看了下一共是56个小节，计划每天完成一个小节的内容，那么预期在两个月读完（实际应该会更快一点，周末可以考虑适当多看一点）， 但是需要注意相关题目，比如看到链表相关章节的时候，需要完成小节的相关题目，吃透题目的解答，当作是一个对基础数据结构和算法的回顾复习，拓展思维模式。 暂时定在每天早上到公司以后的前半个小时完成，如果无法完成而当天事情较多，中午吃饭后继续阅读做题。利用好自己的时间啊，不能浪费了。

　　1、讲为什么要学习数据结构与算法的时候，提到一个概念，和《程序员修炼之道》里的很接近，就是说你到底要写出什么样的代码，是能跑就行，无需考虑效率，也无需考虑美感（当然 这个可能和这个专题关系不太大）；核心是说你对自己的要求有多高。比如你想想你现在的两个服务loginfeature和loginmodel，你觉得从代码层面还有什么地方可以优化的，起码loginmodel 就可以用策略模式来调整一下现在的根据templateId判断的调各种模型的不同逻辑代码。总体来说就是在平时的开发过程中，工期比较急确实可以先写完逻辑推上去，但到了有时间的时候，就需要 进行优化了，这才是锻炼人的地方。你如果永远都写只是凑合着用的代码，那么你必然会被淘汰。

　　2、讲学习方法，一个核心就是 “学而不思则罔，思而不学则殆”，只是单纯的死记硬背或许能帮你刷一些题目，但是对个人思维的提高很有限。第二是需要动手编写，而不是只是看别人的实现， 需要手动把每一道题都实现。

　　3、算法的时间复杂度分析。时间复杂度的全称是渐进时间复杂度，表示的是算法的执行时间与数据规模之间的增长关系，因此常数时间的执行是不计算在内的。算法的执行时间公式 如下 T(n) = O(f(n))，其中T(n)表示算法执行的总时间，f(n)表示每一行代码的执行次数之和。 常用的时间复杂度量级就是那几个：O(1)、O(log(n))、O(n)、O(nlog(n))、O(nn)、O(2^n)等。

　　4、五一期间一直没有看这本书，从5月5日继续看第四章。这一章继续讲时间复杂度，引入了几个新的概念：最好情况时间复杂度 、最坏情况时间复杂度、平均情况时间复杂度。分析一段代码的时间复杂度，需要注意的就是可能存在的不同分支逻辑，一个分支 的复杂度是O(n)，另一个分支的是O(1)，那么整段代码的时间复杂度应该看走向不同分支的概率，比如大部分走向了O(1)，那么整体 往往就是O(1)的时间复杂度；反之也一样。

　　5、数组。计算机会给每个内存单元分配一个地址，并通过地址来访问内存中的数据。当计算机需要访问数组中的某个元素的 时候，它会首先通过寻址公式计算出存储该元素的内存地址，然后访问。这里往往会有一个错误的表述—“链表适合插入，删除， 时间复杂度为O(1)，数组适合查找，时间复杂度为O(1)"。我们知道即使是排好序的数组，二分查找的时间复杂度也是O(log(n)) ，因此正确的表述应该是——“数组支持随机访问，根据下标随机访问的时间复杂度为O(1)"。

　　还有一种比较重要的思想：向一个数组的位置k插入元素的时候，需要将k以后的元素都往后移动一位，给新来的数据腾位置， 这儿的前提是需要保证数组元素的有序；但是如果数组元素本身是无序的，或者顺序不重要，仅做存储数据用，如果要将某个 元素插入到第k个位置，可以直接将第k位置的元素复制到数组的末尾，然后将新的元素赋值到第k个位置，这样仅需O(1)的复杂度。 这个思想在快速排序中会用到。

　　6、链表(一)。相比第一次看这一个章节，又多了一点理解，在用快慢指针的方式找中间节点时，如果链表的节点数为偶数，那么是 可以找中偏左节点，也可以找中偏右节点。那么这里可以做一个约定，倾向于找中偏右节点。原因可以看链表相关的代码，在判断一个链表 是否回文时，找中偏右节点为中间节点，会更加方便一点。

　　关于链表的几道题目，可以参考ListNode博客。

　　7、需要做够多的题目，才能充分意识到什么时候使用栈。Java中的Stack内部使用的是一个数组来存储数据的，涉及到一些扩容操作，扩容操作都在父类Vector中实现了。需要注意的是 栈的入栈和出栈操作时间复杂度都是O(1)，只有在少数情况下才会扩容，进行数组内部元素的搬迁。

　　操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成栈这种结构，每进入一个函数，都会产生一个这个函数对应的栈帧，这个函数的临时变量以及参数都会压入这个栈帧。我们知道的 使用栈的场景有：编译器表达式求值(需要一个操作数栈和操作符栈)，判断一个字符串中的括号是否匹配等。

　　8、队列。和栈一样，内部存储元素的数据结构可以是数组，也可以是链表(想起Doug Lea在JDK1.7的并发包里增加的LinkedTransferQueue，这个队列内部就是链表)。队列往往和栈相反，支持FIFO，但是也有 双端队列，头部和尾部都同时支持增加和删除元素。实现一个队列的时候，往往都在内部维护一个tail下标和一个head下标(对于链表来说就是指针)，head永远指向第一个元素的位置，tail指向最后一个元素 的下一个位置。数组里也可以让tail指向数组最后一个元素的位置；当head == tail时，队列为空；当tail == 数组的size + 1时，队列满。

　　使用数组来实现的时候，随着不断的入队列和出队列操作，head和tail都会不断往后移动。理论上，在你第一次head++的时候，即第一个元素出队列后，你需要将剩下的所有元素整体前移，填充释放的空间； 但是也可以有一种优化的思路：出队列的时候不实时搬迁数据，在入队的时候，如果发现队列满了(即tail = 数组的size + 1，并且head != 0；如果head还等于0那表示队列真的满了)，那么意味着队列前面有一些 已经删除的元素，但是空间仍然可以使用，这时进行一次整体数据的搬迁。

　　避免数据搬迁的方案——循环队列：首尾相连，可以形成一个环。可以参考这篇文章循环队列，这时当head == tail时队列 为空；当head == (tail + 1) % 数组size时，队列满，此时tail指向的位置并不存储元素，所以会一直浪费一个空间的存储。而在循环队列中，入队不再是简单的tail++了，而是tail = (tail + 1) % 数组 size。循环队列最优雅的设计在于Linux内核的数据结构循环队列之kfifo，值得深入研究研究。

　　阻塞队列意味着入队时，如果空间已满，那么操作会阻塞；出队时，如果队列为空，也会阻塞。看Java里面ArrayBlockingQueue和LinkedBlockingQueue代码，里面阻塞都是使用了Condition来进行同步的， 当队列满时，入队方法阻塞，本质上调用的一个Condition的await()方法，在有出队操作的时候，调用该条件变量的signal()方法；同理，入队时调用另一个Condition的signal()方法，表示通知收到了数据，阻塞 住的出队方法即可被唤醒。

　　并发队列，主要也是并发包里面的一些类，比如ConcurrentLinkedQueue，内部使用Unsafe提供的CAS操作(而不是加锁)来实现线程安全的更新，这就是一个无锁的并发队列。

　　在构建一个线程池的时候，往往我们都传的是一个BlockingQueue，作为存放任务的工作队列，如果线程处理不过来，就先将任务放到队列中，这时我们往往使用的是一个LinkedBlockingQueue， 也就是说，即使队列内部使用的链表实现，也不意味着我们就要让这个链表可以无限长(即无界队列)。

　　9、递归。这本书里面讲到比较难以理解的两种基础算法思想，一个是递归，另一个是动态规划。这时候，我就想到之前在做链表翻转的题目 的时候，其实也有递归的解法的，而且递归解法的代码非常的短，只是相对不那么容易理解。这次我们再来看一下。首先思考：

什么样的问题可以用递归来求解？

  • 1、这个问题的解可以分解为几个子问题的解，这样你才能转移为求解子问题，这是你的递推公式的核心；
  • 2、原问题与分解后的子问题，除了数据规模不一样以外，求解思路一样；
  • 3、存在递归终止条件。将原问题分解为子问题并逐级再一层一层分解后，是需要有终止条件的。
  • 最重要的一点：不要像平常debug一样，跳进递归里面层层去想，容易头大，这是一个思维误区。

　　递归的缺点，一个是调用栈容易过深，造成堆栈溢出；第二是重复计算，同一个子问题被计算多次，以此，我们在很多时候需要把计算完成的子问题保存在某个数据结构中，以防重复计算问题。

　　10、排序。整体上会讲下面几种排序算法，其中基于比较的排序算法在执行过程中，会涉及到两种操作：一种是比较元素之间的大小，另一种是交换操作。很早以前用c++写过一版下面的排序算法，放在了GitHub 上，这个是链接常用排序算法的c++实现，里面冒泡是有点小问题的，我们一会可以看到。

排序算法            时间复杂度       是否基于比较        
 冒泡、插入、选择      O(n^2)          是，且这三种都是原地排序，无需开辟新的内存空间
 快排、归并           O(n*log(n))      是
 桶、计数、基数        O(n)            否

　　对于排序算法的执行效率，我们一般会从以下几个方面来衡量：

    1. 最好、最坏、平均情况下的时间复杂度。而且这三种情况下的时间复杂度所对应的原始数据是什么样子的。
    1. 这时候需要考虑时间复杂度的系数、常数、低阶。因为在实际开发中你需要排序的数据往往是确定数量的，比如100w个等。
    1. 比较次数和交换次数，前面我们提到你说的出口的那些排序算法都是基于比较的，所以需要考虑比较的次数，交换的次数等。
    1. 排序算法的内存消耗：往往是看你的排序算法需不需要开辟一块新的内存空间。比如归并排序往往就需要，而像冒泡、插入、选择这些都是原地排序，不需要开辟新的内存空间。
    1. 排序算法的稳定性：稳定性指的是原始数据中值相等的两个元素，排好序以后能否保持他们的先后顺序不变。这一点比较重要，我们熟知的快排就是一个不稳定的排序算法。比如在实际开发中，我们要排序的是 一组对象，按照对象的某个field来排序，这个field一样的对象，则按照另一个field排序，诸如此类的，就需要考虑到排序算法本身的稳定性。

　　对于这些排序算法，新开了一篇文章，不放在这篇里面了，见排序算法。

　　11、二分查找，对于二分查找及其各种变种，单独写一篇文章，见二分查找及其变种。

　　12、跳表-SkipList。跳表是一个很重要的数据结构，Redis在实现sortedSet的时候，核心之一就是SkipList。跳表核心思想就是利用链表来实现部分数组的功能，以达到查找、新增以及删除某个元素的时间 复杂度都达到O(log(n))，我们知道数组支持随机访问，但是不能很好的支持插入和删除元素，链表可以很好地支持插入和删除元素，但是无法做到随机访问。我们常常说的树可以把这两者的优势相结合，最终达到 O(log(n))的复杂度，事实上，跳表也可以，很多场景下跳表是可以替代红黑树的。

　　跳表就是给一个链表的部分节点一直建立上层索引，可以平均每k个节点就在提取一个节点到更上层，这样一直向上维护索引，最底层是原始的链表数据。跳表的插入和删除元素，都涉及到索引的更新和删除，你可以 想象：如果你插入元素永远都只插入到最底层链表中而不更新索引，那你的索引就会失去意义了，最终查找一个元素还是会退化到O(n)的时间复杂度，删除也一样。而在插入一个元素的时候，这个元素是否要被添加 到索引中，以及添加到哪几层的索引中，这也是需要一个算法来解决的，往往是一个随机函数，这个随机函数决定当前元素需要插入到哪些索引层中，所以这个随机函数也是比较重要的，它直接影响着跳表的性能。

　　Redis中有序集合（SortedSet），不止用到了跳表，还用到了散列表，有序集合支持的核心操作主要有下面几个：

  • 1）插入一个元素
  • 2）删除一个元素
  • 3）查找一个元素
  • 4）按照区间查找数据，比如查找[100, 230]之间的所有数据
  • 5）迭代输出有序序列

　　其中插入删除和查找如果用红黑树来实现，也可以达到O(log(n))的时间复杂度，但是如果按照区间查找，红黑树的效率不如跳表高效。对于按照区间查找数据这个操作，跳表可以做到O(log(n))的 时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，这样做非常高效。而且，跳表相对于红黑树来说，更容易实现一点。

　　13、散列表。后面单独成一篇文章。

　　28、堆和堆排序。堆这种数据结构的应用场景有很多，比如Java中的优先队列，最经典的是使用堆排序。这是一种原地的，时间 复杂度是O(n*log(n))的排序算法，前面提到过快排的平均时间复杂度也是这么多，但是实际中快排比堆排序要好很多。 参考堆这一章节的内容。

　　29、图。图分为有向和无向，边上也可以带权重或者不带权重。有向图中，顶点的度又分为入度 和出度，在内存中存储图这种数据结构一般有两种方法：

  • （1） 邻接矩阵法，底层是一个二维数组，对于无向图来说，如果顶点i与顶点j之间有边，我们就 将A[i][j]和A[j][i]标记为1；对于有向图来说，如果顶点i到顶点j之间，有一条箭头从顶点i指 向顶点j的边，那我们就将A[i][j]标记为1。同理，如果有一条箭头从顶点j指向顶点i的边，我们就 将A[j][i]标记为1。对于带权图，数组中就存储相应的权重。

　　无向图的问题在于比较浪费存储空间，对于无向图，来说，事实上我们只需要整个二维数组的一半 就可以表达图的含义了；其次，如果这个图比较稀疏，顶点很多但是边比较少的情况，那么这个二维 数组中就包含了大量的0，绝大部分存储都被浪费了。

　　无向图的好处在于计算快，存储方式简单，数组也能支持随机访问。

  • （2） 邻接表法，每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。这里的 链表其实是有很多优化方式的，比如我们知道链表对查找支持的不友好，所以我们可以把链表这里 转换为平衡二叉查找树，红黑树，跳表等。

　　30、深度优先搜索和广度优先搜索，见另一篇文章。

　　31、字符串相关，共有三个章节，都是讲匹配算法的，见单独文章，由浅入深的讲解了KMP算法。

　　32、Trie树。上一章学习的字符串匹配算法，往往都适用于在单个主串中寻找单个模式串，判断其是否存在；如果要在某个主串中寻找多个模式串，判断其是否存在，那么前面的BM、KMP就不太适合了。 所以这里引入了两种新的算法，一是Trie树，二是AC自动机，他们的典型适用场景就是敏感词过滤，这也是之前信安提供的那个敏感词检测jar包中的实现方式，将敏感词词库构建成一颗Trie树，接下来判断某个字符串中 是否能够匹配到Trie树的一条路径。

　　Trie树，也叫字典树，是一种专门用来处理字符串匹配问题的树形结构。这里需要配合着王争画的图来看，非常容易理解它的结构。字典树的难点在于，它是一棵多叉树，不再像平常的二叉树一样使用左右两个叶子 节点指针来指向其子节点。所以你需要考虑，每一个节点除了其数据以外，如何保存它的子节点的信息。这里的常规思路就是利用数组，数组的长度是字符串中不同字符的个数，LeetCode上有一些关于实现字典树的题目。

　　在刚刚讲的这个场景，在一组字符串中查找字符串，Trie树实际上表现得并不好。它对要处理的字符串有及其严苛的要求。

  • 1） 字符串中包含的字符集不能太大。我们前面讲到，如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。
  • 2） 要求字符串的前缀重合比较多，不然空间消耗会变大很多。
  • 3） 如果要用Trie树解决问题，那我们就要自己从零开始实现一个Trie树，还要保证没有bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。
  • 4） 我们知道，通过指针串起来的数据块是不连续的，而Trie树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

　　所以事实上，字典树不是很适合精确匹配查找，这种问题更适合用红黑树和散列表来实现，字典树比较适合查找前缀匹配的字符串。

　　33、AC自动机

　　单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。 尽管，单模式串匹配算法也能完成多模式串的匹配工作。我们可以针对每个敏感词，通过单模式串匹配算法（比如KMP算法）与用户输入的文字内容进行匹配。但是，这样做的话，每个匹配过程都需要扫描一遍用户输入的 内容。整个过程下来就要扫描很多遍用户输入的内容。如果敏感词很多，比如几千个，并且用户输入的内容很长，假如有上千个字符，那我们就需要扫描几千遍这样的输入内容。很显然，这种处理思路比较低效。

　　与单模式匹配算法相比，多模式匹配算法在这个问题的处理上就很高效了。它只需要扫描一遍主串，就能在主串中一次性查找多个模式串是否存在，从而大大提高匹配效率。我们知道，Trie树就是一种多模式串匹配算法。 那如何用Trie树实现敏感词过滤功能呢？我们可以对敏感词字典进行预处理，构建成Trie树结构。这个预处理的操作只需要做一次，如果敏感词字典动态更新了，比如删除、添加了一个敏感词，那我们只需要动态更新一下 Trie树就可以了。

　　当用户输入一个文本内容后，我们把用户输入的内容作为主串，从第一个字符（假设是字符C）开始，在Trie树中匹配。当匹配到Trie树的叶子节点，或者中途遇到不匹配字符的时候，我们将主串的开始匹配位置后移一 位，也就是从字符C的下一个字符开始，重新在Trie树中匹配。基于Trie树的这种处理方法，有点类似单模式串匹配的BF算法。我们知道，单模式串匹配算法中，KMP算法对BF算法进行改进，引入了next数组，让匹配 失败时，尽可能将模式串往后多滑动几位。借鉴单模式串的优化改进方法，能否对多模式串Trie树进行改进，进一步提高Trie树的效率呢？这就要用到AC自动机算法了。

　　其实，Trie树跟AC自动机之间的关系，就像单串匹配中朴素的串匹配算法，跟KMP算法之间的关系一样，只不过前者针对的是多模式串而已。所以，AC自动机实际上就是在Trie树之上，加了类似KMP的next数组， 只不过此处的next数组是构建在树上罢了。

　　理解AC自动机的先决条件就是充分理解KMP算法