【手册】算法与数据结构手册 - hippowc/hippowc.github.io GitHub Wiki

时空复杂度分析

时间复杂度

事后分析，通过实际跑代码评估时间；问题：依赖测试环境、受数据规模影响
大O复杂度表示法，目前比较通用的分析方法

大O复杂度表示法

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

代码执行时间T(n)与每行代码执行次数成正比，公式表示：T(n) = O(f(n))，T(n)表示代码执行时间，n表示数据规模大小，f(n)表示每行代码执行次数总和，O表示T(n)与f(n)成正比

使用方法

只关注循环次数最多的一段代码
加法法则：总的时间复杂度等于量级最大的那段代码的时间复杂度，其他可以舍弃
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见时间复杂度量级

多项式量级

常量阶：O(1)
对数阶：O(logn)
线性阶：O(n)
线性对数阶：O(nlogn)
平方阶：O(n^2)...O(n^n)

非多项式量级:性能较差的算法

指数阶：O(2^n)
阶乘阶：O(n!)

关于O(logn)

譬如这种：

i = 1;
while(i <= n) {
    i = i * 2;
}

需要计算这段执行了多少次，其中i的取值是等比数列，1，2，4 。。。即：2^0, 2^1，，， 2^x，即计算 2^x = n 时 x的值，即x = log2 n
由于对数之间是可以互相转换的，在采用大 O 标记复杂度的时候，可以忽略系数

O(m+n), O(m*n)

当两个数据规模大小不确定时，不能简单使用加法法则忽略掉其中一个，所以保留为O(m+n)，不过乘法法则可以继续适用

空间复杂度

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

也是看数据规模最多的代码所占空间的大小
讨论空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

常见的空间复杂度量级

O(1), O(n), O(n^2)；其他的像O(logn), O(nlogn)平时用不到

具体情况的时间复杂度

同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。

最好、最坏情况时间复杂度，

在实际情况中，根据具体数据情况，同一种算法的时间复杂度是不确定的

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

平均情况时间复杂度

将每一种情况的概率因素考虑进去，加权求和再除以总数得到的平均值

均摊时间复杂度

对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。

数据结构

数据结构和算法密不可分，特定数据结构会有特定的算法，及其支撑的操作，以及适用的场景

概览

基础数据结构
- 数组
  - 优：根据下标随机访问
  - 劣：
    - 插入删除时为了维护连续性而需要数据移动
    - 扩容需要拷贝
- 链表（单链表、双向链表、循环链表）
  - 优：无需连续空间，插入删除方便
  - 劣：
    - 需要遍历查找
    - 单个节点需要更多的存储空间
衍生数据结构：基于不同应用场景产生的数据结构
- 栈：可基于数组或链表
  - 应用场景：函数栈、表达式求值、括号匹配
  - 优化点
    - 增加栈顶指针（数组下标），可以O(1) 增删改查栈顶元素
- 队列：可基于数组或链表，操作受限，只在队头、队尾增删
  - 应用场景：广度优先搜索
  - 优化点
    - 增加队头、队尾指针，可以O(1)增删改查队头队尾元素
  - 衍生数据结构
    - 循环队列
      - 优化点
        
        通过循环解决数组插入时数据迁移的问题
- 哈希表或散列表：基于数组+链表（优化：数组+红黑树）
  - 应用场景：缓存，等快速根据key值查询数据场景
  - 优化点：
    - 哈希函数：将key值转换为数组下标，key值可能是整型、浮点、字符串、日期等
    - 基于数组下标随机访问。根据key值通过hash函数计算数组下标，实现O(1)增删改查
- 有序数组：基于数组
  - 应用场景：通用查询场景
  - 优化点
    - 数据有序存储，便于查找
      - 排序：冒泡、插入、选择 O(n)^2；归并、快排 O(nlogn)；桶排序，计数排序，基数排序O(n)
    - 二分查找，O(logn)
- 跳表：基于链表
  - 应用场景：通用查询、修改、删除
  - 优化点：
    - 有序链表 + 链表索引，使得查询、插入、删除效率达到O(logn)
- 二叉查找树：基于数组或链表
  - 应用场景：通用查询、修改、删除
  - 优化点：
    - 树形结构，弱有序，通过树结构使查询、插入、删除操作效率达到O(logn)，有序数组插入删除操作为O(n)
- 堆：基于数组或链表
  - 应用场景：topK（合并有序小文件），优先级队列，中位数
  - 优化点：
    - 树形结构，通过维护最值在堆顶，达到取最值效率O(1)

数组

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

操作

查找
插入
删除通过数组下标来维护某个节点

特点

连续的内存空间
相同类型的数据。

优势

数组可以实现随机访问。数组是适合查找操作，但是查找的时间复杂度并不为 O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是 O(logn)。正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

劣势

为保证数组连续性，在进行插入、删除操作是需要平移相关数据。如果数组是有序的，插入一条，需要将其他向后平移，删除一条，需要将其他向前平移，那么时间复杂度是O(n)
- 优化思路
  - 如果数组无序，知识存储的一个集合，插入时可以将在当前位置的数组放到数组尾部，删除也可以从尾部拿一个数据填补，那么时间复杂度就是O(1)
  - 关于删除，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移，这就是jvm标记删除的核心思想
扩容：数组会存在容量不够的问题，扩容需要拷贝所有数据
- 优化思路
  - 在初始化时做好容量预估

容器与数组

针对数组类型，很多语言都提供了容器类，相比有何优劣

ArrayList优势
- 封装数组的操作细节，譬如插入或删除时数组数据的移动
- 动态扩容
数组优势
- 可存储基本类型
- 多维数组表示更加直观

链表

链表通过“指针”将一组零散的内存块串联起来使用，链表通过指针将一组零散的内存块串联在一起。我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，叫作后继指针 next；头结点用来记录链表的基地址，尾结点指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点

单链表
循环链表：与单链表唯一区别在于尾结点指向链表的头结点
双向链表：它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点

操作

查找
插入
删除：需要知道前驱节点通过节点指针来维护某个节点

特点

不连续的内存空间

优势

不存在扩容问题
增删操作只需关心前后节点

劣势

无法随机快速查找某个节点，需要遍历，
单链表无法向前遍历，需要从头开始找
- 优化思路
  - 双向链表：双向链表多存储一个节点，会占用更多空间，但是在链表的各种操作以及有序链表中，比单链表效率高，所以应用场景也比单链表丰富
  - 循环链表

栈

后进者先出，先进者后出，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据

顺序栈：使用数组实现
链式栈：使用链表实现

操作

出栈
入栈

特点

只对栈顶进行操作
- 入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)
- 出栈的时间复杂度是 O(1)，入栈操作来说，最好情况时间复杂度是 O(1)，最坏情况时间复杂度是 O(n)，考虑到入栈时空间不足需要迁移的情况

队列

先进者先出，这就是典型的“队列”，队列跟栈一样，也是一种操作受限的线性表数据结构

顺序队列：使用数组实现
链式队列：使用链表实现

操作

出队
入队

特点

需要两个指针：队头、队尾
队头进队尾入

劣势

使用数组实现的队列，需要进行数据迁移
- 优化思路
  - 循环队列

其他高级队列

阻塞队列：入队、出队增加阻塞操作
并发队列：多线程安全
- 出队、入队加锁，低效
- CAS方法，高效

跳表

链表加多级索引的结构，就是跳表，这样可以支持类似“二分”的查找算法，空间复杂度为O(n)，时间复杂度为O(logn)，插入、删除操作的时间复杂度也是 O(logn)。

跳表动态更新

当不停地往跳表中插入数据时，如果不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。

散列表

散列表也叫hash表，散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展

特点

散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

哈希算法

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值，有很多应用：

安全加密
唯一标识
数据校验
散列函数
负载均衡
数据分片
分布式存储

树

二叉树

最常用的二叉树，特殊情况：

满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点
完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大

实现方式

基于指针或引用的链式存储法
基于数组的顺序存储法
- 如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针

操作

遍历：对于每个节点，时间复杂度O(n)
- 前序：中左右
- 中序：左中右
- 后序：左右中遍历递归伪代码

void preOrder(Node* root) {
  if (root == null) return;
  print root // 此处为伪代码，表示打印root节点
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  print root // 此处为伪代码，表示打印root节点
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  print root // 此处为伪代码，表示打印root节点
}

二叉查找树

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

操作

理想情况都是O(logn)

查找：先插根节点，如果相等返回，如果小于根，递归在左子树查找，如果大于根，递归在右子树查找
插入：
- 新插入数据一般都在叶子节点
- 如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，左子树也是
删除：
- 无子节点：父节点该指针置空
- 只有一个子节点：父节点直接指向其子节点。不需考虑之前是左节点还是右节点，因为左子树每个节点都小于该节点，右子树都大于该节点
- 有两个子节点：先找到该节点右子树最小节点，替换该节点，因为右子树最小节点大于该节点，肯定也大于左子树所有节点
  - 取巧：标记删除，不实际删除，但是比较浪费
查找最大节点、最小节点
查找前驱节点、后继节点

其他

重复数据处理：当做大于等于来看待
与散列表相比：
- 散列表数据是无序的，查找树可以通过中序遍历输出（O(n)）
- 散列表扩容耗时多，查找树稳定一些
- 散列表需要考虑散列函数、冲突解决、扩缩容等，查找树只需要考虑平衡问题

红黑树

红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的，红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比 AVL 树要低。

平衡二叉树：任意一个节点的左右子树高度相差不能大于1
平衡二叉查找树：同时满足平衡二叉树与二叉查找树
- 主要是为了解决在插入、删除操作后二叉树退化的问题
红黑树：红黑树的节点，一类标记为红色，一类标记为黑色
- 根节点是黑色
- 叶子节点都是黑色的空节点
- 任何相邻节点不能同时为红色
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点

红黑树实现

红黑树的平衡过程跟魔方复原非常神似，大致过程就是：遇到什么样的节点排布，我们就对应怎么去调整。红黑树的平衡过程其实并不通用，了解即可。

递归树

使用递归树分析时间复杂度

堆与堆排序

堆是一种特殊的树，堆的条件

堆是一颗完全二叉树
堆的每个节点都必须大于等于其子树中每个节点的值（大顶堆）或者每个节点都小于等于其子树中每个节点的值（小顶堆）

操作

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

插入
- 新插入节点放在堆的最后
- 自下而上堆化：与父节点对比，如果大于则交换，直到找到合适位置
删除堆顶元素
- 堆顶元素是最大值（最小值）
  - 删除后从左右节点找最大值替换，然后递归删除该子树的最大值，直到叶子节点
    - 但是有个问题：整个过程完成后，不一定是完全二叉树
- 自上而下堆化：删除后，将最后一个节点放在堆顶，与子节点对比，如果小则交换，直到找到合适位置

堆排序

基于堆数据结构实现的排序算法，叫做堆排序，排序算法时间复杂度O(logn)，且是原地排序，不稳定

建堆
- 排序算法一般针对数组类型，有两种方法，每个检点堆化是O(logn)，n个节点是O(nlogn)，但实际更小一点是O(n)
  - 1 从前往后处理，依次插入数据，自下而上建堆
  - 2 从后往前处理，自上而下建堆
排序
- 重复取堆顶元素，堆化，类似于删除操作

相比于快排

堆排序数据访问的方式没有快速排序友好。
对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。

堆的应用

优先级队列：一个堆就是一个优先级队列，取优先级最高看做取堆顶元素
- 合并有序小文件：100个有序小文件，合并成有序大文件；每个文件中各取一个放入堆中，将最小的放入大文件，然后在从去掉数据的这个文件中再取一条
  - 维护有序数组是否可以？主要是考虑找到后需要平移元素时间复杂度为O(n)
- 高性能定时器
求topk
- 譬如求topk大的数，维护一个k大小的小顶堆，然后取出数据与堆顶进行比较，如果小于堆顶则抛弃，否则替换堆顶，自上而下堆化
求中位数

图

顶点
边
度
方向
权重

存储方式

邻接矩阵：二维数组，可以表示无向图、有向图、带权图；
- 表示方法：A[][]表示一张图，i，j代表图中两个节点，如果 i->j有一条边，A[i][j] = 1，如果带权重3，A[i][j] = 3
- 优点：图的运算可以转换为矩阵运算
- 缺点：比较浪费空间
邻接表：类似哈希表，数组+链表
- 表示方法：一维数组标志所有顶点，后续链表表示与它有边的顶点
- 优点：存储空间小
- 缺点：
  - 查询效率较低，优化：针对后续链表做优化：可改为二叉查找树、红黑树、跳表、有序数组、哈希表等
  - 获取指向某个节点的所有节点比较困难；优化：增加逆邻接表，链表中存储所有指向该节点的节点

图的搜索算法

在执行效率方面，深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度是 O(V)。

广度优先搜索（BFS）
- 广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。
- 广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。
深度优先搜索（DFS）
- 是一种“走迷宫”的搜索策略，沿着一条路走到底，走不通后退回上一条岔路
- 深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。

算法思想

贪心

应用场景

针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。

举例

霍夫曼编码
Prim和Kruskal最小生成树
Dijkstra单源最短路径

方法论

每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
实际上，用贪心算法解决问题的思路，并不总能给出最优解

分治

分而治之，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

应用场景

原问题与分解成的小问题具有相同的模式；
原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别，等我们讲到动态规划的时候，会详细对比这两种算法；
具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

举例

map-reduce

方法论

分解：将原问题分解成一系列子问题；
解决：递归地求解各个子问题，若子问题足够小，则直接求解；
合并：将子问题的结果合并成原问题。

其他

分治与递归的区别：分治是一种处理问题的思想，递归是一种编程技巧

回溯

大部分情况下，回溯都是用来解决广义的搜索问题，回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。

应用场景

举例

深度优先搜索
正则表达式匹配
编译原理中的语法分析
0-1背包、图片着色等

方法论

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

动态规划

动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。

应用场景

一个模型、三个特征

一个模型：我们一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
三个特征：
- 最优子结构：我们可以通过子问题的最优解，推导出问题的最优解
- 无后效性：
  - 第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。
  - 第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。
  - 无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
- 重复子问题
  - 不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

举例

编辑举例
最长公共子序列问题

方法论

状态转移表法

一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决
先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树
从递归树中，我们很容易可以看出来，是否存在重复子问题
- 找到重复子问题后，有两种处理思路
  - 用回溯加“备忘录”的方法，来避免重复子问题。
  - 使用动态规划的解决方法，状态转移表法
    - 我们先画出一个状态表。状态表一般都是二维的，所以你可以把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。我们根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后，我们将这个递推填表的过程，翻译成代码，就是动态规划代码了
    - 尽管大部分状态表都是二维的，但是如果问题的状态比较复杂，也可能是高维的，这个时候就不适合使用状态转移表法来解决了

状态转移方程

状态转移方程法有点类似递归的解题思路。我们需要分析，某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。

有了状态转移方程，代码实现有两种方式：
- 递归加备忘录
- 迭代递推

算法

递归

递归需要满足三个条件

一个问题可以分解为几个子问题：这个分解是最关键的
这个问题与分解后的子问题，除数据规模不同，求解思路完全一致
存在递归终止条件

思路

找到递推公式
找到终止条件

问题

堆栈溢出
- 解决方案：限制递归最大深度
递归中的重复计算
- 解决方案：数据缓存

排序

排序算法一般基于数组的数据结构进行

排序算法分析

执行效率
- 最好、最好情况时间复杂度，平均情况时间复杂度，以及不同情况下原始数据形式
- 时间复杂度的系数、常数、低阶。实际情况中可能n量级不大，这时候不能简单使用加法原则忽略低阶。
- 比较次数或者交换（移动）次数
内存消耗
- 原地排序：空间复杂度为O(1)
稳定性

排序算法选择

O(n^2) 的三种方式：冒泡、插入、选择

优选：插入排序
- 选择排序不稳定
- 冒泡排序的赋值操作要多于插入排序
适合小规模排序

O(nlogn) 的两种方式：归并、快排

数据量小优先使用归并排序
数据量大使用快排

快排伪代码

// 快速排序，A是数组，n表示数组的大小
quick_sort(A, n) {
  quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r为下标
quick_sort_c(A, p, r) {
  if p >= r then return
  
  q = partition(A, p, r) // 获取分区点
  quick_sort_c(A, p, q-1)
  quick_sort_c(A, q+1, r)
}

归并伪代码

// 归并排序算法, 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])
}

查找

基于有序集合的查找：二分查找，复杂度O(logn)

依赖条件

依赖顺序表结构，也就是数组。因为需要按照下标随机访问
有序数据
数据量不宜过大或过小

应用变形

查找第一个值等于给定值的元素或者查找最后一个值等于给定值元素。需考虑重复值
查找第一个大于给定值的元素或查找最后一个小于给定值元素

字符串匹配

主要解决问题，在一个主串A中，寻找是否包含有模式串或者子串B

BF算法：Brute Force，暴力匹配算法，也叫朴素匹配算法
- 算法思路：在主串中，检查起始位置分别是 0、1、2....n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。
- 复杂度O(m*n) m为子串长度，n为主串长度
RK算法
- 算法思路：基于BF进行优化，不逐个比较字符是否相等，而是比较子串的哈希值。
  - 通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小，哈希值是一个数字，数字之间比较是否相等是非常快速的
  - 哈希算法：把字母看做26进制的数字，从而计算子串的数值
  - 复杂度：计算主串所有哈希值 O(n)，计算子串哈希值O(1)，比较所有哈希值O(n)，由于哈希值可能重复，遇到相等的可以再进一步比较字符串是否相等
BM算法：
- 算法思路：在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位。
  - 坏字符规则
  - 好后缀规则
- 复杂度：最好情况O(n/m)
KMP算法：
- 算法思路：与BM类似。在模式串与主串匹配的过程中，当遇到不可匹配的字符的时候，我们希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况。
  - 好前缀规则
- 复杂度：O(n+m)

trie 树

字典树，它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

算法思路：Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

主要操作

构造trie树
- trie树是一颗多叉树，经典的存储结构，每个节点类似散列表，存储26个字母以及对应的下标关系，以及后续节点的指针
  - 但是这样空间会浪费严重
- 复杂度：O(n)，n为所有字符串的长度
在trie树种查找
- 复杂度：O(k)，k为要查找的字符串长度

使用场景

场景：搜索引擎提示词
- 不适合字符串精确匹配查找，而是适用于前缀字符串查找
- 精确匹配查找更适合使用红黑树或者散列表来进行

AC自动机

单模式串匹配算法：一个主串一个模式串
多模式串匹配算法：一个主串多个模式串
算法思路：AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上

高级算法

拓扑排序

确定代码源文件的编译依赖关系

最短路径

计算地图软件的最优路径

位图

实现网页爬虫的URL去重

向量空间

实现一个简单的音乐推荐系统

B+树

Mysql数据库的索引实现原理

搜索

游戏中的寻路算法

索引

如何从海量数据中快速查找某个数据

并行算法

利用并行提高算法的执行效率

中间件中的数据结构

Redis

Redis 是一种键值（Key-Value）数据库。常用做内存数据库

数据结构

key：字符串
value：
- 字符串
- 列表
  - 压缩列表：通过一片连续的内存空间，来存储数据。不过，它跟数组不同的一点是，它允许存储的数据大小不同，实现方式为通过一个数字表明后续存储数据的长度
  - 双向循环链表
- 字典
  - 压缩列表
  - 散列表
- 集合
  - 有序数组
  - 散列表
- 有序集合
  - 压缩列表
  - 跳表

基础操作

持久化

搜索引擎

基础操作

搜集
- 思路：每个页面看作一个顶点。如果某个页面中包含另外一个页面的链接，那我们就在两个顶点之间连一条有向边。我们可以利用图的遍历搜索算法，来遍历整个互联网中的网页。
- 场景
  - 网页爬取
    - 广度优先遍历
  - 网页判重
    - 布隆过滤器
  - 原始网页存储
分析
- 场景：
  - 抽取网页信息
    - 字符串匹配算法
  - 分词并创建临时索引
    - 基于词典或规则进行分词
索引
- 场景：
  - 构建倒排索引
    - 多路归并排序，解决无法一次性加入内存并排序的问题
查询

高性能队列

数据结构

相比于基于链表实现的无界队列，实际情况中往往会使用基于数据实现的有界队列，由于实际机器的限制，场景一般是有界的

循环队列：解决数组数据迁移的问题
- 支持并发
  - 有锁
  - 无锁：两阶段写入，先加锁申请批量的空闲存储单元，申请过程仍是加锁的

微服务鉴权与限流

操作

鉴权
- 思路：基于url设置权限规则，然后使用请求url对规则进行匹配
- 场景：
  - url匹配
    - 精确匹配：trie树，有序数组
    - 模糊匹配：回溯
限流
- 思路：
  - 固定时间窗口限流：定一个时间起点，之后每当有接口请求到来，我们就将计数器加一；进入下一个时间窗口之后，计数器就清零重新计数。
    - 缺点：在某个时间区间内，会超出流控
  - 滑动时间窗口限流：
    - 在任意 1s 内，接口的请求次数都不能大于 K 次。我们就维护一个大小为 K+1 的循环队列，用来记录 1s 内到来的请求
    - 当有新的请求到来时，我们将与这个新请求的时间间隔超过 1s 的请求，从队列中删除。然后，我们再来看循环队列中是否有空闲位置。
    - 其他：
      - 令牌桶
      - 漏桶