2018-12-17

极客时间-算法-学习总结

系统高效地学习数据结构与算法

什么是数据结构？什么是算法?

广义定义：数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

狭义定义：指的就是著名的数据结构和算法实现（大多数相关书籍里面内容），比如数组，队列，栈，链表，快速排序，二分查找等。

数据结构和算法的关系

数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。因此，无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。

学习重点

必须掌握一个数据结构与算法中最重要的概念——复杂度分析。

数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。

数据结构和算法图示：

对于非算法工程师来说，并不需要掌握图里面的所有知识点，要学会找重点来学习。作者总结了如下20个常用的数据结构和算法：

10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树。
10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法，动态规划，字符串匹配算法。

每种数据结构和算法的学习重点：

来历
自身的特点
适合解决的问题
实际的应用场景

一些技巧

边学边练，适度刷题
多问，多思考，多互动
设立目标，贵在坚持
反复迭代，不断沉淀

复杂度分析

复杂度分析用来解决算法的执行效率和空间占用情况的，这里的空间占用，指的是内存空间的占用。

为什么需要复杂度分析

通过统计和监控确实可以分析算法的执行效率和资源消耗。该方法被称为事后分析法，但是它有一定的局限性。

测试结果非常依赖测试环境。
测试结果受数据规模的影响较大。

大O复杂度分析法

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

n表示数据规模
T(n)表示代码执行时间
f(n)表示每行代码执行时间总和

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也称为渐进时间复杂度（asymptotic time complexity）。

当数据规模n很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。

时间复杂度分析

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

几种常见时间复杂度实例分析

O(1)

O(1)只是常量级时间复杂度的表示，只要算法的执行时间不随着数据规模增加而增加，那么时间复杂度就是O(1)。

O(m + n) 和 O(m * n)

O(m + n)表示算法的时间复杂度是由2个数据规模决定的，事前不能确定n和m的大小关系, 所以不能简单的省略其中任何一个（加法法则失效）。但是乘法法则依然起作用。

空间复杂度

空间复杂度表示算法的使用的存储空间随数据规模增长的变化趋势，所以也称为渐进空间复杂度（asymptotic space complexity）。

常见的空间复杂度有：O(1), O(n), O(n2)，像 O(logN)和O(NlogN)比较少见。

最好，最坏时间复杂度

最好（best case time complexity），最坏（worst case time complexity），平均（average case time complexity）时间复杂度表示算法在不同情况下的执行效率。

平均情况时间复杂度

加权平均值也称为期望值

平均情况时间复杂度 也称为：加权平均时间复杂度 或 期望时间复杂度

均摊时间复杂度

摊还分析(平摊分析)

数组

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

线性表（Linear List）

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

非线性表

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

问题

为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢？

从数组存储的内存模型上来看，下标最确切的定义应该是“偏移（offset）”。前面也讲到，如果用a来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式:

1	a[k]_address = base_address + k * type_size

但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：

1	a[k]_address = base_address + (k-1)*type_size

从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。

C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，为了在一定程度上减少 C 语言程序员学习 Java 的学习成本，因此继续沿用了从 0 开始计数的习惯。实际上，很多语言中数组也并不是从 0 开始计数的，比如 Matlab。甚至还有一些语言支持负数下标，比如 Python。

补充：

二维数组内存寻址：
对于 m x n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：
address = base_address + ( i x n + j) x type_size

链表

链表 VS 数组

数组简单易用，连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。
数组的缺点是大小固定; 链表本身没有大小的限制，天然地支持动态扩容，这也是链表和数组最大的区别。
如果你的程序运行环境内存有限，使用数组更合适一些。

总结

单链表节省内存，但是操作效率总体低。
双向链表费内存，但是操作效率总体高，方便。
双向链表在实际的工程实践中使用较为广泛，是一种以空间换时间的思想。

总结：如何优雅的写出链表代码？6大学习技巧

一、理解指针或引用的含义

1.含义：将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）。
2.示例：
p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。
p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。

二、警惕指针丢失和内存泄漏（单链表）

1.插入节点
在节点a和节点b之间插入节点x，b是a的下一节点，，p指针指向节点a，则造成指针丢失和内存泄漏的代码：

1 2	p—>next = x; x—>next = p—>next;

显然这会导致x节点的后继指针指向自身。
正确的写法是2句代码交换顺序，即：

1 2	x—>next = p—>next; p—>next = x;

2.删除节点

在节点a和节点b之间删除节点b，b是a的下一节点，p指针指向节点a：p—>next = p—>next—>next;

三、利用“哨兵”简化实现难度

1.什么是“哨兵”？
链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。
2.未引入“哨兵”的情况
如果在p节点后插入一个节点，只需2行代码即可搞定：

1 2	new_node—>next = p—>next; p—>next = new_node;

但，若向空链表中插入一个节点，则代码如下：

1
2
3

if(head == null){
    head = new_node;
}

如果要删除节点p的后继节点，只需1行代码即可搞定：

1	p—>next = p—>next—>next;

但，若是删除链表的最有一个节点（链表中只剩下这个节点），则代码如下：

1
2
3

if(head—>next == null){
head = null;
}

从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”节点来解决这个问题。

3.引入“哨兵”的情况
“哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。

4.“哨兵”还有哪些应用场景？
这个知识有限，暂时想不出来呀！但总结起来，哨兵最大的作用就是简化边界条件的处理。

四、重点留意边界条件处理

经常用来检查链表是否正确的边界4个边界条件：
1.如果链表为空时，代码是否能正常工作？
2.如果链表只包含一个节点时，代码是否能正常工作？
3.如果链表只包含两个节点时，代码是否能正常工作？
4.代码逻辑在处理头尾节点时是否能正常工作？

五、举例画图，辅助思考

核心思想：释放脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。

六、多写多练，没有捷径

5个常见的链表操作：
1.单链表反转
2.链表中环的检测
3.两个有序链表合并
4.删除链表倒数第n个节点
5.求链表的中间节点

栈

一、什么是栈？

1.后进者先出，先进者后出，这就是典型的“栈”结构。
2.从栈的操作特性来看，是一种“操作受限”的线性表，只允许在一端插入和删除数据。

二、为什么需要栈？

1.栈是一种操作受限的数据结构，其操作特性用数组(顺序栈)和链表(链式栈)均可实现。
2.任何数据结构都是对特定应用场景的抽象，数组和链表虽然使用起来更加灵活，但却暴露了几乎所有的操作，难免会引发错误操作的风险。
3.所以，当某个数据集合只涉及在某端插入和删除数据，且满足后进者先出，先进者后出的操作特性时，我们应该首选栈这种数据结构。

三、如何实现栈？

1.栈的API

public class Stack<Item> {
//压栈
public void push(Item item){}
//弹栈
public Item pop(){}
//是否为空
public boolean isEmpty(){}
//栈中数据的数量
public int size(){}
//返回栈中最近添加的元素而不删除它
public Item peek(){}
}

2.数组实现（自动扩容）

时间复杂度分析：根据均摊复杂度的定义，可以得数组实现（自动扩容）符合大多数情况是O(1)级别复杂度，个别情况是O(n)级别复杂度，比如自动扩容时，会进行完整数据的拷贝。
空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量存储空间，所以O(1)级别。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

3.链表实现

时间复杂度分析：压栈和弹栈的时间复杂度均为O(1)级别，因为只需更改单个节点的索引即可。
空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量存储空间，所以O(1)级别。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

四、栈的应用

1.栈在函数调用中的应用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将其中的临时变量作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

2.栈在表达式求值中的应用（比如：34+13*9+44-12/3）

利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。

3.栈在括号匹配中的应用（比如：{}{()}）

用栈保存为匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。
当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。

4.如何实现浏览器的前进后退功能？

我们使用两个栈X和Y，我们把首次浏览的页面依次压如栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据一次放入Y栈。当点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，说明没有页面可以继续后退浏览了。当Y栈没有数据，那就说明没有页面可以点击前进浏览了。

五、思考

我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？

答：因为函数调用的执行顺序符合后进者先出，先进者后出的特点。比如函数中的局部变量的生命周期的长短是先定义的生命周期长，后定义的生命周期短；还有函数中调用函数也是这样，先开始执行的函数只有等到内部调用的其他函数执行完毕，该函数才能执行结束。
正是由于函数调用的这些特点，根据数据结构是特定应用场景的抽象的原则，我们优先考虑栈结构。

2.我们都知道，JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？

答：JVM里面的栈和我们这里说的是一回事，被称为方法栈。和前面函数调用的作用是一致的，用来存储方法中的局部变量。

队列

队列也是一种操作受限的线性表结构，支持在在队列的两端进行操作：

队首，出队
队尾，入队

队列的实现通常有两种方式：

数组实现（顺序队列），通常通过循环数组实现。
链表实现（链式队列）

队列在实现上可以分为：

有界队列，可以一直入队，知道不能再获取系统资源为止。
无界队列，队列的容量有限，超过固定容量后入队失败。

队列的分类：

普通队列
阻塞队列
并发队列(无锁并发队列Disruptor)
优先级队列
双端队列
…..

递归

如何理解“递归”？

递归是一种应用非常广泛的编程技巧。很多数据结构和算法的编码实现都要用到递归，比如归并排序，快排，DFS 深度优先搜索、前中后序二叉树遍历等等

递归代码的外在表现就是函数自己调用自己。递归代码的执行分为：递和归两个阶段，递的阶段可以看做是分解问题为子问题的过程，归的阶段可以看做是求解子问题后，合并子问题的解来求解原问题的过程。

递归执行条件

递归需要满足的三个条件：

一个问题的解可以分解为几个子问题的解（这里需要注意：几个子问题的数据规模可能不同）
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
存在递归终止条件

如何编写递归代码？

写递归代码最关键的是写出递推公式，找到终止条件。有了公式，剩下的就是将公式翻译为代码了，比较简单。

在抽象递推公式时，需要用数学思维来定义问题和求解问题。

一个递归求解例子：

假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？

这个问题可以这么理解：

要走到第n个台阶，那么必须是从n-1或n-2个台阶才能走到。那么所有走到第n个台阶的走法整体可以分为：所有走到n-1的走法和所有走到n-2的走法的和。先不用管是如何走到n-1和n-2的，我们可以假设走到n-1或n-2的走法已经知道了。
用f(n)表示n个台阶走法总数，那么有公式f(n) = f(n-1) + f(n-2)

根据上面的分析，得到递推公式如下：

1
2
3

f(n) = f(n-1)+f(n-2)
f(1) = 1
f(2) = 2 (一步一步走，直接走2个台阶)

递归代码实现：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

迭代代码实现：

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  int ret = 0;
  int pre = 2;
  int prepre = 1;
  for (int i = 3; i <= n; ++i) {
    ret = pre + prepre;
    prepre = pre;
    pre = ret;
  }
  return ret;
}

递归总结

优缺点

1.优点：代码的表达力很强，写起来简洁。
2.缺点：空间复杂度高、有堆栈溢出风险（限制递归深度，或用循环方式解决）、存在重复计算（可以通过保存计算结果，通过查表来解决重复）、过多的函数调用会耗时较多等问题。

调试递归

1.打印日志发现，递归值。
2.结合条件断点进行调试

如果实现递归

1.递归代码编写

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

2.递归代码理解

对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。（人脑比不过计算机）
那该如何理解递归代码呢？

如果一个问题A可以分解为若干个子问题B、C、D，你可以假设子问题B、C、D已经解决。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

如何将递归改写为非递归代码？

从理论上讲，所有的递归代码都可以改写为迭代循环的非递归写法。如何做？抽象出递推公式、初始值和边界条件，然后用迭代循环实现。(其实就是将每次循环看为一次函数调用，通过局部变量模拟函数调用的调用参数)

排序1

排序算法太多了，需要掌握最经典的、最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

如何分析一个“排序算法”？

排序算法的执行效率

最好情况、最坏情况、平均情况时间复杂度(还需要了解它们分别对应的原始数据顺序模型)
时间复杂度的系数、常数、低阶（因为日常的软件开发中面对的数据规模都是很大，所有这些项不能简单忽律）
比较次数和交换（或移动）次数

排序算法的内存消耗

排序算法除了分析时间复杂度，还需要分析空间复杂度。

原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。

排序算法的稳定性

针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

稳定排序算法很有用，在需要根据多个维度排序时很重要。例如在SQL中多个字段的排序。

有序度和逆序度

有序度是数组中具有有序关系的元素对的个数

1	有序元素对：a[i] <= a[j], 如果i < j。

对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2，也就是 15

逆序度的定义正好跟有序度相反（默认从小到大为有序)

1	逆序元素对：a[i] > a[j], 如果i < j。

逆序度 = 满有序度 - 有序度

排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

冒泡排序

// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

插入排序

插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

// 插入排序，a表示数组，n表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾

1
2

排序总结

冒泡VS插入

冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。

但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个。

冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

课后题

特定算法是依赖特定的数据结构的。冒泡，插入，选择都是基于数组实现的。如果数据存储在链表中，这三种排序算法还能工作吗？如果能，那相应的时间、空间复杂度又是多少呢？

答案：

一般而言，考虑只能改变节点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系数会减小，选择排序无明显变化。

排序2

归并排序和快速排序是时间复杂度为 O(nlogn) 的排序算法。这两种排序算法适合大规模的数据排序，在日常开发中使用较多。

归并排序和快速排序都用到了分治思想。

归并排序的原理

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

伪代码实现：

// 归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
  merge_sort_c(A, 0, n-1)
}

// 递归调用函数
merge_sort_c(A, p, r) {
  // 递归终止条件
  if p >= r  then return

  // 取p到r之间的中间位置q
  q = (p+r) / 2
  // 分治递归
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 将A[p...q]和A[q+1...r]合并为A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}

排序3

本文标题:极客时间-算法-学习总结

文章作者:kongwenqiang

发布时间:2018-12-17, 09:05:50

最后更新:2020-05-24, 19:46:21

原始链接:https://leokongwq.github.io/2018/12/17/geektime-algo-summary.html

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。