数据结构

数组

数组的特性

  1. 数组是一种线性表，即一种元素之间有且只有前后顺序关联关系的数据结构
  2. 数组在计算机中的的存储是一段连续的空间
  3. 数组的元素都是相同的数据类型
  4. 数组支持随机访问，访问的时间复杂度是O(1)

数组的操作

数组的操作和其他线性表一样，主要支持插入、删除、查找的操作，由于数组存储于连续空间的特点，数组在插入，删除时候可能有数据搬迁的性能损耗，因此有一些针对性的优化措施。

插入优化：将指定元素插入到指定位置后，如果对顺序要求不严格，可以不将后续元素依次后移，只将插入的位置上之前的元素移到数组最末尾就可以了。

删除优化：为了避免删除元素时候数组搬迁的操作，可以在删除元素时候只将元素标记为删除状态，而不真正移除该元素。等到合适时机，再统一删除标记为删除的元素。

数组的封装

很多语言对底层的数组进行了一定的封装，提供给开发者更好用的数据结构。

需要封装起来的操作包括插入删除时候的数据搬迁和动态扩容。

数组下标为何从0开始？

  • 因为数组名称是一段连续空间的首地址，因此访问其他元素方法是首位地址 + “偏移”量。如果下标从1开始，在访问时候就需要进行加法运算。数组这种非常底层的数据结构要尽量保证性能，而从0开始就可以避免加法运算，在一定程度上保证了性能。

链表

链表的存储结构

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

链表中每个结点包括数据域和指针域（后继指针 next）。

头结点，第一个元素结点可能是头结点也可能不是头结点

尾结点

链表的类型

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

链表的操作

  • 插入
  • 删除
  • 查找

链表和数组的性能比较

时间复杂度 数组 链表
插入删除 O(n) O(1)
随机访问 O(1) O(n)

数组存储利用的是连续的内存空间，可以借助CPU缓存机制，预读数组中的数据，所以访问效率高。链表在内存中不是连续存储，对CPU缓存不友好，没办法有效预读。

数组数量需要提前指定，太大浪费，太小就需要动态扩容。

链表频繁的插入、删除会导致频繁的内存申请和释放，容易造成内存碎片。

如何用链表实现LRU算法

要点：

  • 维护一个有序单链表，越靠近尾部是越早之前被访问的结点
  • 访问数据时候，
    1. 遍历链表，若能找到，则将之抽出来插入到链表头部
    2. 若不能找到
      • 若链表已满，则删除尾部结点，将数据插入到链表头部
      • 若链表未满，则直接将数据插入到链表头部

几个链表的操作

  • 单链表反转
  • 链表中环的检测
  • 两个有序链表的合并
  • 删除链表倒数第n个结点
  • 求链表的中间结点

栈

1. 栈的定义

栈是一种操作受限的线性表，先入后出，后入先出

2. 栈的操作

  • 插入（入栈，push）
  • 删除（出栈，pop）

3. 栈的使用场景

当某种数据集合只涉及插入和删除数据，并且满足先入后出，后入先出的特性。应该首选“栈”

4. 栈的实现

需要数据容器和一个栈顶指针，如果有必要也可以加一个栈内元素个数

  • 链表：链式栈
  • 数组：顺序栈

5. 操作的复杂度

  • 时间复杂度：O(1)
  • 空间复杂度：O(1)

6. 动态扩容的栈

数组空间不够时候，申请一块更大的内存，然后把原数组中的数据都拷贝过去

所以动态扩容的栈就放用动态扩容数组来实现就行了

7. 栈的应用

  • 函数调用栈
  • 表达式求值（两个栈，一个存数字，一个存操作符）
  • 括号匹配
  • 浏览器前进后退功能

队列

1. 队列的概念

队列是一种操作受限的线性表数据结构

先进先出，后进后出

2. 队列的操作

  • 入队（enqueue）
  • 出队（dequeue）

3. 队列的实现

需要一个数据容器和一个队头指针（head）、一个队尾指针（tail），如果有必要，可以增加一个元素个数的属性

  • 顺序队列
  • 链式队列
  • 循环数组，循环数组可以在一定程度上解决顺序队列中，插入操作时候数组容量不够而导致的动态扩容。

4. 队列的应用

  • 并发队列
    并发队列是在入队和出队时候加锁，防止并发操作导致数据不一致。这样就可以保证安全地并发入队/出队操作了
  • 阻塞队列
    阻塞队列是在队列基本操作基础上增加阻塞操作，若队列满，则阻塞入队操作，若队列空则阻塞出队操作。阻塞某个操作指的是，当前不允许这个操作，而是把这个操作排队，等到可以进行操作时候，再让队列中的操作依次执行
    使用队列管理有限资源线程池时候，可以采用阻塞形式，即在不满足操作条件情况下（队列满时候的入队操作和队列空时候的出队操作）让入队、出队操作排队，等满足条件后再依次进行操作。也可以采用非阻塞形式，即不满足条件时候直接丢掉操作。

跳表

概念

链表加多级索引的结构，就是跳表

跳表查询数据时候，先在第一层索引中找到目标的范围，然后到第二层索引中继续缩小范围，直到最后一层数据层找到目标元素

跳表是一种动态数据结构，支持高效的插入、删除、查找等操作

性能

跳表的查询操作时间复杂度为O(logn)

跳表的插入、删除时间复杂度也是O(logn)

跳表的空间复杂度为O(n)

为了防止跳表在动态插入数据时候退化成单链表，需要跳表索引动态更新。动态更新的方式是：每次插入数据时候，同时插入索引，随机选择1-k层插入索引。

跳表支持的操作

  1. 插入
  2. 删除
  3. 查找
  4. 按区间查找
  5. 迭代输出有序序列

应用

为什么redis用跳表实现有序集合？

  1. 跳表支持高效地进行按区间查找数据
  2. 跳表更容易实现
  3. 跳表比较灵活，可以通过改变索引构建策略，有效地平衡执行效率和内存消耗

二叉树

1. 二叉树相关概念

  1. 树
  2. 根节点
  3. 父节点
  4. 子节点
  5. 兄弟节点
  6. 叶子节点
  7. 高度
  8. 深度
  9. 层
  10. 二叉树
  11. 满二叉树
  12. 完全二叉树

2. 二叉树的存储

  1. 链式存储
  2. 顺序存储
    完全二叉树使用顺序存储更加节省空间

3. 二叉树的遍历

  1. 前序（先根）
  2. 中序（中根）
  3. 后序（后根）

时间复杂度 O(n)

4. 二叉查找树

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

二叉查找树的操作

  1. 查找
    当前节点值等于目标值，返回之；否则，若目标值小于当前节点值，则在当前节点左子树中递归地查找；若目标值大于当前节点值，则在当前节点右子树中递归地查找
    复杂度 O(logn)
  2. 插入
    若目标值小于当前节点值，左子树为空则插入到左子节点位置，否则递归插入到左子树中；若目标值大于当前节点值，右子树为空则插入到右子节点位置，否则递归递归插入到右子树中
    复杂度O(logn)
  3. 删除
    分3种情况
    1. 要删除的节点无子节点，直接父节点指向它的指针置空
    2. 要删除的节点只有一个子节点，将父节点指向它的指针指向这个子节点
    3. 要删除的节点有两个节点
      1. 找到该节点右子树最小节点，将右子树最小节点替换该节点
      2. 删除右子树最小节点

删除也可以采用设置标志位的方式实现，优点是操作简单，缺点是浪费空间
复杂度O(logn)

二叉查找树的其他操作

  1. 查找最大节点
  2. 查找最小节点
  3. 查找前驱节点
  4. 查找后继节点
  5. 输出有序数据序列（中序遍历）

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

  1. 相同数据用一个链表存储
  2. 右子树的值大于等于当前的值，插入时候，顺序链到相同的值的右子树上

5. 为什么散列表性能优越，还是需要二叉查找树

原因

  1. 散列表无序，二叉树有序，可以高效地输出有序序列
  2. 散列表扩容耗时较多，平衡二叉查找树性能比较稳定
  3. 散列表有冲突时候，性能也很低，而且含有哈希函数耗时
  4. 散列表的构造更复杂，散列函数设计、冲突解决方法、扩容缩容；二叉平衡树只需要考虑平衡性这个问题
  5. 散列表为了性能考虑，装载因子不能太大，这样就会浪费一定的存储空间

图

1. 图的概念

  1. 顶点
  2. 边
  3. 度、入度、出度
  4. 有向图、无向图
  5. 加权图（带权图）

2. 图的存储

  1. 邻接矩阵
    邻接矩阵依赖一个二维数组，A[i][j]表示顶点i和j之间是否有边，带权图则表示权重
    优点：时间性能比较好
    缺点：邻接矩阵存储“稀疏图”（顶点很多但边不多）时候比较浪费空间
  2. 邻接表
    邻接表中有一个数组存储所有的顶点，每个顶点对应一个链表，其中存储这个顶点有边连接的其他顶点
    优点：存储节省空间
    缺点：使用时候耗费时间
    邻接表中的链表可以改成二叉查找树、跳表、散列表、有序动态数组等，以快速判断两个点之间是否有边

3. 社交网络中的好友关系存储

社交网络是一个图的结构，适合用图表示

社交网络是个稀疏图，因此适合用邻接表存储

为了快速获取被关注的粉丝列表，还需要一个“逆邻接表”

社交网络图比较大，内存中存放不下，需要在磁盘上存储，并且采用分布式存储，这就需要用到hash将数据分片，比如按节点分片，将一部分节点存储在一个磁盘上，其他节点存放在另一个磁盘上

4. 图的搜索算法

图的搜索算法，最直接的理解就是在图中找出从一个节点出发到另一个节点的路径

最简单的两个算法

  1. 深度优先（DFS）
  2. 广度优先（BFS）

其他一些搜索算法，如A、IDA算法是基于DFS和BFS的优化

广度优先搜索

  1. 用到3个辅助变量
  3. 1. visited：数组，用来记录顶点是否已经被访问
  4. 2. queue：队列，用来保存当前正在访问的顶点可以触达的顶点，以便后续继续搜索
  5. 3. pre：数组（长度 === V）用来记录搜索路径，p[w]表示顶点w的前驱节点
  7. 时间复杂度
  9. O(V + E)
  11. 空间复杂度
  13. visited、queue、pre，O(V)
  15. 广度优先可以取到最短路径

深度优先搜索

  1. 用到两个辅助变量
  3. 1. visited
  4. 2. pre
  6. 时间复杂度
  8. O(V + E)
  10. 空间复杂度
  12. O(V)
  14. 深度优先搜索可能得不到最短的路径

散列表（哈希表）

1. 概念

  • 键（关键字）
  • 散列函数
  • 散列值
  • 装载因子

2. 散列表简述

散列表是利用数组的随机访问特性，实现对数据的快速存取操作的一种数据结构

散列表的工作原理是

存数据

  1. 数据的标识（key，键）经过散列函数处理，得到散列值
  2. 用散列值作为数组下标，保存该条数据

取数据

  1. 数据的标识（key，键）经过散列函数处理，得到散列值
  2. 通过散列值作为数组下标，访问相应的元素

可以看到存取数据的时间复杂度都是O(1)

散列函数要求

  1. 返回值是一个非负整数
  2. 键相同，散列值相同同
  3. 键不同，散列值不同

散列冲突的解决方法

  1. 开放寻址法：线性探测、二次（二次方）探测、双重散列
  2. 链表法

装载因子 = 填入表中的元素个数 / 表长，装载因子越大，说明空闲位置越少，冲突越多，散列表性能（存取操作的时间性能）会下降

3. 实现工业级水平的散列表

工业级水平散列表的要求

  1. 支持快速查询、插入、删除操作
  2. 不能过分消耗内存空间
  3. 性能稳定，不会退化到无法接受的情况

实现

  1. 设计一个合适的散列表
    散列函数设计不能太复杂
    生成的散列值要尽可能随机且均匀分布
  2. 定义装载因子阈值，设计动态扩容策略（和动态缩容）
    动态扩容（缩容）后，需要数据搬迁，会使之前的数据散列值重新计算
    阈值要考虑恰当，太大，会导致冲突过多，太小，会导致内存浪费严重。综合考虑空间资源和时间性能要求。
    高效扩容：为防止扩容瞬时压力，可以将扩容操作穿插在插入操作的过程中，扩容时候，只申请新空间，不搬迁数据。每次插入新的数据时候，在新的空间插入，并把老的空间中一个数据搬迁。这个过程中，查询数据时候，可以先从老的散列表中取，取不到再从新的空间取。
  3. 选择合适的散列冲突解决办法
    开放寻址法和链表法的优缺点
    开放寻址法
    链表法（可以用红黑树代替链表法） 
  1.  优点
  2.      1. 数组访问可以利用CPU缓存，速度优于链表
  3.      2. 序列化简单
  5.  缺点
  6.      1. 删除数据时候麻烦
  7.      2. 装载因子大的时候，存取代价更高。如果限制装载因子不能太大，那么就会占用更多空间。
  9.  适用场景：数据量小、装载因子小
  1.  优点
  2.      1. 内存利用率更高
  3.      2. 对装载因子的容忍度更高，装载因子大的时候，性能下降相对缓慢
  4.      3. 支持更多优化策略（比如用红黑树、跳表代替链表）
  5.  缺点
  6.      1. 对于较小的数据，更耗内存（指针域）
  8.  适用场景：大对象、大数据量

3. 其他

散列表和链表经常结合使用，链表的顺序结构可以支持常见的顺序访问和高效的插入删除（O(1)操作）。结合散列表则可以让查询效率接近O(1)。

递归

1. 使用递归的问题需要满足的条件

  1. 一个问题可以分解为几个子问题的解
  2. 子问题与原问题结构相同
  3. 存在递归终止条件

2. 编写递归代码关键

  • 找出递推公式
  • 找出递归终止条件

3. 注意事项

  • 堆栈溢出
  • 防止重复计算

4. 递归写法改为非递归写法

  • 所有递归的写法都可以改为非递归的形式
  • 非递归的形式即迭代循环的形式
  • 可能需要借助辅助栈也可能不需要

5. 递归特点

优点：

  1. 代码简介

缺点：

  1. 可能存在堆栈溢出
  2. 可能存在重复计算
  3. 函数调用耗时多
  4. 空间复杂度高

6. 尾递归

尾调用为自身的递归是尾递归。

尾递归由于在return调用自身的时候，变量环境都已确定，因此可以不用保留当前函数栈信息。

所以尾递归可以节省创建函数调用栈的时间和空间。

  1. // 普通的斐波那契数列
  2. function fib(n) {
  3.     if (n <= 2) {
  4.         return 1;
  5.     }
  6.     return fib(n - 1) + fib(n - 2);
  7. }
  9. // 尾递归的斐波那契数列
  10. function tailfib(n, acc1, acc2) {
  11.     if (n < 2) {
  12.         return acc1;
  13.     }
  15.     return tailfib(n-1, acc2, acc1 + acc2);
  16. }

算法

算法思想

1. 贪心算法

1. 贪心算法要素

  1. 最优子结构
  2. 贪心选择性

2. 实例

  1. 钱币找零
    有1元、5元、10元、20元、100元钱币若干，用来支付k元，最少要用多少纸币？
    先用面值大的支付，如果面值大的不够或者超额，换用更小一点面值的纸币，以此类推
  2. 区间覆盖
    有n个区间，起始端点和结束端点分别是(l1, r1), (l2, r2), … ,(ln, rn)。我们从这n个区间中选出一部分区间，这部分区间满足两两不相交，最多能选出多少个区间呢？
    首先将所有区间按照起始端点升序排列
    遍历排好序的区间序列，每次取出一个区间 
  1.  1. 如果这个区间左端点和已经覆盖的区间重叠
  2.      1. 如果这个区间的右端点也和已经覆盖的区间重叠，将上一个区间丢弃，选择当前区间
  3.      2. 如果这个区间的右端点和已经覆盖的区间未重叠，丢弃这个区间
  4.  2. 如果这个区间左端点和已经覆盖的区间未重叠，pick it
  1. 哈夫曼编码

哈夫曼编码是一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在20%~90%之间

哈夫曼编码的思想

  1. 1. 哈夫曼编码考虑字符个数，然后对字符进行二进制编码
  2. 2. 在编码过程中还考虑到字符的频率，出现频率越高，编码长度越小
  3. 3. 编码需要保证各个字符之间不会出现一个编码是另一个编码的前缀的情况

哈夫曼编码的步骤

  1. 把每个字符看成一个节点，每个节点包含频率的值
  2. 把字符按照频率放到优先级队列中
  3. 每次从队列中取出频率最小的两个节点A、B，新建一个节点C，频率为两个节点之和，A、B作为C的两个子节点。再将C节点放到优先级队列中，重复这个过程，直到队列中没有数据
  4. 然后给树中每一条指向左子节点的边标记为0，指向右子节点的边标记为1，从根节点到叶结点的路径就是叶结点对应字符的哈夫曼编码

哈夫曼编码通过贪心算法保证高频字符处于树的更靠近根节点的位置，这样其编码长度就会比较短，由字符组成的文章使用哈夫曼编码就可以很大程度压缩了

2. 分治算法

分治算法能解决的问题，需要满足下面几个条件

  1. 原问题与分解的子问题有相同模式
  2. 原问题分解成的子问题可以独立求解，子问题之间没有相关性
  3. 具有分解终止条件
  4. 可以将子问题合并成原问题，并且合并的复杂度不能太高

分治算法实例

  1. 求序列的逆序对
    类比归并排序算法
  2. 二维平面n个点中距离最近的点对
    1. 按横坐标分治
    2. 先分别求左右两个区间内最小距离
    3. 再求左右两个区间之间最小距离，使用第二步计算出的距离进行限制
  3. mapreduce
  4. 外排序

3. 回溯算法

回溯算法很多时候应用在“搜索”这类问题上，即在一组可能的解中，搜索满足期望的解

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段面临多个选择，随意选择一个，发现其不符合期望时候，再回退到上一个选择，重新搜索。

回溯算法很适合用递归实现

常见问题

  1. 深度优先搜索
  2. 八皇后
  3. 0-1背包问题
  4. 图的着色
  5. 旅行商问题
  6. 数独
  7. 全排列
  8. 正则表达式匹配

【思考】

回溯算法实际就是暴力穷举法（当然可以在回溯基础上做一些剪枝优化），只不过回溯算法规定了穷举的具体实现步骤。

4. 动态规划

排序

0. 指标

  1. 时间复杂度
  2. 空间复杂度
    O(1)的空间复杂度，称为“原地排序”
  3. 稳定
    如果排序算法是稳定的，那么对于按照两种参数排序的需求，可以先按第一种参数排序，再按照第二种参数排序的方式实现。如果排序算法是不稳定的，则无法这样实现需求。

1. O(n²)

  1. 冒泡
  2. 插入
  3. 选择
算法 时间复杂度 空间复杂度 稳定性
冒泡 O(n²) O(1) 稳定
插入 O(n²) O(1) 稳定
选择 O(n²) O(1) 不稳定

算法简单，适合小规模数据排序

2. O(nlogn)

  1. 快排
  2. 堆排
  3. 归并
算法 时间复杂度 空间复杂度 稳定性
快排 O(nlogn) O(1) 不稳定
归并 O(nlogn)) O(n) 稳定
堆排 O(nlogn) O(1) 不稳定

快排的思想（partition），可以用来在O(n)的时间内找到第k大（小）元素。

3. O(n)

  1. 计数排序
  2. 基数排序
  3. 桶排序

4. 通用、高性能排序算法

如何实现一个通用、高性能的排序算法？

首先，线性复杂度的排序函数使用场景比较特殊，因此不能选择

小规模可以使用O(n²)，大规模应该选择O(nlogn)

归并排序由于需要占用较大的空间，因此堆排和快排使用的更多

快排最坏情况下的复杂度是O(n²)，为了优化，需要取分区点时候做一些处理。

  1. 1. 三数取中法
  2. 2. 随机法

通用排序算法可能会在数据规模小时候使用一种排序算法，在规模大时候使用另一种排序算法

比如，数据规模小时候，使用归并或者O(n²)排序，数据规模大时候，使用快排。因为数据规模小时候时间性能可能比O(nlogn)要好。而且快排还有两个问题，就是递归时候会导致调用栈过大；分区点不好时候，时间性能会退化到O(n²)。相应的优化的手段：自己实现一个栈；优化分区点

线性排序

1. 桶排序

思想

将要排序的数据分到几个有序的桶里，每个桶里的数据单独排序，然后把每个桶里的数据按顺序取出，组成的序列就是有序的了

条件

  1. 待排序数据可以分成m个桶，桶与桶之间有序
  2. 数据在各个桶内分布均匀

适合场景

外排

2. 计数排序

计数排序是桶排序的一种特殊情况

思想

如果待排序数据范围不大，最大为k。那么可以把数据划分成k个桶。然后每个桶内的数据都是相同的，因此桶内不需要排序。最后将所有数据依次取出，即可得到排序后的序列。

计数排序的具体实现并不在桶里保存待排序的完整数据项（因为待排序数据项可能比较大，比如考生的信息中除了分数之外还有别的信息，计数排序只维护分数的数据）。计数排序只维护一个”计数数组”和一个”累计数组”。它的具体实现过程如下

  1. 先遍历待排序序列，统计数据每个取值的个数，保存在”计数数组”中（比如60分的3个、98分2个、100分1个）
  2. 然后将”计数数组”顺序求和，得到”累计数组”，累计数组中下标为k的元素，值等于待排序数据中小于等于k的数据的个数
  3. 从后往前遍历待排序数据d，在”累计数组”中找到下标为数据值d-value对应的元素sum，这个sum就是该数据的序号，访问完这个数据后，将sum减一。这样再遍历到下一个值为d-value的元素时候，序号就是sum - 1了

条件

  1. 数据范围不大
  2. 非负整数（如果是小数，需要映射到整数范围）

说明

计数排序相对桶排序的好处是，不需要维护较大的待排序数据，只要维护一个较小的计数数组就行，空间复杂度较低

3. 基数排序

思想

比如对11位手机号排序，就可以选取一种稳定排序算法，从低位开始对数据排序，然后对次低位排序，一直到最按高位排序为止。

稳定排序算法可以采用桶排或者计数排序

条件

  1. 有多个”位”，可以”按位”比较
  2. 位之间有递进关系
  3. 每一位的取值范围不大，可以同桶排或计数排序，这样就可以做到O(n)的复杂度

二分查找

1. 二分查找简述

二分查找的时间复杂度O(logn)

二分查找可以用循环来实现，也可以用递归实现

二分查找条件

  1. 数据有序
  2. 用数组存储

二分查找不适用的场景

  1. 数据量太小（如果比较操作比较耗时，即使数据量小，二分查找也比较合适）
  2. 数据量太大，数据量太大的话，数据就不适合放在数组中存储

2. 二分查找变形

当有序数组中的数据有重复元素时候，二分查找会有一些变形问题

  1. 查找第一个值等于给定值的元素
  2. 查找最后一个值等于给定值的元素
  3. 查找第一个大于等于给定值的元素
  4. 查找最后一个小于等于给定值的元素

这些变形问题的思路类似，以第一个为例。

如果二分查找的数组中没有重复元素，则二分查找终止条件（即找到目标元素的判断条件）为，访问的当前元素等于目标元素。

对于第一个问题，只是将终止条件改变一下，变成“访问的当前元素等于目标元素，且其上一个元素不等于目标元素或者没有上一个元素”。

3. 总结

  1. 相对于散列表和二叉查找树，二分查找优点是内存消耗少，缺点是动态数据的性能差（数组的插入和删除的性能比较差）
  2. 在查找“近似”目标数据（如上面提到的4个变形问题）时候，二分查找更合适

模式匹配

0. 模式匹配简述

主要概念

字符串A中查找字符串B

  • A：主串（n）
  • B：模式串（m）

n > m

主要算法

  • BF、RK
  • BM
  • KMP
  • trie树
  • AC自动机

1. BF、RK算法

1. BF算法

暴力匹配

时间复杂度 O(n × m)

BF比较常用，原因

  1. 实际主串和模式串都比较小
  2. 算法简单，不易出错

2. RK算法

算法思想

  1. 对主串的 n - m + 1个子串分别求hash值
  2. 对模式串求hash值
  3. 将主串的n - m + 1个子串与模式串对比

因为数字之间比较更快

时间复杂度O(n)

hash算法的设计

以字符集字符数K为进制表示数值（如英文字母小写，26进制）

abc =>26º + 26¹ + 26²

26^n可以缓存下来

2. BM算法

1. BM算法简述

BM算法在模式匹配的对比过程中，当不匹配时候，尽量增加滑动个数来减少对比次数

BM算法从后往前比较（从模式串的最后一位向前）

主要有两种匹配方式

  1. 坏字符：从后往前，遇到不匹配的时候，是“坏字符”
  2. 好后缀：从后往前，遇到不匹配的字符时候，已经匹配了的字符叫做“好后缀”

2. 算法思想

坏字符

  1. 1. 坏字符从后往前，遇到不匹配的时候，是坏字符
  2. 2. 滑动，将坏字符与模式串中匹配（如果匹配上多个，选择靠后的那个），匹配结果xi和主串中的坏字符所在位置（si）对齐
  4. 坏字符思想可能出现si - xi为负的情况

好后缀

  1. 1. 从后往前，遇到不匹配的字符时候，已经匹配了的字符叫做“好后缀”
  2. 2. 在模式串中匹配好后缀
  3.     1. 如果匹配到，则将主串中的好后缀和模式串中匹配到的（如果匹配上多个，选择靠后的那个）对齐
  4.     2. 若模式串未匹配到好后缀，则在模式串所有前缀中匹配好后缀的后缀，如果有多个匹配上，则找出最大的那个，将主串中好后缀的后缀和模式串中匹配上前缀对齐

坏字符和好后缀都是利用了已知的信息（坏字符利用列某个字符没有匹配上的信息；好后缀利用了有些字符已经匹配上了的信息）来进行滑动距离优化，减少对比次数

BM算法计算在匹配过程中坏字符和好前缀的滑动距离，选择最大的那个作为滑动距离

【之所以可以在坏字符和好前缀中选择滑动距离最大的作为实际滑动距离，是因为坏字符和好后缀都能保证最小滑动】

3. 实现

坏字符的实现

模式串中坏字符的位置（靠后的）为xi，滑动时候需要计算这个位置

将模式串中每个字符最后出现的位置都记录在一个散列表中

好后缀的实现

需要记录两种信息

  1. 好后缀在模式串中匹配到的位置（如果有多个，取靠后的那个）suffix
  2. 好后缀是否有后缀可以和模式串的前缀匹配 prefix

预处理模式串，得到suffix和prefix

模式串：c a b c a b
0 1 2 3 4 5

后缀子串 长度 suffix prefix
b 1 suffix[1] = 2 prefix[1] = false
ab 2 suffix[1] = 1 prefix[1] = false
cab 3 suffix[1] = 0 prefix[1] = true
bcab 4 suffix[1] = -1 prefix[1] = false
abcab 5 suffix[1] = -1 prefix[1] = false

如何填充这两个数组

  1. 遍历模式串
  2. 拿模式串从0到i的子串与整个模式串求公共后缀子串
  3. 若公共后缀子串长度为k，就记录suffix[k] = j（j表示公共后缀子串的起始下标）
  4. 若j = 0，prefix[k] = true

4. 性能优化

  1. 只用好后缀而不用坏字符规则
  2. 极端情况下，模式串预处理性能较差（如 aaaaaaaa 时间复杂度为O(m²)），有一些方法优化这种情况的时间性能

3. KMP算法

1. 原理

KMP算法的思想也是将模式串与主串进行匹配，失败的话再进行滑动，根据模式串的性质让滑动的距离尽量大，这样就减少了对比的次数，从而提高了匹配的效率

在将模式串和主串对比时候，KMP算法从头向尾进行匹配，如果遇到一个不匹配的字符，将之前已经匹配上的字符称为“好前缀”，未匹配上的字符称为“坏字符”。

在遇到坏字符时候，应该如何向后滑动呢？

由于好前缀是已经匹配到主串的字符串，因此，只有当好前缀的一个前缀prefix和其等长后缀suffix匹配，将prefix和suffix对齐时候，才是一次有效的滑动，否则一定不匹配。

因此KMP算法需要计算模式串的每个前缀子串的最长可匹配前缀子串的结尾字符下标（next数组），这样在进行模式匹配时候，当遇到不匹配的字符串，可以根据已经匹配的字符串的快速找出滑动距离

模式串 ababacd

模式串前缀（好前缀候选） 前缀结尾字符下标 最长可匹配前缀字符串结尾字符下标 next值
a 0 -1（不存在） next[0] = -1
ab 1 -1 next[1] = -1
aba 2 0 next[2] = 0
abab 3 1 next[3] = 1
ababa 4 2 next[4] = 2
ababac 5 -1 next[5] = -1

2. 失效函数（next数组）的计算方法

【省略】

Trie树

【省略】

AC自动机

【省略】

堆

定义

  1. 堆是一个完全二叉树（除了最后一层，其他层都必须是满的，最后一层节点都靠左排列）
  2. 堆中每个节点的值都≥（或≤）其子树中每个节点的值

堆适合用数组存储

堆的操作

  1. 插入元素（从下往上堆化）
    将元素插入到最后一个位置，然后对比元素和父节点的大小，如果不满足堆性质，则交换当前元素和父元素，然后继续对比该元素和父元素的大小并酌情交换。直到满足堆的性质为止。
  2. 删除堆顶元素（从上往下堆化）
    删除堆顶元素后，将最后一个元素补到堆顶，然后从堆顶元素往下和子节点比较，若不满足堆性质则交换，然后继续比较，直到满足堆的性质。

堆排序

  1. 初始建堆（原地建堆）
    1. 从前往后遍历数组，从下往上建堆
    2. 从后往前遍历数组，从上往下建堆
  2. 排序（升序）
    首先创建一个大顶堆。然后先将堆顶元素和第n个元素（最后一个元素）交换，这样最后一个元素就是最大的元素了。但是交换后可能会破坏堆的性质，我们接下来将整个堆堆化，让它重新变成一个大顶堆。然后对前n-1个元素继续相同的操作。

堆的应用

  1. 优先级队列
    【使用堆做优先级队列，插入和删除（获取最高优先级任务）的时间复杂度都是O(logn)、用链表的话，插入的时间复杂度是O(n)，删除的时间复杂度是O(1)、用数组的话，插入和删除的时间复杂度都是O(n)】
  2. topK
    维护一个大小为k的堆
    时间复杂度是nlogk
  3. 中位数
    维护一个大顶堆一个小顶堆，遍历到一个元素时候，将其插入相应的堆中，并维护堆的平衡（两个堆元素个数尽量相等）
    每次插入一个新元素时候，时间复杂度是O(logn)。获取中位数的时间复杂度是O(1)

哈希

1. 哈希算法简述

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射规则就是哈希算法

优秀的hash函数需要满足的条件

  1. 从哈希不能反向推导出原始数据
  2. 对输入数据敏感（输入数据的微小变动会导致输出结果大不相同）
  3. 散列冲突的概率很小
  4. 执行效率要高

哈希算法应用

  1. 安全加密
  2. 唯一标识
  3. 数据校验
  4. 散列函数
  5. 负载均衡
  6. 数据分片
  7. 分布式存储

2. 哈希算法的应用

  1. 安全加密
    MD5（Message digest Algorithm）
    SHA（Secure Hash Algorithm）
  2. 唯一标识
    例如判断一张图片在一个数据库中是否存在，可以用图片的MD5作为标识
  3. 数据校验
    对文件计算MD5，可以判断是否被篡改
  4. 散列函数
  5. 负载均衡
    将请求的ip进行hash计算，得到结果对服务器列表个数取模，得到的就是路由到的服务器编号
    【之所以要先进行hash再取模，而不是直接取模，可能是因为hash计算可以让原数据更加无规律，分布更加均匀】
  6. 数据分片
    并行处理数据时候，可以将数据项进行hash，这样相同的数据项就被分配给同一台服务器进行处理
  7. 分布式存储
    一致性hash
    一致性hash解决的问题是分布式缓存扩容时候，可能会导致缓存穿透，雪崩效应