数据结构与算法

我们学习数据结构和算法，并不是为了死记硬背几个知识点。我们的目的是建立时间复杂度、空间复杂度意识，写出高质量的代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现你的价值，完善你的人生。

概念

数据结构和算法是什么

数据结构是指一组数据的存储结构

算法就是操作数据的方法

数据结构和算法是相辅相成的，数据结构是为算法服务的，而算法要作用在特定的数据结构之上

学习重点

1、数据结构和算法学习的精髓-复杂度分析

数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。所以，如果你只掌握了数据结构和算法的特点、用法，但是没有学会复杂度分析，那就相当于只知道操作口诀，而没掌握心法。只有把心法了然于胸，才能做到无招胜有招！

2、最常用的、最基础的数据结构

数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
3、最常用的算法

递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

4.如何学习

要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”

5.学习技巧

  1. 边学边练，适度刷题
  2. 多思考

复杂度分析

复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。

用来分析算法的执行效率与数据规模之间的增长关系，可以粗略的表示，越高阶的复杂度，算法的执行效率越低。常见的复杂度并不多，从低阶到高阶有:O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。

类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

大 O 复杂度表示法

算法的执行效率，粗略的讲，就是算法代码执行的时间。

从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为 unit_time。

所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比。

T(n)=O(f(n))

  • T(n) 它表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
  • 大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
  • 当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了。

eg：

T(n) = O(2n+2)→T(n) = O(n)

T(n) = O(2n2+2n+3)→T(n) = O(n2)

时间复杂度分析

  1. 只关注循环执行次数最多的一段代码
  2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

几种常见的复杂度实例分析

O(1)

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。

一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

O(logn)、O(nlogn)

对数阶

在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。

O(m+n)、O(m*n)

m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是 O(m+n)。

空间复杂度分析

最好情况时间复杂度

最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。

最坏情况时间复杂度

最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。

平均情况时间复杂度

线性表

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

非线性表

比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

特点：

支持随机访问，查找效率高

插入和删除效率慢，移动元素带来很多消耗。

数组是如何实现根据下标随机访问数组元素？

计算机会给每个内存单元分配一个地址，，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

  1. a[i]_address = base_address + i * data_type_size

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

链表

链表并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

单链表、双向链表、循环链表

查询慢，增删快

单链表

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。

我们把这个记录下个结点地址的指针叫作后继指针 next。

我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

查找：

根据指针一个结点一个结点的遍历，直到找到相应的节点。时间复杂度为O（n）

循环链表

循环链表的尾结点指针是指向链表的头结点。

双向链表

而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

数组和链表的区别


  • 数组简单易用，在实现上用的是连续的的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
  • 内存的消耗。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

如何用链表实现LRU

LRU是一种缓存的淘汰算法，规则是选取最近最少使用的进行淘汰。

思路：维护一个有序的单链表，越靠近链表尾部的结点是越早之前的访问的。当有一个新数据访问时，我们从链表头部顺序遍历链表：

1.如果此数据是之前已经被缓存在链表中，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，插入链表的头部。

2.如果此数据没有缓存在链表中，又可以分为两种情况：

  • 缓存没满的情况下，讲此节点插入到链表的头部。
  • 缓存慢的情况，进行淘汰，尾部就是最近最少使用的数据，删除尾部节点，并将新的数据结点插入到链表的头部。

基于链表的实现思路，缓存访问的时间复杂度为 O(n)。

如何用数组实现LRU

如何轻松的写出正确的链表代码

技巧一：理解指针或引用的含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

技巧二：警惕指针丢失和内存泄漏

技巧三：利用哨兵简化实现难度

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全而出错。

哨兵，解决的是国家之间的边界问题。同理，这里说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。

还记得如何表示一个空链表吗？head=null 表示链表中没有结点了。其中 head 表示头结点指针，指向链表中的第一个结点。

如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

技巧四：重点留意边界条件处理

  • 如果链表为空时，代码是否能正常工作？
  • 如果链表只包含一个结点时，代码是否能正常工作？
  • 如果链表只包含两个结点时，代码是否能正常工作？
  • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

技巧五：举例画图，辅助思考

技巧六：多写多练，没有捷径

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第 n 个结点
  • 求链表的中间结点

单链表反转

迭代解法思路：

从前往后将每个节点的指针反向，即.next内的地址换成前一个节点的，借助一个prev，一个next指针来实现。但为了防止后面链表的丢失，在每次换之前需要先创建个指针指向下一个节点。

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         ListNode prev=null;
  4.         ListNode curr=head;
  5.         while(curr!=null){
  6.             ListNode next = curr.next;  //记录下一个当前节点的下一个节点
  7.             curr.next=prev;   // 指向前一个节点
  8.             prev=curr;    //prev、curr后移
  9.             curr=next;
  10.         }
  11.         return prev;
  12.     }
  13. }

两个有序的链表合并

思想:

迭代法

引入一个哨兵节点，将该节点指向两个链表第一个节点最小值。作用是为了后续更容易的得到链表。

引入一个prev节点，指向当前头节点的最小值。然

  1. class Solution {
  2.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  3.         ListNode preHead= new ListNode(-1);
  4.         ListNode prev=preHead;
  5.         while(l1 !=null && l2!=null){
  6.             if(l1.val<=l2.val){
  7.              prev.next=l1;
  8.              l1=l1.next;
  9.             }else{
  10.                prev.next=l2;
  11.                l2=l2.next;
  12.             }
  13.            prev=prev.next;
  14.         }
  15.         prev.next=l1==null?l2:l1;
  16.         return preHead.next;
  18.     }
  19. }

树

A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫做根节点，也就是图中的节点 E。我们把没有子节点的节点叫做叶子节点或者叶节点，比如图中的 G、H、I、J、K、L 都是叶子节点。

二叉树（Binary Tree）

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。

不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点

满二叉树

上图2 ：叶子节点全部在底层，除了叶子节点，每个节点都有左右两个子节点。

完全二叉树

编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

二叉树的存储方式

一种是基于指针或者引用的二叉链式存储法，

每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针

基于数组的顺序存储法。

我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 i = 2 的位置，右子节点存储在 2 i + 1 = 3 的位置

如果节点 X 存储在数组中下标为 i 的位置，下标为 2 i 的位置存储的就是左子节点，下标为 2 i + 1 的位置存储的就是右子节点如果节点 X 存储在数组中下标为 i 的位置，下标为 2 i 的位置存储的就是左子节点，下标为 2 i + 1 的位置存储的就是右子节点。

二叉树的遍历

前序遍历、中序遍历、后序遍历

前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。

  • 前序遍历: 根节点→左子树→右子树
  • 中序遍历：左子树→根节点→右子树
  • 后续遍历：左子树→右子树→根节点

实际上，二叉树的前、中、后序遍历就是一个递归的过程。

递推公式

  1. 前序遍历的递推公式：
  2. preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
  4. 中序遍历的递推公式：
  5. inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
  7. 后序遍历的递推公式：
  8. postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

时间复杂度为o（n）

二叉查找树（Binary Search Tree）

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。

特点:

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

理想情况下，时间复杂度为O(logn)。

AVL 树

AVL 树是平衡二叉查找树，增加和删除节点后通过树形旋转重新达到平衡。右旋是以某个节点为中心，

将它沉入当前右子节点的位置，而让当前的左子节点作为新树的根节点，也称为顺时针旋转。同理左旋

是以某个节点为中心，将它沉入当前左子节点的位置，而让当前的右子节点作为新树的根节点，也称为

逆时针旋转。

红黑树

什么是“平衡二叉查找树”？

二叉树中任意一个节点的左右子树的高度相差不能大于 1。

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树，

顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

  • 根节点是黑色的；
  • 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
  • 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
  • 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。红黑树的高度近似 log2n，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。

B 树和B+ 树的区别

B 树中每个节点同时存储 key 和 data，而 B+ 树中只有叶子节点才存储 data，非叶子节点只存储 key。

InnoDB 对 B+ 树进行了优化，在每个叶子节点上增加了一个指向相邻叶子节点的链表指针，形成了带

有顺序指针的 B+ 树，提高区间访问的性能。

B+ 树的优点在于：① 由于 B+ 树在非叶子节点上不含数据信息，因此在内存页中能够存放更多的 key，

数据存放得更加紧密，具有更好的空间利用率，访问叶子节点上关联的数据也具有更好的缓存命中率。

② B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可。而 B 树则需

要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有 B+树好。但是 B 树

也有优点，由于每个节点都包含 key 和 value，因此经常访问的元素可能离根节点更近，访问也更迅

速。

排序算法

冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

排序算法 时间复杂度 是否基于比较
冒泡、插入、选择 O(n2) 是
快排、归并 O(nlogn) 是
桶、计数、基数 O(n) 否