目录
- 【基础】1、复杂度
- 【基础】2、动态数组
- 【基础】3、链表（一）
- 【基础】4、链表（二）
- 【基础】5、链表（三）
- 【基础】链表相关算法
- 【基础】6、栈与队列
- 【基础】栈与队列相关算法
- 【基础】7、二叉树（一）
- 【基础】8、二叉树（二）
- 【基础】9、二叉树（三）
- 【基础】10、AVL树
- 【基础】11、B树
- 【基础】12、红黑树
- 【基础】13、集合与映射
- 【基础】14、哈希表（一）
- 【基础】15、哈希表（二）
- 【基础】16、二叉堆
- 【基础】17、优先级队列
- 【基础】18、哈夫曼编码
- 【基础】19、Trie
【基础】1、复杂度
什么是算法
算法是用于解决特定问题的一系列的执行步骤
比如求和，求平均
斐波那契数列
斐波那契数列计算
递归方式
循环方式
如何评判一个算法的好坏？
事后统计法
大O记法
时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
空间复杂度（space complexity）：估算所需占用的存储空间
大O表示法
忽略常数、系数、低阶
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
fib函数复杂度分析
递归方式：O(2^n)
循环方式: O(n)
算法的优化方向
1、用尽量少的存储空间
2、用尽量少的执行步骤（执行时间）
3、根据情况，可以空间换时间或者时间换空间
【基础】2、动态数组
什么是数据结构
数据结构是计算机存储、组织数据的方式
线性结构
数组、链表、栈、队列、哈希表
树形结构
二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集
图形结构
邻接矩阵、邻接表
线性表
数组：内存空间连续
可能会造成内存空间的浪费
自实现动态数组
接口设计
需要注意的点
数组的扩容处理
数组内对象的内存处理
【基础】3、链表（一）
链表
链式存储的线性表，所有元素的内存地址不一定是连续的
链表的设计：
linkedList
size
first
节点
element
next
链表实现动态数组
算法训练
环形链表
快慢指针
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != nullptr && faset->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast ){ return true};
}
反转一个链表
递归方式
temp = oldHead->next
newHead = 递归函数(temp)
temp->next = oldHead
oldHead -> next = nullptr
return newHead
迭代方式
//a -> b -> c -> d -> e
newHead = nil;
//下面是循环内代码
while(head != nullPtr){
temp = head->next;
head->next = newHead;
newHead = head;
head = temp;
}
删除链表中的节点
//node是要删除的节点
node->val = node->next->val;
node->next = node->next->next;
【基础】4、链表（二）
虚拟头节点
为了统一处理可以增加一个虚拟头节点
node
null
next
动态数组的缩容
动态数组的缩容
扩容与缩容时机选择不当,容易引起复杂度震荡
双向链表
双向链表的设计
linkedList
size
first
last
node
element
prev
next
双向链表的优缺点
与单向链表相比减少了一半的操作数量
内存占用比单向链表大
使用
查询较多:动态数组
添加删除较多:链表
复杂度分析
最好情况复杂度
最坏情况复杂度
平均情况复杂度
动态数组
添加:O(n)
删除:O(n)
查询:O(1)
链表
添加:O(n)
删除:O(n)
查询:O(n)
均摊复杂度
【基础】5、链表（三）
单向循环链表
可画出示意图
双向循环链表
可画出示意图
约瑟夫问题
静态链表
数组的每个元素存放 2 个数据：值、下个元素的索引
【基础】链表相关算法
1_83_删除排序链表中的重复元素
2_141_环形链表
思想:快慢指针
3_160_相交链表
思想:两个链表拼接
4_203_移除链表元素
虚拟头结点
记录当前节点的前一个节点
当前节点要删除,就用前一个节点实现
pre.next = pre.next.next
5_206_反转链表
递归方式
迭代方式
思想:借用一个temp临时节点
6_234_回文链表
思想:寻找链表的中间节点
7_237_删除链表中的节点
变相删除,用下个节点的val替换当前节点的val
删除下个节点
8_876_链表的中间结点
思想:快慢指针
9_面试题02.07.链表相交
思想:两个链表拼接
10_剑指Offer52.两个链表的第一个公共节点
思想:两个链表拼接
【基础】6、栈与队列
栈
简介
栈是一种特殊的线性表，只能在一端进行操作
后进先出的原则，Last In First Out，LIFO
入栈
出栈
接口设计
栈的应用
浏览网站的后退和前进
修图软件的回退和撤销
队列
简介
队列是一种特殊的线性表，只能在头尾两端进行操作
先进先出的原则，First In First Out，FIFO
队尾入队
队头出队
接口设计与实现
双端队列
循环队列
用数组实现
栈与队列的相互实现
【基础】栈与队列相关算法
1_20_有效的括号
出现右侧字符
此时栈顶若为空,返回false
栈顶非空,但不能匹配该字符,返回false
出现左侧字符
入栈
2_150_逆波兰表达式求值
如果不是符号就入栈
如果是符号
取出栈顶的两个元素进行计算
将计算结果入栈
最终栈里剩余的就是结果
3_155_最小栈
使用两个栈
一个栈存放数据
一个栈记录当前时刻的最小值
4_232_用栈实现队列
使用左右两个栈
入队进左栈
出队出右栈
5_739_每日温度
利用两个嵌套的循环和一个栈,一个数组
for循环:拿到温度列表的索引
while循环:用当前索引currentIdx和栈顶索引topIdx比较
当前索引对应的温度值高,找到栈顶索引对应的天数 currentIdx - topIdx,并将结果放入数组
当前索引对应的温度值低,currentIdx入栈
进入for循环的下一轮
最终result内放置的就是结果
6_856_括号的分数
准备一个栈,先入栈一个0
如果是 ( 入栈 0
如果是 ) 将栈顶的两个元素出栈
current = 栈顶 pre = 次栈顶
如果current == 0 ,pre += 1 后入栈
如果current != 0, pre += 2*current 后入栈
最终栈顶的元素就是要计算的分数
7_225_用队列实现栈
8_59_剑指Offer滑动窗口的最大值
使用两个循环,一个双端队列存放索引,一个数组存放结果
队列为空时
索引直接入队
队列不为空时
当前索引对应的值与队列尾部(右侧)索引对应的值比较
当前值大,队尾出队,当前值队尾入队
当前值小,直接队尾入队
以上操作保证了队头(左侧)始终是最大值
检查队头的合法性,是否再范围内
在范围内,队头就是最大值,放入结果数组
不在范围内,队头出队一次,当前队头就是最大值,放入结果数组
【基础】7、二叉树（一）
树形结构
树的分类
二叉树
多叉树
树相关的概念
节点
节点的位置
根节点,父节点,子节点,兄弟节点
节点的度
叶子节点,非叶子节点
节点的深度
节点的高度
树
子树,左子树,右子树
有序树,无序树,森林
树的度,树的深度 == 树的高度
树的层数
二叉树
二叉树的特点
最大度为2
二叉树的性质
节点个数与二进制数据对应
节点个数关系
总结点n = n0+n1+n2;
总边数T = n1 + 2*n2;
总结点n = T+1；
因此 n0 = n2 + 1
真二叉树
没有度为1的节点
满二叉树
完全二叉树
度为1的节点要么0个要么1个
二叉搜索树
思考
动态数组,增删改查的复杂度
排序的动态数组,增删改查的复杂度
有没有更好的方案?
二叉搜索树
二叉搜索树
特点
二叉搜索树接口设计
添加节点
元素的比较方案设计
允许外界传入一个 Comparator 自定义比较方案
如果没有传入 Comparator，强制认定元素实现了 Comparable 接口
【基础】8、二叉树（二）
二叉树遍历
线性数据结构的遍历比较简单
正序遍历
逆序遍历
二叉树的遍历
前序遍历
中序遍历
升序：左子树、根节点、右子树
降序：右子树、根节点、左子树
后续遍历
层序遍历
将根节点入队
循环执行以下操作，直到队列为空
将队头节点 A 出队，进行访问
将 A 的左子节点入队
将 A 的右子节点入队
二叉树遍历应用
前序遍历
树状结构展示（注意左右子树的顺序）
中序遍历
二叉搜索树的中序遍历按升序或者降序处理节点
后序遍历
适用于一些先子后父的操作
层序遍历
计算二叉树的高度
判断一棵树是否为完全二叉树
根据遍历结果重构二叉树
以下结果可以保证重构出唯一的一棵二叉树
前序遍历 + 中序遍历
后序遍历 + 中序遍历
练习
前序遍历:4 2 1 3 6 5
中序遍历:1 2 3 4 5 6
遍历相关练习
一. 反转一个二叉树
层序遍历
遍历到节点时,反转左右子树
二. 计算树的高度
方案一:递归方式
计算左子树的高度
计算右子树的高度
较高的高度加1,就是整棵树的高度
方案二:层序遍历的方式
int height = 0;//默认值
int currentLevelSize = 1;//当前层的节点数量,第一层为1
当currentLevelSize减为0时,height++;
三. 是否为完全二叉树
层序遍历的方式
BOOL isLeaf = false;//搞一个标记
判断node左右节点的存在情况
左存在,右存在
继续
左存在,右不在
以后都是叶子节点
若出现非叶子节点就不是完全二叉树
左不在,右存在
不是完全二叉树
左不在,右不在
以后都是叶子节点
若出现非叶子节点就不是完全二叉树
前驱与后继节点
一. 前驱节点
中序遍历时的前一个节点
查找前驱节点
左节点存在
找到左节点,一路向右
左节点不存在
找第一个向左走的父节点
二. 后继节点
中序遍历时的后一个节点
查找后继节点
右节点存在
找到右节点,一路向左
右节点不存在
找第一个向右走的父节点
【基础】9、二叉树（三）
二叉搜索树删除
叶子节点
直接删除
度为1的节点
父节点直接指向其子节点
度为2的节点
先找到节点的前驱(或者后继)节点
用前驱(或者后继)节点的值覆盖原节点
删除前驱(或者后继)节点
平衡二叉搜索树
一. 复杂度分析
添加,删除节点都有可能使二叉搜索树退化成链表
复杂度由O(logn)变为了O(n)
二. 平衡
改进二叉搜索树
节点的添加、删除顺序是无法限制的，可以认为是随机的
所以方案是,在添加或删除节点之后进行调整,使树恢复 合理 平衡
用尽量少的调整次数达到适度平衡即可
达到理想平衡(完全二叉树的高度是最小的),调整的次数过多,反而会增加时间复杂度
平衡二叉搜索树
AVL树
红黑树
【基础】10、AVL树
AVL树
平衡因子(1 0 -1)
左子树高度 - 右子树高度
添加删除完成后变为AVL树
变化依据是平衡因子
添加导致的失衡
失衡
可能会导致所有祖先节点都失衡
父节点和非祖先节点不会失衡
旋转
LL – 右旋转（单旋）
RR – 左旋转（单旋）
LR – RR左旋转，LL右旋转（双旋）
RL – LL右旋转，RR左旋转（双旋）
理解旋转
统一处理旋转
删除导致的失衡
失衡
可能会导致父节点或祖先节点失衡（只有1个节点会失衡），
其他节点，都不可能失衡
总结
添加
可能会导致所有祖先节点都失衡
只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡【仅需 O(1) 次调整】
删除
可能会导致父节点或祖先节点失衡（只有1个节点会失衡）
恢复平衡后，可能会导致更高层的祖先节点失衡【最多需要 O(logn) 次调整】
平均时间复杂度
搜索：O(logn)
添加：O(logn)，仅需 O(1) 次的旋转操作
删除：O(logn)，最多需要 O(logn) 次的旋转操作
【基础】11、B树
B树介绍
多路搜索树，多用于文件系统、数据库的实现
m阶B树性质
m阶B树就是有m个分叉
根节点存储元素数量
[1 m-1]
非根节点存储元素数量
[┌ m/2 ┐ − 1 m-1]
如果 m = 2，那B树是什么样子？
二叉树
你猜数据库实现中一般用几阶B树？
200 ~ 300
B树 VS 二叉搜索树
B树 和 二叉搜索树，在逻辑上是等价的
多代节点合并，可以获得一个超级节点
搜索
先在节点内部搜索
再去子节点搜索
添加
新添加的元素必定是添加到叶子节点
上溢操作,有可能连续上溢
删除
删除原理
叶子节点直接删除
非叶子节点,用其前驱节点的值覆盖,删除前驱节点
真正的删除元素都是发生在叶子节点中
下溢操作
兄弟可借:向兄弟节点借一个
兄弟不可借:父节点下溢,有可能连续下溢
4阶B树
如果先学习4阶B树（2-3-4树），将能更好地学习理解红黑树
所有节点能存储的元素个数 x ：1 ≤ x ≤ 3
【基础】12、红黑树
红黑树介绍
红黑树性质,满足这些性质就能保证平衡
1.节点是 RED 或者 BLACK
2.根节点是 BLACK
3.叶子节点（外部节点，空节点）都是 BLACK
4.RED 节点的子节点都是 BLACK
✓ RED 节点的 parent 都是 BLACK
✓ 从根节点到叶子节点的所有路径上不能有 2 个连续的 RED 节点
5.从任一节点到叶子节点的所有路径都包含相同数目的 BLACK 节点
红黑树与4阶B树
将黑节点看作是4阶B树的节点
添加
新添加的节点为红色,这样能尽快满足5条性质
添加的几种情形
根节点
直接染黑即可
非根节点,共12中情况
4种情况不需要处理
4种情况需要旋转处理
4种情况需要上溢操作
删除
B树中，最后真正被删除的元素都在叶子节点中
删除的几种情形
删除红色节点
直接删除不用作任何调整
删除黑色节点
情形一：拥有 2 个 RED 子节点的 BLACK 节点
不可能直接删除,会删除其前驱或后继节点
情形二：拥有 1 个 RED 子节点的 BLACK 节点
用红色子节点替代,并将红色染为黑色
情形三：为叶子节点的BLACK 节点（最复杂的一种情况）
兄弟节点是黑
兄弟节点可借用
父节点红
父节点黑
兄弟节点不可借用
父节点红
父节点黑
兄弟节点是红
将兄弟节点转为黑再处理
红黑树总结
为何那5条性质，就能保证红黑树是平衡的？
那5条性质，可以保证 红黑树 等价于 4阶B树
AVL树 vs 红黑树
AVL树平衡标准比较严格红黑树的平衡标准比较宽松
搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树
相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树
红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树
【基础】13、集合与映射
集合
特点
不存放重复的元素
常用于去重
实现方式
列表
链表
平衡二叉搜索树(需要传入比较器或使用默认比较器)
映射
特点
Map 在有些编程语言中也叫做字典
key : value
实现方式
列表
链表
平衡二叉搜索树(需要传入比较器或使用默认比较器)
Map 与 Set
Map 的所有 key 组合在一起，其实就是一个 Set
因此，Set 可以间接利用 Map 来作内部实现
用Map实现Set会造成内存的浪费
【基础】14、哈希表（一）
TreeMap分析
时间复杂度（平均）
添加、删除、搜索：O(logn)
特点
Key 必须具备可比较性
元素的分布是有顺序的
不考虑顺序、不考虑 Key 的可比较性，Map 有更好的实现方案，平均时间复杂度可以达到 O(1)
那就是采取哈希表来实现 Map
哈希表
设计一个写字楼的通讯录
创建一个数组companies ,座机号key做数组的索引,公司名称value作为放入数组的元素
添加、删除、搜索的时间复杂度为O(1),但是浪费了大量的空间
其实数组 companies 就是一个哈希表，典型的【空间换时间】
哈希表
key -> 哈希函数生成hash值 -> 与 列表的长度&hash值 运算得到索引index -> 该索引处放入value
列表的长度设计有要求:2^n. 因为2^n -1 = 1111 1111 全为1
哈希冲突
不同的key,计算出相同的index
解决方式:
开放定址法
按照一定规则探测
再哈希法
设计多个哈希函数
链地址法
通过链表将同一index的元素串起来
解决哈希冲突的方案
jdk采用的是
单向链表 / 红黑树
元素较少时用链表,较多时切换成红黑树
哈希函数
先生成 key 的哈希值（必须是整数）
再让 key 的哈希值跟数组的大小进行相关运算，生成一个索引值
为了提高效率，可以使用 & 位运算取代 % 运算【前提：将数组的长度设计为 2 的幂（2^n）】
哈希值
整数的哈希值
整数本省
浮点数的哈希值
将存储的二进制格式转为整数值
Long和Double的哈希值
高32bit 和 低32bit 混合计算出 32bit 的哈希值
充分利用所有信息计算出哈希值
字符串的哈希值
jack 的哈希值可以表示为
j ∗ n^3 + a ∗ n^2 + c ∗ n^1 + k ∗ n^0，
等价于 [ ( j ∗ n + a ) ∗ n + c ] ∗ n + k
乘数 n 为 31,统计计算得到
自定义对象的哈希值
hash = property1.hashCode
hash = hash * 31 + property2.hashCode
hash = hash * 31 + property3.hashCode
...
哈希值的进一步处理
扰动计算
length: 1111 1111 1111 1111
hashcode1:0100 0000 0000 0000 1010 1010 1010 1010
hashcode2:0110 0000 0000 0000 1010 1010 1010 1010
没有扰动计算上边两个哈希值产生的索引是一样的
哈希表内的红黑树
红黑树的比较逻辑设计
哈希表的扩容
装填因子达到某一值,进行扩容
创建一个新的列表
将就的节点,一个一个的放入新的列表
【基础】15、哈希表（二）
TreeMap vs HashMap
何时选择TreeMap？
元素具备可比较性且要求升序遍历（按照元素从小到大）
何时选择HashMap？
无序遍历
LinkHashMap
在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的
一、添加节点
二、删除节点
三、更换节点的链接位置
【基础】16、二叉堆
思考
设计一种数据结构
添加元素
获取最大值
删除最大值
数组,链表,二叉树都可以办到
更优的数据结构:二叉堆
二、Top K问题
100万数据中选出前100个数据
堆
二叉堆
多叉堆
...
二叉堆
类型
大顶堆
小顶堆
实现方式
与完全二叉树结构一样
底层可以用数组实现
添加
添加到数组末尾
上滤操作
删除
数组末尾元素替换掉堆顶元素
下滤操作
批量建堆
一、自上而下的上滤
所有节点的高度之和O(nlogn)
二、自下而上的下滤
所有节点的深度之和O(n)
三、如何构建一个小顶堆
通过修改比较逻辑构建小顶堆
Top K 问题
在n个数据中查找最大的前k个数据,n远远大于k
用n的前k个数据构建一个小顶堆
第k+1个数据开始,如果大于堆顶,就替换掉堆顶
最终堆内留下的k个数据就是最大的前k个数据 O(nlogk)
【基础】17、优先级队列
优先级队列
优先级队列也是个队列，因此接口是一样的
普通队列是先进先出,优先级队列是优先级高的先出
优先级队列场景举例
医院的夜间门诊
队列元素是病人
优先级是病情的严重情况、挂号时间
操作系统的多任务调度
队列元素是任务
优先级是任务类型
优先队列的底层实现
根据优先队列的特点，很容易想到：可以直接利用二叉堆作为优先队列的底层实现
可以通过 Comparator 或 Comparable 去自定义优先级高低
【基础】18、哈夫曼编码
哈夫曼编码(Huffman Coding)
哈夫曼编码，又称为霍夫曼编码，它是现代压缩算法的基础
哈弗曼树
获取每个字符的权值
哈弗曼树的构建
构建哈夫曼编码
每一个编码都不是另外一个编码的前缀，这样就可以做到精准解析,不会产生歧义。
出现频率越高，使用的编码越短。出现频率越低使用的编码较长。降低了整个编码的大小
【基础】19、Trie
Trie
Trie 特里结构；单词查找树
Trie 也叫做字典树、前缀树（Prefix Tree）、单词查找树
Trie 搜索字符串的效率主要跟字符串的长度有关
接口设计与实现
总结
Trie 的优点：搜索前缀的效率主要跟前缀的长度有关
Trie 的缺点：需要耗费大量的内存，因此还有待改进
行者常至，为者常成！