面试中一些较为复杂的常见的算法

桃扇骨 2023-07-01 08:52 23阅读 0赞

**目录**

1.跳跃表

2.并查集

3.哈夫曼树与编码

4.AVL树

5.B树和B+ 树

6.前缀树

7.红黑树

8.线段树

9.图的表示：邻接矩阵和邻接表

10.图的遍历：深度搜索和广度搜索

11. 最短路径算法：Floyd 与 Dijkstra

12. 最小生成树算法： Prim， Kruskal

13.关键路径、拓扑排序

14.模式匹配：KMP， Boyer-Moore

--------------------

### 1.跳跃表 ###

跳跃表让已排序的数据分布在多层次的链表结构中，默认是将Key值升序排列的，以 0-1 的随机值决定一个数据是否能够攀升到高层次的链表中。它通过容许一定的数据冗余，达到 “以空间换时间” 的目的。

在一定量数据中查找数据的方法：

> 1.  有序数组。这种方式的存储结构，优点是支持数据的随机访问，并且可以采用二分查找算法降低查找操作的复杂度。缺点同样很明显，插入和删除数据时，为了保持元素的有序性，需要进行大量的移动数据的操作。
> 2.  二叉查找树。如果需要一个既支持高效的二分查找算法，又能快速的进行插入和删除操作的数据结构，那首先就是二叉查找树莫属了。缺点是在某些极端情况下，二叉查找树有可能变成一个线性链表。
> 3.  平衡二叉树。二叉树表示不服，于是基于二叉查找树的优点，对其缺点进行改进，引入了平衡的概念。根据平衡算法的不同，具体实现有AVL树 ／
> 4.  B树（B-Tree） ／ B+树（B+Tree） ／ 红黑树 等等。但是平衡二叉树的实现多数比较复杂，较难理解。
> 5.  跳跃表。同样支持对数据进行高效的查找，插入和删除数据操作也比较简单，最重要的就是实现比较平衡二叉树真是轻量几个数量级。缺点就是存在一定数据冗余。  
>     
> 6.  二叉树、B树、红黑树等请查看：[啥是二叉搜索树、B树、B+树、AVL树、红黑树，怎么那么多的树，一文全总结][B_B_AVL]

![è¿éåå¾çæè¿°][SouthEast]

一个跳跃表应该有若干个层（Level）链表组成；

> 跳跃表中最底层的链表包含所有数据； 每一层链表中的数据都是有序的；
> 
> 如果一个元素X出现在第i层，那么编号比 i 小的层都包含元素X；
> 
> 第 i 层的元素通过一个指针指向下一层拥有相同值的元素；
> 
> 在每一层中，-∞ 和 +∞两个元素都出现(分别表示INT\_MIN 和 INT\_MAX)；
> 
> 头指针（head）指向最高一层的第一个元素；
> 
> 所以其结点模型是：含有1个数据data，4个指针：left, right, up, down  
>   
> 来源[参考][Link 1]

### 2.并查集 ###

并查集（Union/Find）从名字可以看出，主要涉及两种基本操作:合并和查找。这说明，初始时并查集中的元素是不相交的，经过一系列的基本操作(Union)，最终合并成一个大的集合。

### 3.哈夫曼树与编码 ###

**1）哈夫曼树**

哈夫曼树是一类带权路径最短的树。构造这种树的算法最早由哈夫曼提出，这种树在信息检索中很有用。如用于通讯及数据传送中构造传输效率最高的二进制编码（哈夫曼编码），用于编程中构造平均执行时间最短的最佳判断过程。

![这里写图片描述][SouthEast 1]

**几个基本的概念：**

**1. 路径：**是指在一棵树中，从一个节点到另一个节点之间的分支构成的通路，如从节点8到节点1的路径如下图所示：

![这里写图片描述][SouthEast 2]

**2. 路径长度：**指的是路径上分支的数目，在上图中，路径长度为2。

**3. 节点的权：**指的是为树中的每一个节点赋予的一个非负的值，如上图中每一个节点中的值。节点的带权路径长度指的是从根节

点到该节点之间的路径长度与该节点权的乘积：如对于1节点的带权路径长度为：2。

**4. 树的带权路径长度：**指的是所有叶子节点的带权路径长度之和。

有了如上的概念，对于Huffman树，其定义为：

> 给定n权值作为n个叶子节点，构造一棵二叉树，若这棵二叉树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为Huffman树。

比较下面两棵树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70][]

上面的两棵树都是以\{10, 20, 50, 100\}为叶子节点的树。

> 左边的树WPL=2\*10 + 2\*20 + 2\*50 + 2\*100 = 360 右边的树WPL=350

左边的树WPL > 右边的树的WPL。你也可以计算除上面两种示例之外的情况，**但实际上右边的树就是\{10,20,50,100\}对应的哈夫曼树。**

**哈夫曼树构造形式：**

哈夫曼算法：假设有n个权值，则构造出的哈夫曼树有 n 个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

> 1.  将 w1、w2、…，wn 看成是有 n 棵树的森林(每棵树仅有一个结点)
> 2.  在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和
> 3.  从森林中删除选取的两棵树，并将新树加入森林
> 4.  重复步骤 2、3，直到森林中只剩下一棵树为止，该树即为所求的哈夫曼树

**例子：**可以看出权值越小的，越在树的越底端

以\{5,6,7,8,15\}为例，来构造一棵哈夫曼树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 2][]

**构建流程：**

> **第1步**：创建森林，森林包括5棵树，这5棵树的权值分别是5,6,7,8,15。
> 
> **第2步**：在森林中，选择根节点权值最小的两棵树(5和6)来进行合并，将它们作为一颗新树的左右孩子(谁左谁右无关紧要，这里，我们选择较小的作为左孩子)，并且新树的权值是左右孩子的权值之和。即，新树的权值是11。 然后，将"树5"和"树6"从森林中删除，并将新的树(树11)添加到森林中。
> 
> **第3步**：在森林中，选择根节点权值最小的两棵树(7和8)来进行合并。得到的新树的权值是15。 然后，将"树7"和"树8"从森林中删除，并将新的树(树15)添加到森林中。
> 
> **第4步**：在森林中，选择根节点权值最小的两棵树(11和15)来进行合并。得到的新树的权值是26。 然后，将"树11"和"树15"从森林中删除，并将新的树(树26)添加到森林中。
> 
> **第5步**：在森林中，选择根节点权值最小的两棵树(15和26)来进行合并。得到的新树的权值是41。 然后，将"树15"和"树26"从森林中删除，并将新的树(树41)添加到森林中。 此时，森林中只有一棵树(树41)。这棵树就是我们需要的哈夫曼树！

**2）哈夫曼编码：**

**哈夫曼（Huffman）编码算法**是基于二叉树构建编码压缩结构的，它是数据压缩中经典的一种算法。算法根据文本字符出现的频率，重新对字符进行编码。因为为了缩短编码的长度，我们自然希望频率越高的词，编码越短，这样最终才能最大化压缩存储文本数据的空间。

约定：

*  左孩子编码为0，右孩子编码为1

![这里写图片描述][SouthEast 3]

从上图中，E节点的编码为：00，同理，D节点的编码为1001

### 4.AVL树 ###

查看文章：[啥是二叉搜索树、B树、B+树、AVL树、红黑树，怎么那么多的树，一文全总结][B_B_AVL]

### 5.B树和B+ 树 ###

查看文章：[啥是二叉搜索树、B树、B+树、AVL树、红黑树，怎么那么多的树，一文全总结][B_B_AVL]

### 6.前缀树 ###

前缀树，又称为 Trie树， 字典树

![20150509003807271][]

上图是一棵Trie树，表示了关键字集合\{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”\} 。从上图可以归纳出Trie树的基本性质：

> 1.  根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
> 2.  从根节点到**某一个节点**，路径上经过的字符连接起来，为该节点对应的字符串。
> 3.  每个节点的所有子节点包含的字符互不相同。

通常在实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。

可以看出，Trie树的关键字一般都是字符串，而且Trie树把每个关键字保存在一条路径上，而不是一个结点中。另外，两个有公共前缀的关键字，在Trie树中前缀部分的路径相同，所以Trie树又叫做**前缀树（Prefix Tree）**。

**字典树的应用：**

**1. 词频统计：**

可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？还能这么玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。

**2. 前缀匹配：**

例如：找出一个字符串集合中所有以`ab`开头的字符串。我们只需要用所有字符串构造一个trie树，然后输出以`a->b->`开头的路径上的关键字即可。

trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

**3. 字符串排序：**

Trie树可以对大量字符串按字典序进行排序，思路也很简单：遍历一次所有关键字，将它们全部插入trie树，树的每个结点的所有儿子很显然地按照字母表排序，然后先序遍历输出Trie树中所有关键字即可。

### 7.红黑树 ###

查看文章：[啥是二叉搜索树、B树、B+树、AVL树、红黑树，怎么那么多的树，一文全总结][B_B_AVL]

### 8.线段树 ###

线段树又称区间树，英文叫Segment Tree。

**线段树主要用于解决区间内的统计查询问题。**

对于给定的区间

更新：更新区间中一个元素或一个区间的值。

查询：查询一个区间\[i,j\]的最大值，最小值，或者区间和等。

与数组的时间复杂度对比

![format_png][]

线段树不是完全二叉树，是平衡二叉树（所有叶子结点的最大深度与最小深度相差小于等于1）。

**从一个例子来理解线段树：**

下面我们从一个经典的例子来了解线段树，问题描述如下:从数组arr\[0...n-1\]中查找某个数组某个区间内的最小值，其中数组大小固定，但是数组中的元素的值可以随时更新。

对这个问题一个简单的解法是：遍历数组区间找到最小值，时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大，而查询操作很频繁的时候，耗时可能会不满足需求。

另一种解法：使用一个二维数组来保存提前计算好的区间\[i,j\]内的最小值，那么预处理时间为O(n^2)，查询耗时O(1), 但是需要额外的O(n^2)空间，当数据量很大时，这个空间消耗是庞大的，而且当改变了数组中的某一个值时，更新二维数组中的最小值也很麻烦。

我们可以用线段树来解决这个问题：预处理耗时O(n)，查询、更新操作O(logn)，需要额外的空间O(n)。根据这个问题我们构造如下的二叉树

*  叶子节点是原始组数arr中的元素
 *  非叶子节点代表它的所有子孙叶子节点所在区间的最小值

例如对于数组\[2, 5, 1, 4, 9, 3\]可以构造如下的二叉树（背景为白色表示叶子节点，非叶子节点的值是其对应数组区间内的最小值，例如根节点表示数组区间arr\[0...5\]内的最小值是1）：

![format_png 1][]

由于线段树的父节点区间是平均分割到左右子树，因此线段树是完全二叉树，**对于包含n个叶子节点的完全二叉树，它一定有n-1个非叶节点，总共2n-1个节点**，因此存储线段是需要的空间复杂度是O(n)。

### 9.图的表示：邻接矩阵和邻接表 ###

查看文章：

[图的邻接矩阵和邻接表的表示][Link 2]

### 10.图的遍历：深度搜索和广度搜索 ###

[图的深度优先遍历][Link 3]

[图的广度优先遍历][Link 4]

### 11. 最短路径算法：Floyd 与 Dijkstra ###

### 12. 最小生成树算法： Prim， Kruskal ###

### 13.关键路径、拓扑排序 ###

### 14.模式匹配：KMP， Boyer-Moore ###

### 项目推荐： ###

**[2000多G的计算机各行业电子资源分享（持续更新）][2000_G]**

**[2020年微信小程序全栈项目之喵喵交友【附课件和源码】][2020]**

**[Spring Boot开发小而美的个人博客【附课件和源码】][Spring Boot]**

**[Java微服务实战296集大型视频-谷粒商城【附代码和课件】][Java_296_-]**

**[Java开发微服务畅购商城实战【全357集大项目】-附代码和课件][Java_357_-]**

**[最全最详细数据结构与算法视频-【附课件和源码】][-]**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]

[B_B_AVL]: https://blog.csdn.net/qq_40587575/article/details/108615934
[SouthEast]: https://img-blog.csdn.net/20180115125211841?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvREVSUkFOVENN/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[Link 1]: https://blog.csdn.net/DERRANTCM/article/details/79063312
[SouthEast 1]: https://img-blog.csdn.net/20170204140550598?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZ29vZ2xlMTk4OTAxMDI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: https://img-blog.csdn.net/20170204142717988?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZ29vZ2xlMTk4OTAxMDI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200916163848694.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200916164023563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200916164041880.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1,size_16,color_FFFFFF,t_70
[SouthEast 3]: https://img-blog.csdn.net/20170204153342221?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvZ29vZ2xlMTk4OTAxMDI=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[20150509003807271]: https://img-blog.csdn.net/20150509003807271
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzEvMTZiYWQ5MmJiNjkxYTE3Yw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMwLmNuYmxvZ3MuY29tL2Jsb2cvNTE3MjY0LzIwMTMxMi8wMTIwNDA1OC00MjZkY2U4YjhhMDU0OTFiOTFlZGViYTllYzJlNDExMi5qcGc?x-oss-process=image/format,png
[Link 2]: https://blog.csdn.net/qq_40587575/article/details/104149816
[Link 3]: https://blog.csdn.net/qq_40587575/article/details/105725860
[Link 4]: https://blog.csdn.net/qq_40587575/article/details/105918919
[2000_G]: https://mp.weixin.qq.com/s/sP4JgGWkCzpgwKr9sAV2_Q
[2020]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487704&idx=1&sn=5f4b2127c4d49fd07ae072a0721424a2&chksm=e8036fc2df74e6d489c4aa9b06f917ef7cee6027f13e150fca53cf79d5d188d4ccc1af49e098&scene=21#wechat_redirect
[Spring Boot]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487798&idx=2&sn=ac0293b996521b872a9dba5fbb3e65e6&chksm=e8036e2cdf74e73aba104a9a994a5b2e31483e8dcbe0f1d9936f6d5173b887e1560f59d2819c&scene=21#wechat_redirect
[Java_296_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487674&idx=1&sn=7aff0bdf2bb727303f3d3618995aef21&chksm=e8036fa0df74e6b6d872c7e6ece179c524ed463a4a6b74c96875475c9a3d5ddb903427dd993b&scene=21#wechat_redirect
[Java_357_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247486376&idx=1&sn=d1fef270c463ea8ac663f6fbfedd70a0&chksm=e80374b2df74fda4d3bafba878a106a19e18c5fcda266008f4f37975847a21bc612ffcd5ff39&scene=21#wechat_redirect
[-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487750&idx=1&sn=747bccbb5f5ea6b58915198de40da777&chksm=e8036e1cdf74e70ae97a5e8e265b49d7236d904d291203309159d07ba1724033062c0e370843&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210105230611623.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1,size_16,color_FFFFFF,t_70#pic_center