算法
2025-03-26 22:56:12 0 举报AI智能生成
算法
作者其他创作
大纲/内容
基础
数据结构
数组
链表
单向链表
双向链表
循环链表
跳表
在普通链表上简历索引
哈希
一致性哈希
队列
栈
树
红黑树
五个特性
根节点是黑色
叶子节点（NIL）是黑色
从根节点到叶子节点黑色节点的个数相同
节点为黑色或者红色
红色节点的两个子节点为黑色
优点
并不追求“完全平衡”——它只要求部分地达到平衡要求，
降低了对旋转的要求，从而提高了性能。
二叉搜索树
b树
定义
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）
和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于
K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键
属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
特性
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；
b+树
定义
其定义基本与B-树同，除了：
1.非叶子结点的子树指针与关键字个数相同；
2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树
（B-树是开区间）；
3.为所有叶子结点增加一个链指针；
4.所有关键字都在叶子结点出现；
特性
1. 所有关键字都出现在叶子结点的链表中（稠密索引），
且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3. 非叶子结点相当于是叶子结点的索引（稀疏索引），
叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；
b树和b+树区别
B树中同一键值不会出现多次，并且它有可能出现在叶结点，
也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，
并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡
因为B树键位置不定，且在整个树结构中只出现一次，
虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。
B+树相比来说是一种较好的折中。
B树的查询效率与键在树中的位置有关，最大时间复杂度与
B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。
而B+树的时候复杂度对某建成的树是固定的
B*树
定义
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；
特性
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3
b*和b+的区别
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数
据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结
点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分
数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的
关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点
与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增
加新结点的指针； 所以，B*树分配新结点的概率比B+树要低，空间使用率
更高；
AVL树
定义
相比于”二叉查找树”，它的特点是：
AVL树中任何节点的两个子树的高度最大差别为1。
失去平衡的可以概括为4种姿态
左左
左子树的左子树导致的失衡
左右
左子树的右子树导致的失衡
右左
右子树的左子树导致的失衡
右右
右子树的右子树导致的失衡
总结：发生问题的那个节点要成为根节点才能解决问题。
不管我们是执行插入还是删除操作,只要不满足上面的条件,
就要通过旋转来保持平衡,而旋转是非常耗时的,
由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。
哈夫曼树
是一种带权路径长度最短的二叉树
如何译码
Tire树
定义
字典树（Trie）可以保存一些 字符串 -> 值 的对应关系。
基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，
只不过 Trie 的 key 只能是字符串。
使用场景
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），
所以经常被搜索引擎系统用于文本词频统计
基本性质
（1） 根节点不包含字符，
除根节点意外每个节点只包含一个字符。
（2）从根节点到某一个节点，
路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。
（4）如果字符的种数为n，则每个结点的出度为n，
这也是空间换时间的体现，浪费了很多的空间。
（5）插入查找的复杂度为O(n)，n为字符串长度。
Trie的核心思想是空间换时间。利用字符串的
公共前缀来降低查询时间的开销以达到提高效率的目的。
基本算法
排序（https://blog.csdn.net/zxzxzx0119/article/details/79826380）
插入排序
直接插入
平均时间复杂度O(n2)
空间复杂度O(1)
稳定排序
shell排序
平均时间复杂度O(n1.3)
空间复杂度O(1)
不稳定排序
选择排序
直接选择排序
平均时间复杂度O(n2)
空间复杂度O(1)
不稳定排序
堆排序
平均时间复杂度O(nlgn)
空间复杂度O(1)
不稳定排序
交换排序
冒泡排序
平均时间复杂度O(n2)
空间复杂度O(1)
稳定排序
快速排序
平均时间复杂度O(nlgn)
空间复杂度O(1)
不稳定排序
归并排序
平均时间复杂度O(nlgn)
空间复杂度O(n)
稳定排序
堆排序
从(array.length-2)/2开始到0构造堆
调用Adjustheap,dad=start,end,son
从0至array.length-1,依次把最大的移至数组尾
两指针之三色排序
查找数组中间元素
KMP算法
怎么优化
使用linkhashmap实现LRU
栈实现队列
反转链表
新建节点
非新建节点
大数据算法
1亿个手机号码，判断重复
bitset或者布隆过滤器
100亿个数中寻找中位数
分区间（分桶统计，然后计数找到中间的）
leetcode与剑指offer
两个有序数组如何找到相同的元素
两个下标分别指向数组的头部，比如，i 指向数组 a 的头部，j 指向数组 b 的头部，
那么比较 a[i] 和 b[j] ，如果 a[i] 较大，移动 j，如果 b[j] 较大，那么 移动 i，
如果相等，那么 i 和 j 往后挪动，采用这种方式，只需要一次遍历即可
查找旋转数组
旋转数组找最小值
https://blog.csdn.net/zhangxiao93/article/details/55101605
旋转数组找目标值(target)
https://www.cnblogs.com/grandyang/p/4325840.html
循环链表
是否有环
找出环
树的四种遍历
前序遍历
递归
栈
中序遍历
递归
栈
后序遍历
递归
栈、双向链表
层次遍历
递归（Digui(root,h）
非递归（队列)
硬币找零
最少硬币数
多少种组合
多少种排列组合
面试算法题
100层楼丢玻璃球，一旦超过某层就会破，你只有两个球
分段20层、20层的去检测
其他算法
正则表达式匹配ip地址
逆波兰式
LRU
基于时间的算法.最近最久未访问 Least Frequently Used
三种实现
1.用一个数组来存储数据
给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
2.利用一个链表来实现
每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。
3. 利用链表和hashmap。同时维护链表和 map,map用来索引查找
当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项
Java实现
LinkedHashMap
缺点
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。
LRU-K算法
LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。
实现
LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史
只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。
数据第一次被访问时，加入到历史访问列表，如果书籍在访问历史列表中没有达到K次访问，则按照一定的规则（FIFO,LRU）淘汰
LRU-2
2Q将LRU-2算法中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。
当数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里面，两个队列各自按照自己的方法淘汰数据。
避免了批量的查询对于缓存的破坏
Multi Queue
MQ算法根据访问频率将数据划分为多个队列，不同的队列具有不同的访问优先级，其核心思想是：优先缓存访问次数多的数据。详细的算法结构图如下，Q0，Q1....Qk代表不同的优先级队列，Q-history代表从缓存中淘汰数据，但记录了数据的索引和引用次数的队列
新插入的数据放入Q0，每个队列按照LRU进行管理，当数据的访问次数达到一定次数，需要提升优先级时，将数据从当前队列中删除，加入到高一级队列的头部；为了防止高优先级数据永远不会被淘汰，当数据在指定的时间里没有被访问时，需要降低优先级，将数据从当前队列删除，加入到低一级的队列头部；需要淘汰数据时，从最低一级队列开始按照LRU淘汰，每个队列淘汰数据时，将数据从缓存中删除，将数据索引加入Q-history头部。如果数据在Q-history中被重新访问，则重新计算其优先级，移到目标队列头部。Q-history按照LRU淘汰数据的索引。
FIFO
先进先出页面置换算法
维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾
该算法不会对使用频率进行统计,仅仅根据一开始进入缓存的时间作为依据, 谁进入的最老谁最先被丢弃.
该算法可能会将使用频率比较高的元素, 丢弃. 实际上 LRU 算法是 FIFO的优化,没新访问一次就将其放在缓存头部
NRU
最近未使用页面置换算法
该算法关注 访问元素的状态位 ,每次清理时,只清理掉 未访问到的元素
还需要一个定时机制能够 定期的清理 元素的标记位,将其标记为未访问
算法、数据结构
数据结构
数组
链表
单向链表
双向链表
循环链表
跳表
在普通链表上简历索引
哈希
一致性哈希
队列
栈
树
红黑树
五个特性
根节点是黑色
叶子节点（NIL）是黑色
从根节点到叶子节点黑色节点的个数相同
节点为黑色或者红色
红色节点的两个子节点为黑色
优点
并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
二叉搜索树
b树
定义
1.定义任意非叶子结点最多只有M个儿子；且M>2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键属于(K[i-1], K[i])的子树；
8.所有叶子结点位于同一层；
特性
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；
b+树
定义
其定义基本与B-树同，除了：
1.非叶子结点的子树指针与关键字个数相同；
2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
3.为所有叶子结点增加一个链指针；
4.所有关键字都在叶子结点出现；
特性
1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；
b树和b+树区别
B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡
因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的
B*树
定义
是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；
特性
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3
b*和b+的区别
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分
数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的
关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点
与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增
加新结点的指针； 所以，B*树分配新结点的概率比B+树要低，空间使用率
更高；
AVL树
定义
相比于”二叉查找树”，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。
失去平衡的可以概括为4种姿态
左左
左子树的左子树导致的失衡
左右
左子树的右子树导致的失衡
右左
右子树的左子树导致的失衡
右右
右子树的右子树导致的失衡
总结：发生问题的那个节点要成为根节点才能解决问题。不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。
哈夫曼树
是一种带权路径长度最短的二叉树
如何译码
Tire树
定义
字典树（Trie）可以保存一些 字符串 -> 值 的对应关系。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不过 Trie 的 key 只能是字符串。
使用场景
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计
基本性质
（1） 根节点不包含字符，除根节点意外每个节点只包含一个字符。
（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
（3）每个节点的所有子节点包含的字符串不相同。
（4）如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
（5）插入查找的复杂度为O(n)，n为字符串长度。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
基本算法
排序（https://blog.csdn.net/zxzxzx0119/article/details/79826380）
插入排序
直接插入
平均时间复杂度O(n2)
空间复杂度O(1)
稳定排序
shell排序
平均时间复杂度O(n1.3)
空间复杂度O(1)
不稳定排序
选择排序
直接选择排序
平均时间复杂度O(n2)
空间复杂度O(1)
不稳定排序
堆排序
平均时间复杂度O(nlgn)
空间复杂度O(1)
不稳定排序
交换排序
冒泡排序
平均时间复杂度O(n2)
空间复杂度O(1)
稳定排序
快速排序
平均时间复杂度O(nlgn)
空间复杂度O(1)
不稳定排序
归并排序
平均时间复杂度O(nlgn)
空间复杂度O(n)
稳定排序
堆排序
从(array.length-2)/2开始到0构造堆
调用Adjustheap,dad=start,end,son
从0至array.length-1,依次把最大的移至数组尾
两指针之三色排序
查找数组中间元素
KMP算法
怎么优化
使用linkhashmap实现LRU
栈实现队列
反转链表
新建节点
非新建节点
大数据算法
1亿个手机号码，判断重复
bitset或者布隆过滤器
100亿个数中寻找中位数
分区间（分桶统计，然后计数找到中间的）
leetcode与剑指offer
两个有序数组如何找到相同的元素
两个下标分别指向数组的头部，比如，i 指向数组 a 的头部，j 指向数组 b 的头部，那么比较 a[i] 和 b[j] ，如果 a[i] 较大，移动 j，如果 b[j] 较大，那么 移动 i，如果相等，那么 i 和 j 往后挪动，采用这种方式，只需要一次遍历即可
查找旋转数组
旋转数组找最小值
https://blog.csdn.net/zhangxiao93/article/details/55101605
旋转数组找目标值(target)
https://www.cnblogs.com/grandyang/p/4325840.html
循环链表
是否有环
找出环
树的四种遍历
前序遍历
递归
栈
中序遍历
递归
栈
后序遍历
递归
栈、双向链表
层次遍历
递归（Digui(root,h）
非递归（队列)
硬币找零
最少硬币数
多少种组合
多少种排列组合
面试算法题
100层楼丢玻璃球，一旦超过某层就会破，你只有两个球
分段20层、20层的去检测
其他算法
正则表达式匹配ip地址
逆波兰式
蓄水池抽样算法
给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据
特点
数据流长度N很大且不可知，所以不能一次性存入内存。
时间复杂度为O(N)。
随机选取m个数，每个数被选中的概率为m/N。
思路
如果接收的数据量小于m，则依次放入蓄水池。
当接收到第i个数据时，i >= m，在[0, i]范围内取以随机数d，若d的落在[0, m-1]范围内，则用接收到的第i个数据替换蓄水池中的第d个数据。
重复步骤2。
推导
第i个接收到的数据最后能够留在蓄水池中的概率=第i个数据进入过蓄水池的概率*之后第i个数据不被替换的概率（第i+1到第N次处理数据都不会被替换）。
思路:
分别证明 当i m 时, 进入蓄水池的概率和 不被后边替换的概率
重要证明在下面
当i<=m时，程序从接收到第m+1个数据时开始执行替换操作，第m+1次处理会替换池中数据的为m/(m+1)，会替换掉第i个数据的概率为1/m，则第m+1次处理替换掉第i个数据的概率为(m/(m+1))*(1/m)=1/(m+1)，不被替换的概率为1-1/(m+1)=m/(m+1)。依次，第m+2次处理不替换掉第i个数据概率为(m+1)/(m+2)...第N次处理不替换掉第i个数据的概率为(N-1)/N。所以，之后第i个数据不被替换的概率=m/(m+1)*(m+1)/(m+2)*...*(N-1)/N=m/N。
分布式蓄水池
思路:
1. 将N 分到k 个机器上,可以按照hash来分片
2. 单机分别蓄水池得到 m 个 值
3. 在[1,N]中随机取一个值, 若在N1(第一个机器上,如果用hash 直接就能根据hash 计算出来) 上,则从第一个蓄水池中,随机1/m取一个值
假设有K台机器，将大数据集分成K个数据流，每台机器使用单机版蓄水池抽样处理一个数据流，抽样m个数据，并最后记录处理的数据量为N1, N2, ..., Nk, ..., NK(假设m<Nk)。N1+N2+...+NK=N。
取[1, N]一个随机数d，若d<N1，则在第一台机器的蓄水池中等概率不放回地（1/m）选取一个数据；若N1<=d<(N1+N2)，则在第二台机器的蓄水池中等概率不放回地选取一个数据；一次类推，重复m次，则最终从N大数据集中选出m个数据。
推导
第k台机器中的蓄水池数据被选取的概率为m/Nk。
从第k台机器的蓄水池中选取一个数据放进最终蓄水池的概率为Nk/N。
第k台机器蓄水池的一个数据被选中的概率为1/m。（不放回选取时等概率的）
重复m次选取，则每个数据被选中的概率为m*(m/Nk*Nk/N*1/m)=m/N
限流算法漏斗和令牌桶区别
漏斗算法
设置漏斗总容量即服务的最高并发级别
设置漏斗的消耗速率,该速率是固定的
漏斗默认是空的,请求进入到桶中.
漏斗算法其实是悲观的，因为它严格限制了系统的吞吐量，从某种角度上来说，它的效果和并发量限流很类似。漏斗算法也可以用于大多数场景，但由于它对服务吞吐量有着严格固定的限制
保证服务的最高并发次数,但是在瞬间流量增大情况下,表现不好
令牌桶算法
令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。
令牌桶可以为空时,请求会被丢弃. 同时令牌按照1/r 速度向桶中存放令牌
分支主题
一致性Hash 算法
作用
负载均衡
处理分片,无分布式锁架构
常见Hash 算法不能解决增减节点 缓存大量漂移失效情况
如何处理漂移情况
使用Hash环
将请求路由到环中,漂移时将请求漂移给上一个顺时针上一个节点
如何避免漂移后处理不均衡的情况
使用虚拟节点.
使用物理节点到虚拟节点的映射.将一个物理节点映射多个虚拟节点.
虚拟节点的key 可以使用前缀+数字标记.这样根据虚拟节点字节可以定位到物理节点
物理节点到虚拟节点的映射并不是严格的划片,而是完全随机的.
当发生漂移时,该物理节点漂移到的节点完全随机,避免一个
物理节点完全漂移到另一个物理节点.造成负载失衡
实际实现
包括hash 环 add,remove和hash 节点的定位
使用两个 Map
一个treemap存储hash虚拟节点到物理节点的映射.同时key 是可以排序的,
给定hash 值可以定位到具体哪个虚拟节点应该处理,进而根据虚拟节点前缀
确定物理节点(key:hash value: 物理节点#index)
存储 物理节点到虚拟节点的映射.其中 key 是物理节点,value 是对应的虚拟节点hash值.(查询 treemap 可以找到)
当添加物理节点时,生成若干(可以定义)虚拟节点.存储在两个map 钟
当删除物理节点时,查询物理节点对应的虚拟节点,开始执行漂移逻辑,将请求漂移到该节点的上一个节点
需要将虚拟节点的 treemap value修改为上一个key对应的 value.
使用 murmur 将相似度非常高的key散列的足够均匀.随机性越好.此时 漂移就可以做的足够随机,实际物理节点负载不比较均匀
具体的漂移逻辑由客户端自己实现
添加时也需要漂移,以前由上一个节点处理的请求要被路由到本节点. 删除时,,本节点处理的请求要被转发出去
murmur
非加密哈希算法
0 条评论
下一页
