在拉钩1块钱抢了一个算法课程，讲的还不错，记下笔记。

一共有21节课，抽时间看，持续更新。

课程二维码在最后

第一讲

时间复杂度和代码结构的关系

一些经验性的结论

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

总结

复杂度通常包括时间复杂度和空间复杂度
在具体计算复杂度时需要注意：

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

时间复杂度与代码结构设计高度相关
空间复杂度与代码中数据结构的选择高度相关

第二讲

程序优化

降低复杂度，直观的思路：梳理流程，看其流程中是否有无效的计算或者无效的存储
常用的降低时间复杂度的方法：

  • 递归、二分法、排序算法、动态规划

降低空间负责度的核心思路：

  • 能用低复杂度的数据结构解决的问题，就千万不要用高复杂度的数据结构

数据结构连接时空

在程序开发中，连接时间和空间的桥梁就是数据结构
空间换时间：对于一个开发任务，如果能找到一种高效的数据组织方式，采用合理的数据结构就可以实现时间复杂度的再次降低，这通常会增加数据的存储量，也就是增加了空间的复杂度。

程序优化步骤

第一步，暴力解法

在没有任何时间、空间的约束下，完成代码任务的开发

第二步，无效操作处理

将代码中的无效计算，无效存储剔除，降低时间或空间复杂度

第三步，时空转换

设计合理的数据结构，完成时间复杂度向空间复杂度的转移

第三讲

数据处理的基本操作

即便是很复杂的代码，它对数据的处理也只有这3个基本操作：增删查

常用的分析方法可以参考下面三个步骤：

  1. 这段代码对数据进行了哪些操作？
  2. 这些操作中，哪个操作最影响效率，对时间复杂度的损耗最大？
  3. 哪种数据结构最能帮助你提高数据操作的使用效率？

数据操作与数据结构案例

查找

  • 根据元素的位置或索引来查找
  • 根据元素的数值特征来查找

新增

有两个可能：

  • 在这个复杂数据结构的最后，新增一条数据
  • 在这个复杂数据结构的中间某个位置，新增一条数据

区别：新增数据之后，是否会导致原有数据结构中数据位置顺序改变

删除

有两个可能

  • 在这个复杂数据结构的最后，删除一条数据
  • 在这个复杂数据结构的中间某个位置，删除一条数据

区别：删除数据之后，是否会导致原有数据结构中数据位置顺序改变

第四讲

什么是数据结构？

数据的组织方式

线性表

  • 单向链表
  • 双向链表
  • 循环链表
  • 双向循环链表

链表的优缺点：

  • 链表在新增和删除数据都可以在**O(1)**的时间复杂度内完成
  • 对于查找，无论是按照索引查找还是按照特征值查找，都需要对全部数据进行遍历，都是**O(n)**的时间复杂度

总结：

  • 链表虽然在新增和删除数据有优势，但是这种优势并不实用，因为在新增和删除数据时，都会伴随着一个查找操作。
  • 链表真正的价值在于，它对数据的存储方式是按照顺序的存储。
  • 如果数据元素不确定，且经常需要进行数据的新增和删除时，那么链表比较合适
  • 如果数据元素大小确定，删除插入操作并不多，那么数组可能更合适。

线性表案例

单向链表的翻转

代码实现

找出奇数链表中间位置节点的值

思路： 一个快指针一个慢指针，慢指针每次向后移动一个元素，快指针每次向后移动两个元素，当快指针的next是null时，慢指针所在就是中间节点。
代码实现

判断链表是否有环

思路： 一个快指针一个慢指针，当快慢指针相遇，说明链表有环。

代码实现

第五讲

顺序栈

栈的顺序存储可以借助数组来实现。

  1. 把数组首元素存在栈底，最后一个元素放在栈顶。
  2. 然后定义一个top指针来指示栈顶元素在数组中的位置。

链式栈

用链表的方式对栈表示，通常，可以把栈顶放在单链表头部。

顺序栈和链式栈的代码实现

栈与线性表

  • 相同点：操作原理完全相似，时间复杂度完全一样，都依赖当前位置的指针来进行数据对象的操作。
  • 区别：新增和删除的对象，只能是栈顶的数据结点。

栈的案例

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须与相同类型的右括号匹配，左括号必须以正确的顺序匹配。例如，{ [ ( ) ( ) ] } 是合法的，而 { ( [ ) ] } 是非法的。

思路： 使用栈的先进后出规则，遇到左括号进栈，遇到右括号出栈并且判断是否匹配。

代码实现

仿照浏览器的前进后退功能，利用栈来记录用户的浏览信息

思路：用一个前进栈和一个后退栈分别保存，前进时，前进栈出栈后退站栈进栈，后退时，后退栈出栈，前进栈进栈。

代码实现

总结

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

第六讲

队列是什么

队列也是一种特殊的线性表，与线性表的不同之处体现在对数据的增和删的操作上。

队列的特点：

  • 先进：队列的数据新增操作只能在末端进行，不允许在队列的中间某个节点新增数据。
  • 先出：队列的数据删除操作只能在始端进行，不允许在队列的中间某个节点后删除数据。

顺序队列：

  • 使用数据实现。新增O(1)，删除O(n)。
  • 使用循环队列。新增O(1)，删除O(1)。

链式队列：

队列的案例

约瑟夫环的问题

思路：构造一个循环队列（大于人数），定义计数变量i，开始出队，当i= m时，将这个人放入一个数组，如果i!=m，出队后再入队，继续上述步骤。

约瑟夫环代码实现

总结

在时间复杂度上

  • 循环队列和链式队列的新增删除操作都为O(1)
  • 在查找操作中，队列只能通过全局遍历的方式进行，需要O(n)的时间复杂度

在空间性能上

  • 循环队列必须有一个固定的长度，因此存在存储元素数量和空间浪费的问题。
  • 链式队列更为灵活一些。

第七讲

数组增删查的时间复杂度

  • 增加：尾部插入，时间复杂度O(1)，中间某处插入数据，时间复杂度为O(n)。
  • 删除：指定元素的删除，扫描全数组，时间复杂度为O(n)。
  • 查找：根据索引查找，时间复杂度O(1)，根据元素值查找，时间复杂度O(n)。

链表存在的价值是什么呢

  • 链表的长度的可变的，数组的长度是固定的，在申请数据长度时，就已经在内存中开辟了若干个空间。
  • 链表在内存中不是顺序存储的，可以充分利用内存空间。

第八讲

字符串的顺序存储和链式存储

顺序存储

是用一组地址连续的存储单元来存储串中的字符序列，一般用定长数组实现。

链式存储

因为字符串结构中，每一个元素都是一个字符，如果简单的将每个链节点存储为一个字符，就会造成很大的空间浪费。

所以可以在每个链节点存入多个字符，最后一个节点尾部用其他符号补全。

  • 如果字符串包含的数据量很大，就应该减少链节点，在每个节点放入更多的字符。
  • 如果需要对字符串进行大量的插入和删除数据，如果每个链节点包含的数据过多，操作就会变得很麻烦。

总结：链式存储没有顺序存储灵活。性能也没有顺序存储好。

字符串的操作

字符串的新增操作

  • 在中间新增，时间复杂度O(n)
  • 在尾部新增，时间复杂度O(1)

字符串的删除操作

  • 在中间删除，时间复杂度O(n)
  • 在尾部删除，时间复杂度O(1)

字符串的查找操作

例题1：假设要从主串 s = “goodgoogle” 中找到 t = “google” 子串。

思路：

  • 首先，我们从主串 s 第 1 位开始，判断 s 的第 1 个字符是否与 t 的第 1 个字符相等。

  • 如果不相等，则继续判断主串的第 2 个字符是否与 t 的第1 个字符相等。直到在 s 中找到与 t 第一个字符相等的字符时，然后开始判断它之后的字符是否仍然与 t 的后续字符相等。

  • 如果持续相等直到 t 的最后一个字符，则匹配成功。

  • 如果发现一个不等的字符，则重新回到前面的步骤中，查找 s 中是否有字符与 t 的第一个字符相等。

代码实现

例题2：假设有且仅有 1 个最大公共子串。比如，输入 a = “13452439”， b = “123456”。由于字符串 “345” 同时在 a 和 b 中出现，且是同时出现在 a 和 b 中的最长子串。因此输出 “345”。

思路：和上面的查找字符串是否包含的思路差不多。多了一个同步遍历的for循环，多维护两个变量存储最长子串的内容和长度。

代码实现

练习题

翻转字符串：给定一个字符串，逐个翻转字符串中的每个单词。例如，输入: “the sky is blue”，输出: “blue is sky the”。

思路：

  1. 第一眼看到翻转，我会想到用栈。

  2. 先创建一个临时栈和结果栈，遍历字符串入栈，遇到空格时，临时栈出栈并放入另一个栈中，最后入栈一个空字符串。

  3. 结果栈出栈，拼接为一个字符串并返回。

代码实现

第九讲

树是什么

树是由节点和边组成的，不存在环的一种数据结构。

二叉树

二叉树中，每个节点最多有两个分支。即每个节点最多有两个子节点，分别称作左子节点和右子节点。

满二叉树

除了叶子节点，所有节点都有两个子节点。

完全二叉树

除了最后一层以外，其它层的节点个数都达到最大，并且最后一层的叶子节点都靠左排列。

完全二叉树为什么叫完全二叉树？

从存储空间的利用率来看，不完全二叉树，按照顺序存储会浪费大量空间。。

链式存储

像链表一样，每个节点有三个字段，一个存储数据，另外两个分别存放指向左右两个节点的指针。

顺序存储

按照规律吧节点放进数组里。如果根节点从0开始，left=root*2+1 right=root*2+2；从1开始，left=root*2 right=root*2+1。

树的基本操作

树的遍历

  • 前序遍历：父节点->左子节点->右子节点
  • 中序遍历：左子节点->父节点->右子节点
  • 后序遍历：左子节点->右子节点->父节点

二叉树的前中后序遍历递归实现

二叉树的前中后序遍历栈实现

二叉树的遍历，时间复杂度为O(n)。

对于没有任何特殊性质的二叉树，删除和新增操作时间复杂度为O(1)。

查找操作，需要遍历每一个节点去判断，时间复杂度为O(n)。

二叉查找树

特性

  • 二叉查找树中任意一个节点，其左子节点的值一定小于这个节点的值。
  • 二叉查找树中任意一个节点，其右子节点的值一定大于这个节点的值。
  • 在二叉查找树中，会尽可能规避两个节点数值相等的情况。
  • 对二叉查找树进行中序遍历，就可以输出一个从小到大的有序数据队列。如下图所示，中序遍历的结果就是 10、13、15、16、20、21、22、26。

二叉查找树的查找操作
在利用二叉查找树执行查找操作时，我们可以进行以下判断：

  • 首先判断根结点是否等于要查找的数据，如果是就返回。

  • 如果根结点大于要查找的数据，就在左子树中递归执行查找动作，直到叶子结点。

  • 如果根结点小于要查找的数据，就在右子树中递归执行查找动作，直到叶子结点。

二叉查找树的插入操作

  • 情况一，如果要删除的结点是某个叶子结点，则直接删除，将其父结点指针指向 null 即可。
  • 情况二，如果要删除的结点只有一个子结点，只需要将其父结点指向的子结点的指针换成其子结点的指针即可。
  • 情况三，如果要删除的结点有两个子结点，则有两种可行的操作方式。
    • 第一种，找到这个结点的左子树中最大的结点，替换要删除的结点。
    • 第二种，找到这个结点的右子树中最小的结点，替换要删除的结点。

树的案例

输入一个字符串，判断它在已有的字符串集合中是否出现过?（假设集合中没有某个字符串与另一个字符串拥有共同前缀且完全包含的特殊情况，例如 deep 和 dee。）如，已有字符串集合包含 6 个字符串分别为，cat, car, city, dog,door, deep。输入 cat，输出 true；输入 home，输出 false。

思路：

  1. 首先把集合中的子串，按照字节查分，实现一个字典树。
  2. 判断输入字符串，按顺序匹配书中的节点，最后以为如果是叶子节点，则说明存在。

代码实现

总结

  • 二叉树的遍历操作，时间复杂度都是O(n)。
  • 二叉树的单纯增删操作，时间复杂度都是O(1)。(但是有特性的树增删一般伴随着查找或自平衡)。
  • 普通二叉树的查找操作时间复杂度是O(n)；二叉查找树的查找操作时间复杂度为O(logn)。

练习题

给定一棵树，按照层次顺序遍历并打印这棵树。

层序遍历代码实现

第十讲

哈希表的核心思想

哈希表的设计采用了函数映射的思想，将记录的存储位置与记录的关键字关联起来。这样的方式能够快速定位到自己想要查找的记录，而且不需要和表中存在的记录的关键字比较后再来进行查找。

数组的局限性是，他可以通过索引来查找，但是不能通过了数据的数值去查找。但是如果有一个方法可以使f(数值) = index,那就可以通过数值找索引，索引找值。

如何设计哈希函数

直接定制法

哈希函数为关键字到地址的线性函数。

H（key） = a * key + b

a，b是常数

数字分析法

假设关键字集合中的每个关键字key都是由s位数字组成（k1,k2,...,ks）

并从中提取均匀分布的若干位组成哈希地址

平方取中法

如果关键字每一位都有某些数字重复出现，并且频率很高

可以先求关键字的平方值，通过平方值扩大差异，然后取中间几位作为最终存储地址

折叠法

如果关键字的位数很多，可以将关键字分割为几个等长的部分

取它们的叠加和的值（舍去进位）作为哈希地址

除留余数法

预先设置一个数p，然后对关键字进行取余运算。

地址 = key % p

哈希冲突

无论哈希函数设计的多好，理论上来说只要输入的数据足够多，哈希冲突就必然会发生，所以哈希冲突只能减少，无法避免。

开放寻址法（开放定址法）

当遇到哈希冲突时，使用某种探测技术在哈希表形成一个探测序列，然后沿着这个探测序列一次查找下去，当碰到一个空单元时，则插入其中。

假设有一组关键字：[12,13,25,23]，采用哈希函数为除留余数法：H(key) = key % 11

0 1 2 3 4
插入12 12
插入13 13
插入25 25
插入23 冲突1 冲突2 冲突3 23

链地址法（链表法）

将哈希地址相同的记录存储在一张线性表中

哈希表的优缺点

优势：

  • 提供非常快速的插入-删除-查找操作。
  • 查找操作速度比树还要快

不足：

  • 哈希表的数据没有顺序的概念
  • 哈希表的key不允许重复

案例

例1：将关键字序列 {7, 8, 30, 11, 18, 9, 14} 存储到哈希表中。哈希函数为： H (key) = (key * 3) % 7，处理冲突采用线性探测法。

代码实现

例2：假设有一个在线系统，可以实时接收用户提交的字符串型关键字，并实时返回给用户累积至今这个关键字被提交的次数

这个如果使用语言内置的Object 或者 Map的话就几行代码，没什么好说的。

第十一讲

什么是递归

递归指的是在函数的定义中使用函数自身的方法。

递归有两层含义：

  • 递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，并且这些子问题可以用完全相同的解题思路来解决。
  • 递归问题的演化过程是一个对原问题从大到小进行拆解的过程，并且会有一个明确的终点（临界点），最后从这个临界点开始，把小问题的答案按照原路返回，原问题便得以解决。

递归的实现包含了两个部分：

  • 递归主体
  • 终止条件

递归的算法思想

递归的数学模型其实就是数学归纳法

数学归纳法

证明：

  1. 证明当n=1时命题成立
  2. 假设 n=m时，命题成立，name尝试推导出在n=m+1时命题也成立

所以当一个问题同时满足以下两个条件时，就可以使用递归的方法求解：

  1. 可以拆解为除了数据规模以外，求解思路完全相同的子问题
  2. 存在终止条件

二叉树的中序遍历分析

分析：

  1. 对二叉树中的任意结点
    1. 中序遍历左子树
    2. 打印这个结点
    3. 中序遍历右子树
  2. 当某个结点没有左子树或右子树时，终止。

当然，这个思路也适用与前序和后序遍历。

代码很简单

总结

写出递归代码的关键在于：写出递推公式和找出终止条件

  1. 找到将大问题分解为小问题的规律，并基于此写出递推公式
  2. 找出终止条件，就是当找到最简单的问题时，如何写出答案
  3. 将递推公式和终止条件翻译成代码

汉罗塔问题

汉诺塔问题是源于印度一个古老传说的益智玩具。

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

将这个问题拆解为三个小问题：

  1. 把从小到大的n-1个圆盘，从x移动到y

  2. 把最大的圆盘，从x移动到z

  3. 把从小到大的n-1个圆盘，从y移动到z

我们发现，第一和第三个小问题都是汉罗塔问题

然后我们要找到终止条件：

  • 当只剩一个圆盘时，它可以自由自动，所以递归终止。

我的思路和理解

  • 假设从小到大有五个盘子，编号为1、2、3、4、5
  • 我们把1~4当做一个整体t，这样只需要三步：
    • 把t移动到y
    • 把5移动到z
    • 把t移动到z
  • 而我们对t采用相同的操作，当t的盘子数量为1时，递归终止，因为最小的盘子可以随便移动。

代码实现

第十二讲

分治法

什么是分治法

分治法的思想就是分而治之

将一个大问题，分解成为n个子问题，采用同一种解法，递归的去解决这些子问题，再将每个子问题的解合并，就得到原问题的解。

分治问题的特征

  1. 难度在降低：即原问题的解决难度，随着数据的规模的缩小而降低
  2. 问题可分：原问题可以分解为若干个规模较小的同类型问题
  3. 解可合并：利用所有子问题的解，可以合并出原问题的解
  4. 相互独立：各个子问题之间相互独立，某个子问题的求解不会影响到另一个子问题

分治法的使用方法

分治法需要递归的分解问题再去解决问题，因此分治法在每轮递归上都包含了分解问题、解决问题、合并结果这三个步骤。

二分查找总结

  1. 二分查找的时间复杂度是O(logn)，这也是分治法普遍具备的特性。
  2. 二分查找的循环次数不确定，一般是达到某个条件就跳出循环。一般使用while循环加break跳出。
  3. 二分查找处理原问题必须是有序的

练习题

在一个有序数组中，查找出第一个大于 9 的数字，假设一定存在。例如，arr = { -1, 3, 3, 7, 10, 14, 14 }; 则返回 10。

代码实现

第十三讲

常见排序

代码实现

冒泡排序

时间复杂度：Ï

  • 当输入有序，时间复杂度O(n)
  • 当输入逆序，时间复杂度O(n*n)
  • 平均时间复杂度O(n*n)

空间复杂度

  • 不需要额外空间O(1)

当元素相同时，不做交换，是稳定的排序算法。

插入排序

时间复杂度：

  • 当输入有序，时间复杂度O(n)
  • 当输入逆序，时间复杂度O(n*n)
  • 平均时间复杂度O(n*n)

空间复杂度

  • 不需要额外空间O(1)

当元素相同时，不做交换，是稳定的排序算法。

归并排序

原理：

分治法

时间复杂度：

  • 平均时间复杂度O(nlogn)

空间复杂度

  • 要额外空间O(n)

是稳定的排序算法。

快速排序

原理：

分治法

时间复杂度：

  • 当输入有序，时间复杂度O(nlog(n))
  • 当输入逆序，时间复杂度O(n*n)
  • 大部分情况不会出现出入逆序，平均时间复杂度O(nlog(n))

空间复杂度

  • 不需要额外空间O(1)

是不稳定的排序算法

排序算法性能分析

时间复杂度 空间复杂度 是否稳定
冒泡排序 O(n*n) O(1) 稳定
插入排序 O(n*n) O(1) 稳定
归并排序 O(nlog(n)) O(n) 稳定
快速排序 O(nlog(n)) 最坏情况O(n*n) O(1) 不稳定

第十四讲

什么是动态规划

动态规划是一种运筹学方法，是在多轮决策过程中的最优方法

基本概念

  1. 策略，每轮的动作是决策，多轮决策合在一起常常被称为策略。
  2. 策略集合，由于每轮的决策动作都是一个变量，这就导致合在一起的策略也是一个变量。我们通常会称所有可能的策略为策略集合。因此，动态规划的目标，也可以说是从策略集合中，找到最优的那个策略。

动态规划的目标就是从策略集合中找到最优的几个策略

动态规划的基本方法

动态规划的解题方法并没有那么标准化，但它有一些宏观层面通用的方法论：

  1. 分阶段，将原问题划分成几个子问题。一个子问题就是多轮决策的一个阶段，它们可以是不满足独立性的。
  2. 找状态，选择合适的状态变量 Sk。它需要具备描述多轮决策过程的演变，更像是决策可能的结果。
  3. 做决策，确定决策变量 uk。每一轮的决策就是每一轮可能的决策动作，例如 D2 的可能的决策动作是 D2 -> E2 和 D2 -> E3。
  4. 状态转移方程。这个步骤是动态规划最重要的核心，即 sk+1= uk(sk) 。
  5. 定目标。写出代表多轮决策目标的指标函数 Vk,n。
  6. 寻找终止条件。

一般而言，具有如下几个特征的问题，可以采用动态规划求解：

  1. 最优子结构。它的含义是，原问题的最优解所包括的子问题的解也是最优的。例如，某个策略使得 A 到 G 是最优的。假设它途径了 Fi，那么它从 A 到 Fi 也一定是最优的。
  2. 无后效性。某阶段的决策，无法影响先前的状态。可以理解为今天的动作改变不了历史。
  3. 有重叠子问题。也就是，子问题之间不独立。这个性质是动态规划区别于分治法的条件。如果原问题不满足这个特征，也是可以用动态规划求解的，无非就是杀鸡用了宰牛刀。

最短路径问题

ps：这个有点难呀。。本子上画了好久才理清推导过程

代码实现

第十六讲

解决问题的方法论：

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

第十八讲

给定一个链表: 1 -> 2 -> 3 -> 4 -> 5, 和 n = 2。当删除了倒数第二个节点后，链表变为 1 -> 2 -> 3 -> 5。时间复杂度要求为 O(n)

思路： 其实比较简单，使用快慢指针，假设删除倒数第n个结点，那么快指针就比慢指针先移动n次，然后快慢指针一起移动，最后慢指针的下一个结点就是要删除的结点。

代码实现

END~

课程二维码