# 前言

例行总结一下时间：

满打满算的话，怕是也花了一个月。主要是这本书涉及需要理性思考的更多，想不明白的话，就得多花点时间了。

加上这个月还插入了一些其它的东西，比如前几天的 优化博客加载、添加文章统计等 之类的就花去了挺多时间。

本书我是非常推荐的，看完之后，对很多算法原理性的东西认识都更深了 (虽然现在又忘了不少了，所以才需要笔记呢，等我跟着笔记再复习下)

# 第一章 复杂度分析

# 精确统计法（事后统计法）

• 运行一次代码，通过监控和统计手段得到算法执行的时间和占用内存大小
• 缺点
  • 测试结果受环境影响
  • 测试结果受测试数据影响

# 大 O 复杂度表示法

• 粗略估计算法执行效率

# 时间复杂度

• 表示算法执行时间与数据规模之间的增长关系（并不能度量在特定的数据规模下，代码执行的时间具体多少）
• 分析方法
  • 加法法则：代码总的复杂度等于量级最大的那段代码的复杂度
  • 乘法法则：嵌套代码复杂度等于嵌套内外代码复杂度的乘积
• 常见时间复杂度量级
  • O (1)：常量级，代码执行时间不随数据规模 n 变化
  • O (n)：线性阶
  • O (n*n)：平方阶
  • O (logn)、O (nlogn)：对数阶时间复杂度
  • O (m+n)、O (mn)：复杂度由两个数据规模决定
• 常见增长趋势排序：O (logn)->O (n)->O (nlogn)->O (n*n)

# 空间复杂度

• 表示算法存储空间与数据规模之间的增长关系
• 常见量级与时间复杂度一样
• 注：代码空间复杂度指的是除原本的数据存储空间外，算法运行过程中需要额外申请的存储空间

# 其它

• 最好时间复杂度
• 最坏时间复杂度
• 平均时间复杂度
• 均摊时间复杂度

# 第二章 数组、链表、栈和队列

• 线性表结构
• 线性表：线性表中数据只有前后两个方向

# 数组

用一块连续内存空间存储相同类型的一组数据

# 特点

• 线性表结构
• 连续内存空间
• 相同类型的数据

# 重要特性

• 随机访问：支持在 O (1) 时间复杂度内按照下标快速访问数组中的元素

排好序的数组，通过二分查找，时间复杂度为 O (logn)
数组支持随机访问，因此根据下标访问元素的时间复杂度为 O (1)

# 插入删除低效

• 时间复杂度为 O (n)
• 优化
  • 若不需要有序，将插入位置元素搬到最后，再插入元素 (或直接插入最后)
  • 或标记删除，空间不足时才删除元素

# 其它

• 下标：确切定义应该是偏移，相对于首地址偏移量，若从 1 开始，每次访问都需要做一次减法运算
• 一维数组偏移：baseAddress+i*typeSize
• 二维数组偏移：baseAddress+(m*i+j)*typeSize
• 注：二维数组，C# 中可不是这样的

# 链表

链表不需要一块连续内存，通过指针将一组零散内存块串联起来使用。

• 比较擅长 插入、删除操作，时间复杂度为 O (1)
  • 注：前提是已知前驱节点，否则操作时间复杂度为 O (n)
• 随机访问需要遍历，时间复杂度为 O (n)

# 循环链表

# 双向链表

比单链表更加常用，双向链表可以快速找到某个节点的前驱节点，支持双向遍历 (会占用多一些内存)

• 随机访问时间复杂度与单链表一致，为 O (n)
• 插入、删除 操作比单链表更加高效（单链表不支持直接获取前驱节点），时间复杂度为 O (1)

# 数组与链表性能对比

• 数组使用连续内存空间存储数据，可以更有效利用 cpu 缓存机制，提高访问效率。链表则不然
• 数组大小固定，占用连续内存空间，扩容耗时。链表则本身没有大小限制，天然支持动态扩容
• 链表需要额外数据，总体内存消耗更高

# 问题

• 寻找链表中间节点
  • 遍历求长度，再遍历取值
  • 快慢指针
• 单链表反转
  • 遍历，存储下一个节点，将当前节点下一个节点设置为上一个节点，将当前节点设置为上一个节点，进入下一轮
• 删除链表倒数第 n 个节点
  • 遍历求长度，再遍历删除
  • 双指针法，快指针先前进 n 步，然后两个指针一块走，快指针走到尾的时候，慢的指针就处于节点 n 上
• 链表中环检测
  • 快慢指针，相遇则有环 (快追慢)，无环则末尾

# 栈

先进后出，后进先出
操作受限的线性表数据结构

• 用数组实现的栈称作顺序栈，用链表实现的栈称为链式栈
• 应用
  • 函数调用
  • 表达式求值
  • 括号匹配
  • 浏览器前进后退 (两个栈)

# 队列

先进先出
操作受限的线性表数据结构

• 用数组实现的队列称为顺序队列，基于链表实现的队列称为链式队列
• 基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的无锁并发队列，因此循环队列比链式队列应用更加广泛
• 应用
  • 有限资源池的请求排队功能 (如线程池)
  • 注：C# 队列是循环队列，扩容时尾指针比头指针小时，会有两次复制操作

# 第三章 递归、排序、二分查找

# 递归

# 条件

• 待求解问题可以分解为几个子问题的解
• 待求解问题与分解后子问题除数据规模差异，求解思路相同
• 存在递归终止条件

# 思考方式

• 对于一个问题 A，只需要思考问题 A 及其分解问题的两层之间关系，屏蔽递归细节
• 不需要一层层往下思考子问题与子问题的关系
• 不要试图以人脑分解递归每个步骤，而是通过总结递推公式找出终止条件方式

# 问题

• 堆栈溢出
• 重复计算
• 函数调用耗时多
• 空间复杂度高

# 尾递归

• 有限制
• 并不是所有的编程语言都支持尾递归优化
• 并不是所有递归都可以改成尾递归
• 能改成尾递归的都可以改成迭代
• 尾递归代码可读性差

# 排序

# 执行效率

• 最好时间复杂度、最坏时间复杂度和平均时间复杂度
  • 原始数据有序程度对排序执行时间有较大影响
• 时间复杂度的系数、常数和低阶
  • 实际排序中，规模可能较小，因此需要考虑
• 比较次数和交换 (/ 移动) 次数
  • 比较元素大小的耗时少于交换 (/ 移动) 元素位置
  • 两者需要区分统计

# 内存消耗

• 原地排序算法：在原存储空间上完成排序操作
• 非原地排序算法：需要额外的非常量级数据存储空间才能完成排序
• 注：空间复杂度为 O (1) 的一定是原地排序算法，反过来原地排序算法空间复杂度不一定是 O (1)

# 算法稳定性

• 待排序数据中存在值相等元素，经排序后是否可能发生改变

# 排序类型

# 冒泡排序（稳定排序）

两层循环，第一层为 i<length，第二层 j<length-i-1

• 最好时间复杂度 (已经有序)：O (n)
  • 注：若某一次没有任何元素交换，可提前退出
• 最坏时间复杂度 (倒序排列)：O (n*n)
• 平均时间复杂度：O (n*n)

# 插入排序（稳定排序）

将数组分为两个区间：已排序区与未排序区
取未排序区元素插入已排序区合适位置，保持插入后依然有序

• 注：虽然理论时间复杂度与冒泡一样，但实际插入排序比冒泡排序性能好，插入交换操作只有一条，冒泡有 3 条

# 选择排序（不稳定排序）

与插入排序一样，将数组划分为已排序区和未排序区
每次从未排序区寻找最小元素，将其放 (交换) 到已排序区末尾

• 不稳定：若从大到小 1、1、2、7，7 与第一个 1 交换，此时两个 1 顺序就已经被交换了
• 时间复杂度都是 O (n*n)

# 归并排序（稳定排序）

分治算法思想：由下到上，先处理子问题，再合并
分治算法一般是用递归实现

• 注：分治是一种解决问题的处理思想，递归是一种编程技巧

归并排序的执行效率与原始数组的有序程度无关，任何情况下时间复杂度都非常稳定，执行时间复杂度都一样。但不是原地排序算法，空间复杂度较高，因此没有快速排序应用广泛。

• 时间复杂度：O (nlogn)
• 空间复杂度：O (n)

# 快速排序（不稳定排序）

分治算法思想：由上往下，先分区，再处理子问题

• 时间复杂度：O (nlogn)
  • 最坏：O (n*n)
  • 退化到 O (n*n) 的概率较小，而且可以通过合理选择 pivot 避免极端情况发生
• 空间复杂度 (递归深度，函数调用栈空间)：O (logn)
  • 最坏：O (n)

注：最好是指被中心点分割的区间均衡，最坏是指分区极不均衡

# 线性排序

时间复杂度是线性的，不基于比较的排序算法，排序过程不涉及元素之间的比较操作，排序的速度快于任何比较排序算法。

# 桶排序（bucket sort）

定义几个有序的『桶』，将要排序的数据分到这几个桶里，对每个桶的数据单独进行排序，再把每个桶数据按照顺序依次取出，组成的序列即有序

• 或者，若数据排序值较低，则直接划分为值数量的桶（例如，根据年龄排序，划分 150 个年龄桶），填充完毕后，依次遍历即已经排好序了

平均时间复杂度：O (n+k)
空间复杂度：O (n+k)
桶排序比较适合用在外部排序中：外部排序即数据存储在外部磁盘中，数据量比较大，而内存有限，无法全部加载内存处理

# 计数排序（counting sort）

桶排序的一种特殊情况
当要排序的 n 个数据所处范围并不大的时候，如最大值为 k，那么就可以把数据划分成 k 个『桶』，每个桶内数据都是相等的，省掉了桶内排序时间

• 计数 (遍历待排序数组，计算每个数据个数)
• 求每个计数累加和 (遍历计数数组累加)
• 整理
  • 从后往前遍历待排序数组，扫描到的元素的数据即为计数数组的下标
  • 从计数数组取出下标对应值 (整数索引)，该值即代表扫描元素应该处于新的排序数组所在位置
  • 将元素放入排序数组中，计数减一（从后往前处理数组，是为了保持排序算法稳定性，即相同数据元素保证依然排在前面）

平均时间复杂度：O (n+k)
空间复杂度：O (k)-- 听说是为了返回而创建的新数组不算？

• 计数排序时间复杂度为 O (n+k)，k 表示要排序的数据范围，若 k 远小于 n，那么时间复杂度可以表示为 O (n)
• 计数排序只能用在数据范围不大的场景，若数据范围 k 比要排序的数据 n 大很多，就不适合了
• 除此之外，计数排序只能给非负整数排序，若待排序数据是其它类型，就得将其在不改变相对大小的前提下，转换为非负整数

其它优化方式

• k 大小取待排序的数组中元素大小的极值差 + 1（max-min+1），确保不会造成额外不需要的空间浪费

注：通常会用于基数排序的子过程

# 基数排序（radix sort）

将整数按位数切割成不同的数字，然后每个『位』的数进行依次排序
注：按照每位排序算法必须稳定，否则就会有问题：非稳定排序算法，后一次排序不会兼顾前一次排序之后的数据顺序，那么之前所做的基于低位的排序就相当于白做了
根据每一位排序的排序算法，可以使用桶排序或计数排序（有多少位就做多少次额外排序）
平均时间复杂度：O (n*k)
空间复杂度：O (n+k)
要求

• 数据可以分割出独立的『位』，并且位之间有递进关系 (如手机号码)：如果 a 数据的高位比 b 数据大，那么剩下低位就不用比较了
• 另外，不等长数据也可以经过处理满足要求（例如根据单词排序，单词字母数量不一致，补齐到相同长度）
• 每一位数据范围不能太大，可以使用其它线性排序算法来排序，否则基数排序时间复杂度就无法达到 O (n) 了

# 总结

上述三种线性排序算法对数据有一定特殊要求，因此应用不是非常广泛，但如果数据正好符合这些排序算法要求，应用会更加高效，时间复杂度可达到 O (n)
桶排序 (每个桶存储一定范围的数值) 与计数排序 (每个桶只存储单一值) 思想类似，都是针对范围不大的数据，将数据划分到不同『桶』里实现排序
基数排序则要求数据可以划分成高低位，位之间有递进关系，且每一位的数据范围不能太大，因为基数排序需借助桶排序或计数排序完成每一个位的排序工作
另外，理论上 计数排序 是最快的

# 排序优化

# 优化快速排序

如果数据原来就是有序或接近有序，每次分区点选最后一个数据，那么性能就会退化到 O (n*n)
理想的分区点是，被分区点分开的两个小区间大小接近相等

• 选择合理分区点方式
  • 三数取中法：从区间首尾中分别取出一个数据，对比大小，取中间值作为分区点
  • 随机法：每次从待排序区间随机选取一个元素作为中心点
• 为避免堆栈溢出，限制递归深度，该用其它排序，或采用模拟实现函数调用栈

# 二分查找

对有序数据的一种快速查找算法
时间复杂度：O (logn)
对数运算的逆运算就是指数运算，该算法及其高效

• mid=low+(high-low)/2
• 或 mid=low+((high-low)>>1)

# 二分查找变体问题

通常的二分查找，只能查找不重复元素，若元素重复，那么查出来的结果就不能确定是重复元素中的哪个了
若对查找出的元素没有顺序要求，自然也无所谓，不过若有一定要求，那么就涉及变体问题
因此，其又分为以下四种变体方式：

• 查找第一个值等于给定值元素
  • 简洁写法
    • while(low<=high){a[mid]>value high=mid-1 else low=mid+1} if(low<n&&a[low]==value return low
    • 注意循环退出条件，并注意返回值，返回的是 low，此时 low 应该比 high 大，low 和 high 通过不断逼近 value 实现，最后 low 和 high 交错而过，low
  • 清晰写法
    • a [mid] 与要查找的 value 大小关系有三种情况：大于、小于和等于，主要特殊处理等于的情况
    • a[mid]>value;high=mid-1
    • a[mid]<value;low=mid+1
    • if(mid==0)||(a[mid]-1!=value) return mid;else high=mid-1
• 查找最后一个值等于给定值的元素（同上）
• 查找第一个值大于或等于给定值的元素（同上）
• 查找最后一个值小于或等于给定值的元素（同上）

# 第四章 哈希表、位图和哈希算法

哈希表 (hash table) 是数组的一种扩展，由数组演化而来，底层依赖数组支持按下标快速访问元素的特性

• 如果没有数组，就没有哈希表
• 即：哈希表利用数组通过下标访问元素的时间复杂度为 O (1) 的特性，利用哈希函数把元素的键值映射为数组的下标存储；当按照键值查询元素时，使用同样的哈希函数将键值转化为数组下标，然后通过索引直接取值

哈希函数涉设计时 3 个基本要求：

• 哈希函数计算得到的值是一个非负整数（因为数组下标从 0 开始）
• 如果 key1=key2，hash (key1)=hash (key2)
• 如果 key1≠key2，hash (key1)≠hash (key2)
  • 这个要求满足比较困难，也叫哈希冲突，即使 md5 都会出现冲突；而且数组存储空间有限，因此更加大了冲突概率
  • 哈希冲突需要进行解决

# 哈希冲突解决

# 开发寻址法 (open addressing)

一旦出现冲突，就通过重新探测新位置的方法来解决冲突

• 线性探测法 (linear probing)
  • 当插入数据时，若对应位置已经被占据，那就从该位置向后依次查找，直到找到一个空闲位置为止
  • 线性探测法删除时需要特殊处理，避免影响查找节点逻辑（查找若探测到空位置，就会导致直接返回空），方式是标记为 delete，查找探测时，遇到 delete 不会停止
  • 对于线性探测法，随着插入数据越来越多，空闲位置越来越少，哈希冲突概率就会越来越大，探测时间也会越来越长（最差时间复杂度 O (n)）
• 二次探测法
  • 与线性探测法很像，只是探测步长变为原来的二次方
  • hash (key)+0、hash (key)+pow (1,2)、hash (key)+pow (2,2) 等
• 双重哈希法
  • 使用多个哈希函数，若第一个哈希函数计算得出位置已经被占用，就用第二个、第三个哈希函数重新计算...... 直到找到空闲位置

# 链表法 (chaining)

是一种更加常用的解决哈希冲突的方法
在哈希表中，每个『桶』或者『槽』会对应一个链表，将哈希值相同的元素放到相同的槽位对应的链表中

• 当插入元素时，通过哈希函数计算出对应的槽位，然后将元素插入槽位对应的链表中；查找、删除元素同理
• 插入时间复杂度是 O (1)，且当链表中元素不多（哈希冲突不是那么高）时，其它操作 (查找、删除) 也可以粗略认为操作时间复杂度是 O (1)

装载因子 (load factor)= 元素个数 / 哈希表长度 (槽个数)
装载因子越大，说明链表长度越长，哈希表性能就会更低

# 工业级哈希表

若所有数据都被装到一个链表，哈希表退化后时间复杂度为 O (n)，是原本的执行消耗的 n 倍

• 精心设计的数据能使其退化造成性能急剧下降，形成拒绝服务攻击，这就是哈希表碰撞攻击的基本原理

# 设计哈希函数

哈希函数设计好坏，决定了哈希表冲突概率大小，也直接决定了哈希表的性能

• 哈希函数不能过于复杂，否则会消耗更多计算时间
• 哈希函数生成的值应尽可能随机分布

# 解决装载因子过大

动态扩容

• 动态扩容后，需要通过哈希函数重新计算每个数据在新的哈希表中位置
• 触发扩容的操作时间复杂度为 O (n)

# 避免低效扩容（增量扩容）

集中扩容会导致某一次插入时，耗时过高，因此可以考虑增量扩容

• 当装载因子达到阈值时，仅创建新的表，但并不立即将数据全部移到新表中
• 当插入新数据时，还会从原数据表中搬运一个数据到新表中，经过多次插入后，原表数据就被一点点移到新表中了，使扩容消耗分散，所有插入操作都变得很快
• 缺点：原表数据没有搬移完成时，内存无法释放，且为了兼容，查询操作需要同时在两张表中进行

# 选择合适的冲突解决方法

# 开放寻址法

优点

• 数据直接存储在数组中，可有效利用 cpu 缓存加快查询速度
• 不涉及链表和指针，方便序列化

缺点

• 所有数据都存在一个数组，发生冲突概率更高
• 因此装载因子不能过大，必须小于 1，所有需要消耗更多空间
  • 装载因子接近 1 时，会有大量的哈希冲突，导致大量探测、再哈希等，性能急剧下降
• 删除数据比较麻烦，需要额外特殊标记删除数据

因此，当数据量小，装载因子小时，适合采用开发寻址法

# 链表法

链表法相比开放寻址法，对大装载因子容忍度更高

• 只要哈希函数计算得到的值比较随机且均匀，即便装载因子变成 10，也只是链表长度变长了点，性能下降并不多

缺点

• 链表中节点要额外存储 next 指针，对于小对象存储，有可能会让内存消耗翻倍（当然若存储大对象，远大于指针消耗，那么指针内存消耗就可以忽略了）
• 链表节点在内存种零散分布，对 cpu 缓存不友好

也可以考虑将链表改造成其它高效数据结构，例如红黑树，这样即便出现哈希冲突，在极端情况下所有数据都哈希到了同一个『桶』，最终哈希表也只是退化成红黑树，查询效率也不会太差 (O (logn))

# 总结

需满足要求

• 支持快速查询、插入、删除操作
• 内存占用合理，不浪费过多内存空间
• 性能稳定，在极端情况下，哈希表性能也不会退化到无法接受的程度

设计思路

• 设计一个合适的哈希函数
• 设置合理的装载因子阈值 (开放寻址法)，并设计动态扩容策略
• 选择合适的哈希冲突解决方法

# 利用哈希表优化 LRU 缓存淘汰算法

哈希表对应链表中对应节点，节省遍历链表开销

• 虽然哈希表支持高效插入、删除和查找操作，但哈希表中数据经哈希函数打乱后是无规律存储的，无法支持按照某种顺序遍历并输出数据
• 因此可以将其与有序链表结合使用

有序链表支持按照某种顺序遍历并输出数据，哈希表与其结合，就可以实现：既可以快速插入、删除和查找操作，又支持 O (n) 时间复杂度按顺序遍历并输出数据

# 位图：网址链接去重

假设一条网址平均长度 64B，10 条网址为 60G 左右
对基于链表法解决冲突的哈希表，在查询网址链接时，找到对应链表后，还需要用待判重网址链接依次对比，对比也操作较耗时

# 位图（bitmap）

原理：申请对应长度的 bool 数组，使用 bool 进行标记，标记对应元素是否存在
char 类型表示一个长度为 16 的位图

• 存取位图数据时，用数据除以 16，得到数据存储元素，然后与 16 取余，得到具体哪个二进制位上

# 布隆过滤器（Bloom filter）

基于位图实现，是对位图的一种改进，用于改进存储空间的利用
做法

• 尽管数据范围增大了，但是依然使用更低范围的位图，但是使用哈希函数进行索引
• 哈希函数必然有冲突，其做法是定义多个哈希函数，并同时将对应下标处置为 true，即用 k 个二进制位而非一个表示一个元素是否存在
• 判断是否存在时，判断所有哈希函数计算的下标都为 true 才通过

缺点

• 存在『误判』，即不存在的被判断为存在
• 多个元素的哈希函数重叠设置导致

对于误判情况，某些业务场景可以容忍的情况下，是可以使用的
另外，误判只会误判断『已经存在』，数据存在的情况下不会导致判断『不存在』

• 利用该特定，也可以在例如查询数据库之前，利用布隆过滤器判断数据是否存在，不存在就可以省略查询开销

布隆过滤器非常适合不需要完全准确，允许存在小概率误判的大规模判重场景
其误判概率主要与哈希函数个数、位图大小有关，更适合静态数据，当数据越来越多，false 越来越少，误判率就会增高（因此对于动态数据，布隆过滤器还需要支持动态扩容，阈值）

# 总结

位图和布隆过滤器，相比哈希表，在内存消耗上降低了许多，在特定场景下，优势更明显
而且位图属于 cpu 密集型，哈希表由于链表存在，若进行判重还需要读取对应数据 (内存密集型) 对其元素进行额外对比，因此理论上位图性能更好

# 哈希算法

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射规则就叫做『哈希算法』，原始数据映射后得到的二进制值串就称为『哈希值』
一般要求

• 哈希值不能反向推导出原始数据（因此也叫单向哈希算法）
• 对数据变化敏感，原始数据哪怕变动一个二进制，对应哈希值也大不同
• 哈希冲突概率要小
• 执行效率要高

# 应用 - 安全加密

MD5（message-digest 5）、SHA（secure hash algorithm）
需求

• 很难根据哈希值反向推导出原始数据
• 哈希冲突概率要很小

哈希冲突无法完全避免

• 巢鸽理论（抽屉理论）：将 11 只鸽子放进 10 个鸽巢，那么肯定有一个鸽巢中鸽子数量多于一个，即肯定有两只鸽子在一个鸽巢内
• 例如 MD5 最大 128 位，表示数据也有限，而需要计算的原始数据是无穷大的
• 另一个角度看，哈希值越长的算法，哈希冲突概率就越低（相应计算时间就越长）

# 应用 - 唯一标识

例如海量图库中查询是否存在，例如从图片开头取 100B、中间取 100B、末尾取 100B，然后放在一块计算哈希值

# 应用 - 数据校验

例如 BT 分块文件的校验，通过将下载文件块与种子文件记录的哈希进行对比避免文件块出现问题

# 应用 - 哈希函数

哈希函数是设计哈希表的关键，不过相比其它，对冲突容忍度更高，一般比较简单，更追求效率

# 应用 - 负载均衡

会话沾滞：属于同一会话所有请求都会被路由到同一台服务器上

# 应用 - 数据分片

统计 1TB 大小日志 “搜索关键词” 出现的次数

• 从日志文件依次读取每个搜索关键词，通过哈希算法计算哈希值，然后与机器个数求模取余
• 假设得出值为 k，那么数据就会发送至编号为 k 的机器
• 相同关键词会被分配给相同机器处理，每台机器分别计算统计结果，最后合并

# 应用 - 分布式存储

哈希算法计算哈希值，求模取余，最终值即为对应缓存机器编号

• 该方式在新增机器后，会有扩容问题：数据需要在机器之间重新分配，即缓存失效

为解决缓存失效问题，于是有一致性哈希算法

• 假设 k 台机器，数据的哈希值范围是 [0,Max]，将整个范围划分为 m 个区间（m 远大于 k），每台机器负责 m/k 个小区间
• 当有新机器加入，就将某几个小区间数据搬入新机器
• 这样既不需要全部重新计算哈希值并搬移数据，又保持了各个机器上数据量的均衡

# 总结

哈希算法作为密码存储，可以加『盐』以提高用户密码复杂度，增加字典攻击的破解难度

# 第五章 树

# 树和二叉树

# 树的定义

• 节点的高度 = 节点到叶子节点的最长路径长度
• 节点的深度 = 根节点到这个节点的路径长度
• 节点的层 = 节点的深度 + 1
• 节点的高度 = 根节点的高度

# 二叉树

每个节点最多两个子节点，但是并不要求每个节点必须要有两个子节点
分类

• 满二叉树：除叶子节点外，每个节点都有左右两个子节点
• 完全二叉树：叶子节点分布在最下层和倒数第二层，最下面一层 (若只有一个节点) 的叶子节点都靠左排列

注：满二叉树是完全二叉树的一种特殊情况

# 二叉树的存储

一般两种方法

• 基于指针的链式存储方式（通用）
• 基于数组的顺序存储方式（适用完全二叉树）
  • 若节点 x 存储于数组 i 处
  • 左子节点 = 2i
  • 右子节点 = 2i+1
  • 父节点 = i/2

完全二叉树仅浪费一个下标 0 的存储空间，对于非完全二叉树，会浪费比较多的存储空间，因此非完全二叉树一般采用链式存储
采用数组方式更节省内存，且不需要记录左右子节点指针，因此完全二叉树单独提出，这也是完全二叉树要求最下层节点需要全部靠左排列的原因

# 二叉树的遍历

• 前序：根左右
• 中序：左根右
• 后序：左右根

遍历时间复杂度：O (n)

# 二叉查找树（binary search tree）

也称为二叉搜索树，也是二叉树中常用的一种类型
用来组织动态数据集合，可以支持数据的快速插入、删除和查找操作

• 对于二叉查找树中任意节点，左子树值都小于这个节点的值，右子树值都大于这个节点的值

# 操作

# 查找操作

• while(p!=null)
  • if(data<p.data) p=p.left
  • else if(data>p.data) p=p.right
  • else return p

# 插入操作

与查找类似，判断节点大小插入叶子节点

# 删除操作

• 待删除节点没有子节点，直接将父节点指向该节点指针置为 null
• 待删除节点有一个子节点，更新父节点指向删除节点指针，使其重新指向待删除节点的子节点
• 待删除节点有两个子节点，需要找到这个节点右子树中最小节点，将其替换到删除的节点位置

另外，还有一个比较简单、取巧的处理方法：只将删除节点标记为已删除，而并不真正删除。这样删除操作就会变得很简单，缺点是占用了内存并会降低查询效率

# 其它

中序遍历可以从小到大有序输出数据，且时间复杂度为 O (n)

• 因此二叉查找树也称二叉排序树

# 支持重复数据的二叉查找树

针对包含值相同的节点的二叉树，有两种存储方式

• 每一个节点存储不是一个数据，而是一组数据，把值相同的数据存储在同一个节点上
• 每个节点仍然只存储一个数据，当插入数据时，如果碰到一个节点的值与插入数据的值相同，就将插入的数据放到该节点的右子树。即某个节点的右子树存储的是大于等于该节点的值的节点

# 二叉查找树的性能

在二叉查找树中，查找、插入和删除等操作与树的高度成正比

• 最坏时间复杂度 (退化为链表)：O (n)
• 最好时间复杂度 (完全二叉树)：O (logn)

# 哈希表与二叉查找树

哈希表不能替代二叉查找树

• 哈希表数据无序存储，若需要输出有序数列，需要先排序，或配合有序链表使用（二叉查找树中序遍历即可）
• 哈希表扩容耗时，当哈希冲突时，性能不稳定（二叉查找树性能也不稳，但平衡二叉查找树是稳定 O (logn) 的）
• O (logn) 有时不一定比 O (1) 慢，取决于具体数据规模、常量、系数等。因此哈希表由于哈希冲突、哈希计算等，不一定比之高效
• 哈希表构造比二叉查找树复杂，需要考虑更多：哈希函数设计、冲突解决、扩容、缩容 等。平衡二叉查找树只需要考虑如何维护平衡性

# 平衡二叉查找树

普通二叉查找树在频繁动态更新过程中，可能会树的高度远大于 log2n 的情况，导致各个操作效率下降。特别是极端情况下退化为链表，时间复杂度变成 O (n)
因此有了平衡二叉查找树

# 定义

二叉树中任意一个节点的左右子树的高度相差不大于 1（完全二叉树、满二叉树均为平衡二叉树）
平衡二叉查找树不仅满足平衡二叉树定义，同时满足二叉查找树的特点

• 种类：AVL、红黑树、Treap (树堆)、Splay Tree (伸展树)
• AVL 树：最先被提出的平衡二叉查找树是 AVL 树，它严格符合平衡二叉查找树的定义，是一种高度平衡的二叉查找树
• 红黑树：并没有严格符合平衡二叉查找树的定义，从根节点到各个叶子节点的最长路径有可能会比最短路径长一倍

# 红黑树的定义

Red-Black Tree,R-B Tree，是一种相对平衡的二叉查找树，并不符合严格意义上的平衡二叉查找树的定义

• 根节点是黑色
• 每个叶子节点都是黑色的空节点 (叶子节点不存储数据)
• 任何上下相邻的节点不能同时为红色，红色节点被黑色节点隔开（不会有连续的红色节点）
• 对每个节点，从该节点到叶子节点的所有路径，都包含相同数目的黑色节点

# 红黑树性能

平衡二叉查找树提出是为了解决二叉查找树因为动态更新导致性能退化问题
『平衡』可以等价为性能不退化，『近似平衡』可以等价为性能退化不太严重

• 红黑树比高度平衡的 AVL 树高了一倍，性能损失不会太大。红黑树维护节点平衡成本更低，因此性能并不比 AVL 树差

为何红黑树更受欢迎？

• AVL 是一种高度平衡的二叉树，查找数据效率非常高。但为了维护平衡，每次插入、删除数据都要对树中节点的分布做调整，操作复杂耗时
• 红黑树只做近似平衡，因此维护平衡成本比 AVL 树更低，性能又损失不大。

# 递归树

借助 树 求递归算法的时间复杂度

# B + 树

通过二叉查找树演化而来

• B + 树由 m 叉查找树和有序链表组合而成
• 每个节点中子节点个数不能超过 m，也不能小于 m/2
• 根节点的子节点个数可以不超过 m/2，这是例外
• 一般情况下，根节点会被存储在内存，其它节点存储在磁盘

其它，与 B- 树差异（注：B - 就是 B 树） BalanceTree、B-Tree

• B+ 树中节点不存储数据，只是索引，而 B 树中节点存储数据
• B 树中的叶子节点并不需要链表串联
  • 即 B 树只是一个每个节点的子节点个数不能小于 m/2 的 m 叉树

# 第六章 堆

# 堆：如何维护动态集合的最值

# 堆的定义

• 堆必须是一个完全二叉树
• 堆中每个节点的值必须大于或等于 (或小于等于) 其子树中每个节点的值
  • 即堆中每个节点的值都大于或等于 (或小于或等于) 其左右子节点的值
  • 注：由于该特性，堆不一定是二叉查找树，左子节点不一定比右子节点小

若堆中每个节点的值都大于或等于子树中每个节点的值，称为大顶堆
若堆中每个节点的值都小于或等于子树中每个节点的值，称为小顶堆
注：下述理论部分特指大顶堆

# 堆的存储

完全二叉树比较适合用数组存储，因此堆也适合用数组存储

• 用数组存储完全二叉树非常节省内存，因为不需要存储左右子节点指针，只需要通过数组下标运算就可以找到某个节点的左右子节点和父节点

对于下标为 i 的节点，根存储于 1 处，有：

• 左子节点：2i
• 右子节点：2i+1
• 父节点：i/2

另外，也可以将根节点存储于 0 处：

• 左子节点：2i+1
• 右子节点：2i+2
• 父节点：(i-1)/2

对比来看，将根节点从 1 开始存储，计算父子节点下标更方便
比较常用操作：插入元素、获取堆顶元素、删除堆顶元素

• 不常用操作：按照节点指针 (数组下标) 删除任意元素

# 在堆中插入元素

若将新元素插入堆的末尾 (数组的末尾)，堆就不满足定义要求了，因此需要调整，调整过程称为『堆化』
堆化分为两种：自上而下和自下而上

• 自下而上：假设堆化节点为 a，顺着节点 a 所在路径向上对比，若节点 a 大于父节点，就将其与父节点交换，重复该过程
• 自上而下：从堆顶元素开始，对父子节点进行对比，对于不满足大小关系的父子节点互换位置，重复该过程直到满足要求

# 删除堆顶元素

对于大顶堆，当删除堆顶节点后，需要将第二大节点放到堆顶，并迭代处理后续节点
不过如此处理后，最后对就不是完全二叉树树了（叶子节点出现空洞），因此有另一种处理方式：

• 将最后一个节点放到堆顶，然后利用自上而下的堆化方式让堆重新满足定义

# 删除任意元素

将堆中最后一个元素替换到删除元素位置，分条件执行堆化

• 替换的元素大于删除元素，进行自下而上的堆化
• 替换的元素小于删除元素，进行自上而下的堆化
• 替换元素等于删除元素，不需要堆化

# 性能

获取堆顶元素（最大最小值)：O (1)
插入、删除、删除任意元素时间复杂度：O (logn)

# 堆排序

堆排序时间复杂度：O (nlogn)
空间复杂度：O (1)
堆排序的时间复杂度要比快速排序稳定，但性能比快速排序慢

• 数据访问方式对 cpu 不友好 (数据跳着访问，堆排比较的几乎都不是相邻元素)，且实际交换可能会比快排更多
• 建堆会降低数据有序度，例如对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了

排序整个过程分为两步：建堆、排序

# 建堆

先将数组中数据原地组织成一个堆
两种思路

• 借助堆中插入数据处理思路
  • 将堆中数据划分为前后两个部分，前半部分表示已建好堆的数据，后半部分表示非堆中数据
  • 开始堆中只存在下标为 1 的数组元素，将下标 2~n 依次插入堆中，执行自下而上的堆化，执行完毕后所有数据即组织成堆结构
  • 建堆时间复杂度：O (nlogn)
  • 每个节点堆化时间复杂度：O (logn)
• 从后往前处理数组，对每个数据执行自上而下的堆化（效率更好）
  • 因为叶子节点不需要堆化，对于完全二叉树，下标 n/2-1~n 的节点都是叶子节点
  • 因此只需要对 n/2~1 的数据依次执行自上而下堆化
  • 建堆时间复杂度：O (n)
  • 每个节点堆化时间复杂度：O (logn)

# 排序

建堆结束后，堆中数据已经是按照大顶堆的特性来组织的了（注：左右子节点中，左子节点不一定大于右子节点）

• 将最大元素与最后一个元素 k 交换
  • k=k-1
  • 然后执行从 0~k 的自上而下堆化
• 反复进行，直到最后只剩一个元素即排序完成

# 堆的应用

经典应用是求 topK 一类的问题，另外还有例如优先级队列、求中位数和求百分位数

# 优先级队列

在优先级队列中，数据并不是先进先出，而是按照优先级的高低，优先级最高的最先出队
堆天然就是一个优先级队列

# 合并多个有序文件

使用优先级队列 (堆) 维护动态数据最小值的时间复杂度是 O (logn)，更高效

# 高性能定时器

常规做法是每指定间隔 (如 1s) 扫描一次定时任务，该做法比较低效：任务可能间隔还很久、每次扫描整个任务列表消耗大
使用堆做优先级队列存储任务，队首存储最先执行任务

• 将队首任务执行时间与当前时间相减，得到时间间隔 t，t 代表从当前时间开始，需要等待多久才会有第一个任务被执行，如此定时器就可以设定 t 秒后再来执行任务
• t 秒后取队首任务执行，然后计算新的队首任务的执行时间与当前时间之差

# 求 TopK

• 静态数据，事先确定，不会再变
  • 建堆、堆化
  • 时间复杂度：O (nlogK)
• 动态数据，有数据会动态加入集合
  • 插入时维护堆

# 求中位数和百分位数

如果数据个数是奇数，把数据从小到大排列，第 n/2+1 就是中位数
如果数据个数是偶数，中位数有两个：n/2 和 n/2+1

• 静态数据集合
  • 建堆后排序即可
• 动态数据集合
  • 维护一个大顶堆和一个小顶堆
  • 大顶堆存储动态集合前半部分数据，小顶堆存储后半部分数据，且小顶堆数据都大于大顶堆数据
  • 如此，大顶堆中堆顶元素即为中位数（偶数情况下，则大小堆顶元素）
  • 插入元素时，判断元素大小，以决定插入哪个堆
  • 插入后若元素个数不满足要求，则将其中一个堆顶元素移到另一个堆，以保持平衡

求百分位数

• 与中位数原理一致，同样维护两个大小顶堆，只是元素个数比例调整为规定的百分比

# 第七章 跳表、并查集、线段树和树状数组

# 跳表

我们只需要对链表稍加改造，就可以支持类似『二分』的查找算法，改造后的数据结构可称为跳表 (skip list)
如 Redis 中有序集合就是用跳表实现

• 按区间查找：跳表可以以 O (logn) 时间复杂度定位区间起点，然后在原始链表中顺序向后遍历，直到遇到区间终点节点
• 相比红黑树，跳表更灵活、易实现

跳表实现非常灵活，可以通过改变索引构建策略，平衡空间、时间复杂度
注：跳表是有序的

# 跳表的由来

在链表中的数据，即使有序存储，查找数据的时间复杂度也是为 O (n)
于是对链表建立一级『索引』，每指定间隔 (如两个) 节点提取到索引层，这样查找节点时，先遍历索引层，然后跳入原始链表层，节省遍历时间

• 第三级索引：2 个节点
• 第二级索引：4 个节点
• 第一级索引：8 个节点
• 原始链表：16 个节点

即，假设原始链表包含 n 个节点，第一级大约 n/2 个节点，每上升一级大约减少一半节点，依次类推直到剩下两个节点为止

# 跳表效率

时间复杂度：O (logn)，与二分查找相同

• 不过由于查询效率提升的前提是构建多级索引，属于空间换时间的设计思路

空间复杂度：O (n)

• 不过可以通过增加抽取节点间隔控制索引节点占用的存储空间，以达到时间复杂度和空间复杂度的平衡

插入、删除时间复杂度：O (logn)

• 若删除节点在索引中也有出现，除删除原始链表节点外，还需要删除索引中对应节点

# 跳表索引动态更新

跳表借助随机函数更新索引结构
如通过随机函数得到某个值 k，就将该节点添加到第一级到第 k 级索引中

# 并查集（Union-find set）

根据对象两两之间的直接关系来快速查询任意两个对象之间是否存在关系（直接或间接）

• 即 若 a、b 存在关系，b、c 存在关系，那么 a 和 c 就是存在关系的

基于操作的对象 (集合) 和行为 (并和查)，将这种数据结构称为并查

# 基于链表的实现

通过链表来表示集合，链表头节点作为集合代表标识集合
假设原始数据存储在一个数组中，通过

• 将链表头节点作为集合的『代表』，每个链表节点除存储 next 指针外，还存储一个指向『代表』的头节点 R 指针
• 合并集合时，将两个链表合并，并更新其中一个链表所有节点的 R 指针指向新的表头
• 查询两个对象是否属于同一个集合时，判断指向头节点的 R 指针是否指向相同即可

查找时间复杂度：O (1)
合并时间复杂度：O (n)

• 主要是更新指向头节点指针耗时

# 基于树的实现

为降低 union 操作时间复杂度，可以使用树的方式实现
基于树的并查集实现，使用树来表示集合，树的根节点作为集合代表来标识集合

• 判断节点所属集合时，通过借助节点父节点指针，向上追溯，沿着节点路径到达根节点
• 合并时，只需要把一棵树拼接到另一棵树：让其中一棵树的根节点指针指向另一棵树的根节点即可

因此，按树实现方式虽然会减少合并消耗，但是会增加查找时间复杂度
为避免查询时间复杂度增加过高，需要尽量让树 矮胖 而非 高瘦

• 按秩合并
  • 记录树的高度，称为秩 (rank)
  • 若两棵树的秩不同，合并后的秩为原高度大的树的秩
  • 若两棵树的秩相同，合并后的秩等于原秩 + 1
• 路径压缩（更有效）
  • 在借助父节点指针追溯根节点时，将经过路径上的所有节点父节点指针都更新为指向根节点（再次查找就快了）

合并时间复杂度：O (1)
查找时间复杂度：路径压缩后，O (1)
两个优化是可以同时支持的

# 线段树

如果我们需要罗列落在某个区间的所有数据，基于跳表的实现方案最优
但若是只需要统计落在某个区间的数据『个数』，即解决区间统计问题时，线段树更加高效

• 假设数据集合最大值为 m，且数据都是正整数，可以构建一棵特殊的二叉树，每个节点代表一个区间，包含 3 个基本数据：区间起始点、区间结束点和统计值 (如数据个数，具体视需求而定)
• 根节点表示最大区间 [1,n]，左右子节点分别代表 [1,n/2]、[n/2+1,n]
• 可采用数组形式存储（虽然不是完全二叉树，可能会浪费一定空间，不过由于线段树叶子节点主要集中在最后两层，整体空洞不大，可以接受。另外还有链式方式）

空间复杂度：O (n)

• 与数据集合个数无关，与数据集合最大值有关

时间复杂度：

• 构建：O (n)
• 插入、删除：O (logn)

线段树能解决的问题统一称为区间统计问题，除统计区间数据个数外，还可以统计某个区间数据之和、最大值和最小值，以及某个区间第 k 大值
注：关于线段树数据存储大小

• 如果 n 恰好是 2 的 k 次幂，由于线段树最后一层的叶子节点存储的是数组元素本身，最后一层的节点数就是 n，前面所有层的节点数之和是 n−1，那么总节点数就是 2×n−1。为了方便起见，分配 2×n 的空间。
• 如果 n 不是 2 的 k 次幂，最坏的情况就是 n=2k+1，那么有一个元素需要开辟新的一层来存储，需要 4×n−5 的大小。为了方便起见，可以分配 4×n 的空间

# 树状数组

可以解决大部分基于区间上的更新以及求和问题

• 所有树状数组能做的，线段树也能做，不过树状数组的优点是简单（但是原理反而感觉更难理解一些）、效率更高点
• 利用线段树可以解决区间统计问题，利用树状数组可以解决前缀和问题，区间统计包括 前缀和

时间复杂度：O (logn)，

• 相比线段树系数更少
• 缺点是功能有限，不能解决复杂区间问题

# 前缀和

标准做法：创建一个 n+1 大小的前缀和数组，遍历计算，前缀和数组下标从 1 开始

• preSum[i]=preSum[i-1]+array[i]
• 要么更新元素慢 (更新时计算)，要么查询前缀和操作慢 (查询时计算)

任何一个数，都可以分解为一组 2 的 k 次方的和

• 6=b110=2²⁺²1+2^0
• 7=b111=2²⁺²1+2^1

lowbit：求某一个数的二进制表示中最低的一位 1，例如 6 返回 2

• 先消掉最后一位 1，然后再用原数减去消掉最后一位 1 后的数
• 求负数的二进制补码表示：负数的补码为其绝对值取反后加 1，然后与原数进行与操作 i&(-i)，正好得到最低一位 1

前缀和可通过递推公式计算

• 假设数组 c 存放所有通过 lowbit 计算出来的对应数值的和
• 那么前缀和 preSum=preSum [i-lowbit (i)]+c [i]

借助树状数组，可以将前缀和更新操作的时间复杂度降低到 O (logn)

# 第八章 字符串匹配算法

概念：主串和模式串，所有字符串匹配算法都会用到

• 如果在字符串 a 中查找字符串 b，那么字符串 a 就是 主串，字符串 b 就是模式串
• 将主串长度记作 n，模式串长度记作 m
• 一般情况下，n 大于或等于 m；若 n 小于 m，则主串中必然不存在模式串

# BF 算法

# 原理与实现

BF（Brute Force，暴力匹配）算法，也称为朴素匹配算法，该算法比较暴力，简单直接，因此性能不高

• 如果模式串长度为 m，主串长度为 n，那么在主串中就会有 n-m+1 个长度为 m 的子串
• 只需要暴力对比这 n-m+1 个子串与模式串，就可以找出主串与模式串匹配的子串

# 性能

最坏时间复杂度：O (nm)
虽然时间复杂度较高，但实际却比较常用

• 实际开发中，大部分情况模式串和主串长度不会太长，数据规模较小（小规模下性能与更加高效的 KMP、BM 算法可能相差无几）
• 每次模式串与主串中字符串匹配时，若中途遇到不能匹配字符，可提前终止
• BF 算法思想简单，代码实现也简单（意味着不容易出错）

# RK 算法（Rabin-Karp）

对 BF 算法的优化，借助哈希算法提高匹配效率

# 原理

通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较

• 若某个哈希值相等，则说明匹配

哈希计算优化

• 假设主串和模式串对应字符集只包含 k 个字符，那么就可以用一个 k 进制数表示一个子串

时间复杂度：O (n)

• RK 算法的执行效率取决于哈希算法
• 若事先缓存，则会有额外空间复杂度消耗

# BM 算法（Boyer-Moore）

模式串和主串的匹配过程可以看做模式串在主串中不停地往后滑动，当遇到不匹配字符串时，BF 算法和 RK 算法的做法：将模式串往后滑动一位，从模式串第一个字符重新开始匹配

• BM 算法本质上就是在寻找某种规律，借助这种规律，在模式串与主串匹配过程中，能够跳过一些肯定不会匹配的情况，将模式串往后多滑几位，以此提高效率

# 原理

• 坏字符串规则（bad character rule）
  • 按照模式串下标从大到小顺序倒序进行
  • 当发现某个字符无法匹配，就将该字符称为坏字符（指主串中字符）
  • 用坏字符在模式串中查找，发现不存在则可以直接滑到坏字符之后
  • 若坏字符在模式串中存在，则滑动对应位数，使其与模式串对齐，再重新匹配
  • 滑动规则
    • 坏字符对应模式串下标记为 si，若在模式串存在，则记作 xi，不存在则 xi=-1
    • 往后滑动位数 = si-xi，所以若不存在，滑动位数等于模式串字符个数 (length-1-(-1))
    • 计算滑动位数有可能是负数，因此有好后缀规则补充
• 好后缀规则（good suffix rule）

最坏时间复杂度：O (n)
最好时间复杂度：O (n/m)
注：空间复杂度较高

# KMP 算法

与 BM 算法本质一样，希望匹配过程中找到一些规律，多滑几位

• 从前往后匹配
• 将不能匹配的字符称为坏字符
• 已经匹配的那段字符串称为好前缀

空间复杂度：O (m) m 表示模式串长度
时间复杂度：O (m+n)

# Trie 树（字典树）

又叫前缀树 (prefix tree)，属于多模式串匹配算法
是一个树形结构，用来解决在一组字符串集合中快速查找某个字符串的问题
本质上是利用字符串之间的公共前缀，将重复的前缀合并在一起

• 根节点不包含信息
• 其它每个节点表示字符串中一个字符
• 从根节点到到某节点一条路径表示字符串集合中的一个字符串（添加字符串时，需要将字符串结尾节点设置为 EndingChar，以使查找时能区分）

# 效率

构建时间复杂度：O (m*len)

• len 表示模式串平均长度，m 表示模式串个数

查询时间复杂度：O (k)

• k 表示待查询字符串长度

字符串匹配非常高效，不过由于借助了空间换时间的设计思路，内存消耗较大

• 例如每个节点存储字符串的数据结构，需借助有序数组、哈希表、红黑树

# 总结

对于精确匹配，哈希表或红黑树更加适合
对于模糊查找，例如查找前缀匹配字符串，Trie 树更合适、无可替代

• 如关键词提示
• 自动输入补全

# AC 自动机：多模式串匹配实现敏感词过滤

• 单模式串匹配算法是指在一个模式串和一个主串之间进行匹配
• 多模式匹配串算法是指在多个模式串和一个主串之间作匹配（在一个主串中同时查找多个模式串）
  • 只需要扫描一遍主串，就可以在主串中一次性查找多个模式串是否存在

# 基于 Trie 树的敏感词过滤

对敏感词库进行预处理，构建成 Trie 树

• 将用户输入作为主串，从第一个字符开始，在 Trie 树中进行匹配
• 当匹配到 Trie 树叶子节点或中途遇到不匹配字符时，将主串起始匹配位置向后移一位，重新从根节点开始

# 基于 AC 自动机的敏感词过滤

借鉴单模式串匹配算法优化思路，对 Trie 树进行优化，进一步提高效率，产生 AC 自动机

• 类似于单模式串匹配算法中 BF 与 KMP 的关系

主要操作

• 将多个模式串构建成 Trie 树
• 在 Trie 树上构建失败指针
  • 失败指针指向『最长可匹配后缀子串』
  • 例如 abc 后缀子串为 bc、c，将其与其它模式串匹配，若两个都能匹配上，则最长可匹配后缀子串为 bc

匹配的时间复杂度：O (n*len)

• 与 Trie 树一样
• 但实际情况下，由于失败指针优化，可以接近 O (n)

# 第九章 图

# 图的表示：如何存储社交网络中好友关系

# 图的定义

图 (graph) 与树一样，也是一种非线性表，不过相比树更复杂

• 对应树中元素称为节点，图中的元素称为顶点 (vertex)
• 图中一个顶点可以与任意其它顶点建立连接关系，这种连接关系称为边 (edge)
• 与顶点相连接的边的条数，称为顶点的度 (degree)
• 边有方向的称为有向图，边没有方向的称为无向图
• 无向图中顶点的度表示此顶点有多少条边与之相连，有向图中则分为入度 (in-degree) 和出度 (out-degree)
• 带权图 (weighted graph)：每条边都有一个权重

# 邻接矩阵的存储方法

邻接矩阵（adjacency matrix），底层依赖二维数组

• 对于无向图，若顶点 i 与 j 之间有边，则将 A [i][j] 和 A [j][i] 标记为 1
• 对于有向图，则只标记有连接的为 1
• 对于带权图，数组中存储对应权重

邻接矩阵存储方式，可能比较浪费空间，特别是对于稀疏图（sparse matrix）来说，顶点很多，每个顶点的边并不多

# 邻接表的存储方法

邻接表（adjacency list），每个顶点对应一条链表

• 对于有向图，每个顶点对应的链表存储其指向的顶点
• 对于无向图，每个顶点对应的链表存储的是与这个顶点有边相连的顶点

邻接矩阵存储起来比较浪费空间，但使用起来更高效
邻接表存储起来比较节省空间，但使用起来就没那么高效了（当然邻接表的链表数据结构也可以再优化，换成更合适的数据结构）

# 深度优先搜索与广度优先搜索

六度分割理论：只需要六层关系就能认识任何一个陌生人；即与任何一个陌生人之间能通过 5 个中间人建立关系

# 搜索算法

搜索：在图中寻找从一个顶点出发到另一个顶点的路径
深度、广度优先搜索是针对无权图的搜索算法

# 广度优先搜索（Breadth First Search，BFS）

是一直地毯式层层推进的搜索策略，首先查找距离起始顶点 s 最近的，然后是次近的，依次往外搜索，直到找到终止顶点
时间复杂度：O (V+E)

• V 表示顶点个数
• E 表示边的个数

空间复杂度：O (V)

# 深度优先搜索（Depth First Search，DFS）

不撞南墙不回头策略
即走完一条路径之后，才可能搜索下一个节点路径
时间复杂度：O (V+E)
空间复杂度：O (V)

# 拓扑排序

拓扑排序运行在有向无环图上
一般可用于通过局部顺序推导全局顺序问题，还能检测图中是否存在环

• 通过局部的依赖关系、先后顺序，推导出一个满足所有局部依赖关系的执行序列
• 解决算法主要有两种：Kahn 算法和深度优先搜索

# Kahn 算法实现拓扑排序

Kahn 算法利用贪心算法思想
在定义数据结构时，若 s 需要先于 t 执行，就添加一条 s 指向 t 的边

• 因此每个顶点的入度表示这个顶点依赖多少个其它顶点
• 若某个顶点入度变成 0，则表示该顶点没有依赖的顶点了（或者说依赖都已执行）
• 从图中找出一个入度为 0 的顶点，将其输出到拓扑排序结果序列，所有依赖它的顶点入度都可以减 1（即将该顶点可达顶点入度减 1）
  • 循环执行该过程，最后输出序列即为满足所有局部依赖关系的一个拓扑排序

时间复杂度：O (V+E)

# 深度优先搜索实现拓扑排序

或者应该叫『深度优先遍历』，需要遍历图中所有顶点，而非只是搜索一个顶点到另一个顶点的路径

• 通过邻接表构建逆邻接表
• 在邻接表中，s->t 表示 s 先于 t 执行，即 t 依赖于 s
• 在逆邻接表中，s->t 表示 s 后于 t 执行，即 s 依赖于 t
• 递归处理每个顶点，先输出其可达所有顶点，再输出自己

时间复杂度：O (V+E)

# 利用拓扑排序检测环

对于 Kahn 算法，如果最终输出顶点个数少于图中顶点个数，也就是图中还存在入度不是 0 的顶点，就说明图中存在环

# 单源最短路径

例如地图做优出行路线
适用于场景抽象成有权图的搜索
单源最短路径算法不仅能求得单个源点到单个终点的最短路径，还能一次性求得单个源点到多个终点的最短路径

# Dijkstra 算法

类似于广度优先搜索，每次找到与起点最近的顶点，往外扩展

• 用一个优先级队列记录已经遍历的顶点
• 取与起点路径长度最小顶点进行扩展

构建于有向有权图之上，要求不能存在负权边

• 将所有顶点除初始顶点外的距离初始化为 int.max
• 将起始顶点距离初始化为 0，放入优先级队列中
• 从优先级队列中取出距离最短的顶点，然后考察该顶点可达的所有顶点
• 若顶点距离加上前往考察顶点边权重，的值小于考察顶点距离，则将其距离更新为顶点距离 + 权重，并将考察顶点加入优先级队列（重复该过程）

时间复杂度：O (ElogV)

# 多源最短路径

# Floyd 算法

Floyd 算法：可以一次性计算出图中任意两个顶点之间的最短路径
与 Dijkstra 算法一样，既可以处理有向图，也可以处理无向图，但 Floyd 算法允许图中存在负权边（但不允许存在负权环）
该算法利用了动态规划思想，状态转移方程式：

• dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

多阶段决策模型：将整个算法划分为 v 个阶段，每个阶段引入一个中转节点，基于上一个节点状态，推导下一个阶段状态
时间复杂度：O (V^3)

# 启发式搜索

heuristically search algorithm

# A * 算法

能实现快速寻找次优路线，对 dijkstra 算法的优化改造
dijkstra 算法可能跑偏，因为其主要按照顶点与起点的路径长度排出出队顺序，与起点越近的顶点，就会越早出队，但是并未考虑其与终点距离

• 因此，将顶点到终点距离也考虑进去，综合判断哪个顶点应该先出队列，避免跑偏

不过，尽管 A * 算法可以更加快速地找到起点到终点的路线，但并不能像 Dijkstra 算法那样找到最短路径

• A * 算法只要找到终点即结束，不会考察所有路线
• Dijkstra 算法则是终点出队结束，实际上考察了从起点到终点所有路线

启发式搜索算法利用估价函数避免跑偏，贪心地朝着最有可能到达终点的方向前进，因此找出并非最短路径，而是次优路径。但工程中路径规划问题往往不需要如此精确，因此启发式搜索算法能更好地平衡路线质量和执行效率，应用更加广泛

# 最小生成树：随机生成迷宫地图

# 什么是最小生成树

假设图包含 V 个顶点和 E 条无向有权边，要连通所有顶点，至少需要 V-1 条边（对于一个连通图，V-1 肯定小于或等于 E）

• 这 V-1 条边和 V 个顶点构成一棵树，称为生成树
• 图的生成树并不是唯一的，如果某棵生成树包含的 V-1 条边的权重和最小，那么这棵树就称为最小生成树（Minimum Spanning Tree，MST）

最小生成树在现实生活中应用就很多，例如 V 个城市建立通信网络最省铺设线路方式、道路建设等

# Kruskal 算法

贪心算法思想

• 利用并查集，初始时每个顶点对应一个集合，按照权重从小到大依次考察每条边
• 如果某条边对应的两个顶点不在同一个集合中，就将这条边选入最小生成树中，并将两个顶点对应集合合并
  • 若某条边对应两个顶点在同一个集合，说明两个顶点已经连通，若再添加一条边会导致形成环
• 依此类推，考察每条边，直到最小生成树中包含 V-1 条边为止

时间复杂度：O (ElogE)

# Prim 算法

同样利用贪心算法思想
在 Prim 算法中，使用优先级队列存储待考察顶点、以及前驱顶点与这个顶点之间的边的权重

• 先初始化一棵只包含图中最小边的最小生成树
• 基于当前的最小生成树，考察与最小生成树相连的所有边，找到权重最小且加入不会导致最小生成树中包含环的那个边，将这个边加入最小生成树
• 依此类推，重复第二步，直到最小生成树中包含 V-1 条边

具体步骤

• 初始选择一个顶点，将该顶点相连的边放入优先级队列
• 从优先级队列中取出队首元素
• 若边的两个顶点均已访问，则不进行任何处理，跳入下一轮
• 若边对应顶点中，有一个顶点未访问，则将这条边加入最小生成树中，并考察与其相连的所有边
• 直到有 V-1 条边出队，此时即为最小生成树

时间复杂度：O (ElogE)

# 随机 Prim 算法

将迷宫中元素分为两类：道路、墙

• 初始迷宫没有任何道路，可以将迷宫中每个单元格看作图中一个顶点，墙看作一条边
• 一堵墙要么连接左右两个道路单元格，要么连接上下两个道路单元格
• 在这样一个图上，寻找一棵生成树，生成树中包含的边代表墙将被打通（移除）
• 因为生成树包含所有的顶点，且连通所有的顶点，将生成树中边对应的墙从迷宫地图移除，所以所有这样的道路单元格就打通了
• 任选一个迷宫的起点和终点，都会有相应的通路

随机 Prim 算法与 Prim 算法处理思路几乎相同，唯一区别在于将优先级队列改为了随机队列，从随机队列取出的元素是随机选择元素，而非权重最小元素

• 对于随机生成迷宫问题，抽象出来的是无权图，只需要求得生成树即可满足要求

# 最大流

针对一张有向权图，选定两个顶点分别作为源点 s 和汇点 t，计算从源点到汇点的最大流量

• 即源点可以发出的最大流量，也等于汇点可以接受的最大流量

最大流算法很多，大体可以分为两类：

• 基于增广路径（augmenting path）的算法
• 基于推送 - 重贴标签（push relabel）的算法

例如应用于网络流

# Ford-Fulkerson 方法

基于增广路径
之所以称为方法而非算法，是因为其只给出了求解最大流框架思路，而非具体实现
基本原理非常简单：即通过不停地在残余网络中寻找增广路径来求解最大流。不过也需要对基本原理进行修正，通过增加反向边对之前的增广路径实现『改道』

• 用 g [i][j] 表示顶点 i 到顶点 j 的边的权值 (容量)，初始从源点到汇点的最大流值 maxflow=0
• 在图中找出一条从源点到汇点的可达路径 p
  • 假设路径中最小边的权值是 delta，也就表示这条路径可以输送 delta 大小的流量
• 将 delta 值加到 maxflow 上，并将路径 p 中所有边的容量都减去 delta
• 这条流量为 delta 的路径称为增广路径，将增广路径从图中移除后，剩下的图即为残余网络，使用 c [i][j] 记录残余网络中顶点 i 到顶点 j 的残余容量
• 不停在残余网络中寻找增广路径，然后增加 maxflow 值 -> 移除增广路径，直到残余网络中没有增广路径为止
• 最后得到的 maxflow 值就是图的最大流，此时 g [i][j]-c [i][j] 就是对应 maxflow 每条边流过的流量

注 1：指的是所有路径加起来的流量，以及所有可以自己独立运行，不互相干涉的路径
单纯像上述计算，会有缺陷，可能找出的不一定是最大流

• 调整方式：其它逻辑不变，当找到一条增广路径后，不仅将其从图中移除，还会将反向的增广路径添加至残余网络
• 即，例如找到 i~j，将其流量减掉后，反向添加 j~i 的流量（即，使存在反向边）

# Edmonds-Karp 算法

利用广度优先搜索实现的 Ford-Fulkerson 方法称为 Edmonds-Karp 算法

# 最大二分匹配

对于一个二分图，图中顶点分为左右两个部分，所有的边都横跨左右两部分，起始顶点在左，结束顶点在右
如果某两个顶点有边相连，称其为可匹配，一个顶点最多与一个顶点匹配成功
找出二分图中最大可匹配树，即为最大二分匹配

• 例如单身交友联谊匹配问题

可在二分图上补充两个顶点，一个源点，一个汇点。源点连接左半部分，汇点连接右半部分，即可转换为最大流问题

# 第十章 贪心、分治、回溯和动态规划

# 贪心算法（greedy algorithm）

应用：霍夫曼编码 (Huffman coding)、Prim、最小生成树等
针对一组数据，事先定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大

• 套用贪心算法模型
• 尝试用贪心算法解决；每次选择对限制值同等贡献量的情况下，对期望值贡献最大的数据
• 举例验证算法是否正确

注：使用贪心算法解决问题，并不总能给出最优解

• 主要原因在于贪心选择过程中前面的选择会影响后面的选择
• 例如即便第一步选择了最优解 (权值最小)，但也可能因为这一步的选择，导致后面可选择的路径不是最好的

对于贪心算法，最难的是将要解决的问题抽象成贪心算法模型，只要完成这一步，贪心算法就会很简单

# 霍夫曼编码

霍夫曼编码是一种非常有效的编码方法，广泛应用于数据压缩中，压缩率通常为 20%～90%
霍夫曼编码使用一种特别的方法为信号源中的每个符号设定二进制码。出现频率更大的符号将获得更短的比特，出现频率更小的符号将被分配更长的比特，以此来提高数据压缩率，提高传输效率

• 其不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率
• 根据频率不同，选择不同长度的编码，使用这种不等长的编码方法进一步提高压缩效率
• 由于编码不定长，因此解压缩时比较复杂，另外为了避免歧义，要求各个字符编码之间不能出现某个编码是另一个编码前缀的情况

编码方式

• 将每个字符看作一个节点，并把对应的出现频率一起放到优先级队列中
• 从优先级队列中取出出现频率最小的两个节点 A、B
• 新建一个节点 C，其频率设置为两个节点之和，然后将两个节点设置为 C 节点的子节点
• 将 C 节点放入优先级队列中（A、B 节点将标记为已处理）
• 重复操作直到队列没有未处理数据，最终将得到一棵霍夫曼树
• 霍夫曼树构造完成对树进行编码，左子节点标记为 0，右子节点标记为 1（左 0 右 1），从根节点到叶子节点的路径就是叶子节点对应的霍夫曼编码（二进制）

# 分治算法

分治算法（divide and conquer）核心思想其实就 4 个字：分而治之

• 将原问题划分成 n 个规模更小并且结构与原问题相似的子问题，递归地解决这些子问题，然后合并结果得出原问题解

条件

• 原问题与分解成的小问题具有相同的结构
• 由原问题分解成的子问题可以独立求解，相互没有相关性（与动态规划的明显区别）
• 具备分解终止条件
• 可以将子问题合并成原问题的结果

# 应用示例

求一组数据的逆序对个数
我们使用一组数据中包含的有序对或逆序对个数来表示有序度或逆序度

• 有序度：一组数据的有序程度
• 逆序度：一组数据的无序程度

使用归并排序，排序合并两个元素组时顺便统计：合并时判断左边元素是否大于右边元素进行统计

# 回溯算法

如深度优先搜索即利用回溯算法思想
我们一生中，会遇到很多重要的『岔路口』，每个选择都会影响我们今后的人生。有的人在每个岔路口都能做出正确的选择，生活、事业达到一个新的高度。而有的人一旦选错，最后可能碌碌无为。
贪心算法，每次面对选择时，都能做出『当下』最优选择，期望这一局部最优使我们达到全局最优。但是，贪心算法不一定能得到最优解。

# 理解

回溯的处理思想有点类似枚举（或穷举），枚举所有的解，找出其中满足期望的解

• 为了有规律枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段
• 每个阶段都会面对一个『岔路口』，先随意选择一条路走，当发现这条路走不通时 (不符合期望解)，就回退到上一个『岔路口』，另选一种走法继续走

# 应用

• 八皇后问题
• 0~1 背包问题（经典解法是动态规划，回溯算法也可以，但性能没那么好）
• 正则表达式匹配
• 图的着色
• 旅行商
• 数独
• 求全排列

# 动态规划

动态规划比较适合用来求最值问题，如最大值最小值等，可以显著降低时间复杂度，提高代码执行效率
大部分动态规划能解决的问题，也可以通过回溯算法解决，不过时间复杂度较高
动态规划可以避免重复计算，并利用上一阶段的最优状态来推导下一个阶段的状态，但是动态规划的空间复杂度也提高了，相当于空间换时间的算法思想

# 理论

一个模型和三个特征

• 一个模型指动态规划适合解决的问题的模型：多阶段决策模型
  • 一般用动态规划来解决最优问题，并把解决问题过程划分为多个决策阶段，每个决策阶段对应一组状态
  • 寻找一组决策序列，经过这组决策序列能够产生最终期望求解的最优指
• 三个特征
  • 最优子结构：问题的最优解包含子问题的最优解，可以通过子问题最优解推导出问题最优解（后面阶段状态可以通过前面阶段状态推导而来）
  • 无后效性：在推导后面阶段状态时，只关心前面阶段状态的状态值，不关心这个状态是如何推导出来的。某阶段状态一旦确定，就不受之后阶段的决策影响
  • 重复子问题

# 两种解题方法

状态转移表法

• 先设计一个状态表（一般是二维的）
• 每个状态包含 3 个变量：行、列和数组值
• 根据决策先后过程，分阶段填充状态表中的每个状态
• 将递推填表过程翻译成代码

状态转移方程法

• 有点类似递归思路：需要分析某个问题如何通过子问题来求解，找最优子结构，根据最优子结构写递推公式，即状态转移方程

# 四种算法对比

贪心、回溯、动态规划可以划分为一类，分治可以单独作为一类。前三个算法解决问题模型多数可以抽象成多阶段决策模型，分治虽然也是求最优解，但大部分不能抽象为多阶段决策最优解模型
回溯是个比较万金油算法，对于能用动态规划、贪心解决的问题基本也能用回溯解决。回溯相当于穷举搜索，穷举所有情况对比得到最优解，因此时间复杂度较高，为指数级别，只能用于解决小规模问题
在重复子问题上，动态规划和分治算法区别明显：分治算法要求分解后的子问题不能有重复子问题，动态规划正好相反，正是为了解决分解后子问题有重复而存在
贪心实际上动态规划的一种特殊情况，具有贪心选择性：通过局部最优解能产生全局最优选择

# 总结

总之，比较推荐，图文并茂。就算之前知道的，说不定都会有新的认识