数据结构 ​

线性结构 ​

说说数组和链表的区别、适用场景 ​

数组和链表是两种常见的数据结构，它们在存储和处理数据方面有着各自的优势和劣势。

1. 存储结构：数组是一种连续的存储结构，它将元素存储在连续的内存空间中，每个元素都可以通过索引直接访问。而链表则是一种非连续的存储结构，它的元素存储在独立的节点中，每个节点都包含一个元素和一个指向下一个节点的指针。
2. 访问速度：由于数组的连续存储特性，我们可以通过索引在常数时间内访问任何元素，因此数组在随机访问时非常高效。而链表则需要从头节点开始，逐个遍历节点才能访问到目标元素，因此链表在随机访问时效率较低。
3. 插入和删除：链表在插入和删除元素时非常高效，只需要改变相应节点的指针即可，时间复杂度为 O(1)。而数组在插入和删除元素时需要移动大量元素以保持连续的存储，时间复杂度为 O(n)。
4. 内存利用：链表可以有效地利用内存，因为它只需要为需要的元素分配内存。而数组则需要预先分配一定大小的内存空间，如果实际使用量小于预分配的大小，会造成内存浪费。

适用场景：

• 数组：当你需要频繁进行随机访问，且插入和删除操作较少时，数组是一个好的选择。例如，在实现一个数字排序算法时，数组可以提供快速的随机访问。
• 链表：当你需要频繁进行插入和删除操作，且随机访问较少时，链表是一个好的选择。例如，在实现一个队列或栈这样的数据结构时，链表可以提供高效的插入和删除。

什么是跳表 (Skip List) ​

跳表 (Skip List) 是一种可以用于快速查找的数据结构。它是一种扩展自有序链表的数据结构，通过在链表的基础上增加多级索引，使得查找效率大大提高，理论上可以达到和二分查找相同的时间复杂度 O(log n)。

跳表的基本思想是这样的：在有序链表的基础上，为了实现快速查找，我们可以创建一级“快速通道”，在这个通道中的节点包含了原始链表中的部分节点，这些节点是原始链表中的每两个节点就取一个。然后在这一级快速通道的基础上，我们可以再创建一级更快的通道，每两个节点取一个，以此类推，我们可以创建多级这样的快速通道。

这样，如果我们要查找一个节点，我们可以从最高级的快速通道开始查找，如果当前节点的值比目标值大，我们就下降到下一级快速通道，如果当前节点的值比目标值小，我们就在当前快速通道向后查找，直到找到目标值为止。

跳表的插入、删除操作也相对简单，只需要维护好各级快速通道的节点即可。

跳表在实际应用中的一个典型例子是 Redis 的有序集合数据类型。

说说栈和队列的区别、适用场景 ​

栈 (Stack) 和队列 (Queue) 是两种常见的数据结构，它们在计算机科学和编程中有着广泛的应用。尽管它们都是线性的数据结构，但是它们的操作方式和使用场景有很大的不同。

1. 栈 (Stack)：栈是一种后进先出 (LIFO) 的数据结构，也就是说最后一个进入栈的元素会被首先取出。栈通常有两种主要操作：push(添加元素到栈顶) 和 pop(从栈顶移除元素)。栈的一个常见应用是在计算机科学中的函数调用，其中每个函数调用都会在栈上创建一个新的栈帧，当函数返回时，对应的栈帧就会被弹出。
2. 队列 (Queue)：队列是一种先进先出 (FIFO) 的数据结构，也就是说最先进入队列的元素会被首先取出。队列通常有两种主要操作：enqueue(添加元素到队列尾部) 和 dequeue(从队列头部移除元素)。队列的一个常见应用是在计算机科学中的任务调度，其中每个任务都会被添加到队列的尾部，然后按照它们到达的顺序依次执行。

什么时候会产生栈溢出，为什么一直递归就会栈溢出 ​

栈溢出通常发生在程序请求的栈空间超过了为其分配的最大空间时。这通常发生在递归函数中，因为每次函数调用自身时，都会在栈上添加一个新的层级，每个层级都需要自己的内存空间。

递归函数如果没有正确的终止条件，或者终止条件设置得过于严格，导致递归层级过多，就可能会导致栈溢出。这是因为每次函数调用都会在栈上分配内存来存储变量和函数调用的上下文信息。如果递归调用的层级过多，就会消耗掉所有的栈空间，导致栈溢出。

例如，考虑一个简单的递归函数，它的任务是计算一个数字的阶乘：

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

这个函数在计算factorial(10000)时，会导致栈溢出，因为这需要在栈上创建 10000 个层级，每个层级都需要存储n的值和返回地址。这可能会超过大多数系统为栈分配的默认最大空间。

为了避免栈溢出，我们需要确保递归函数有一个明确的终止条件，并且这个终止条件能在递归层级不太深的情况下达到。另外，我们也可以通过增加系统为栈分配的最大空间来解决这个问题，但这并不总是可行的，因为物理内存是有限的。

哈希表 ​

哈希表解决冲突有哪些方式？ ​

哈希表 (Hash Table) 是一种数据结构，它通过将键值 (Key) 通过一个函数转换为索引，然后将数据存储在这个索引对应的位置，以实现快速查找数据。然而，由于不同的键值可能会被哈希函数转换为同一个索引，这就产生了所谓的“冲突”(Collision)。解决哈希表冲突的主要方法有以下几种：

1. 开放寻址法 (Open Addressing)：当冲突发生时，寻找下一个空的哈希地址，直到找到为止。常见的开放寻址法有线性探测 (Linear Probing)、二次探测 (Quadratic Probing) 和双重哈希 (Double Hashing)。
2. 链地址法 (Chaining)：每个哈希表数组元素不再是单个数据，而是一个链表。当哈希地址冲突时，就将冲突的元素加到该地址的链表中。
3. 再哈希法 (Rehashing)：当冲突发生时，使用另一个哈希函数计算新的哈希地址，直到冲突不再发生。
4. 建立公共溢出区：这种方法是将哈希表分为基本表和溢出表两部分，所有的冲突元素都放入溢出表中。

以上就是解决哈希表冲突的常见方法，不同的方法有各自的优缺点，需要根据实际情况选择合适的解决方案。

哈希表使用链地址法解决冲突，当冲突特别严重时，复杂度会退化成 O(N), 有什么解决办法 ​

当哈希表使用链地址法解决冲突时，如果冲突特别严重，链表可能会变得特别长，这样查找效率就会降低，复杂度会退化成 O(N)。这种情况下，可以采取以下几种策略来改善：

1. 调整哈希函数：哈希函数的设计直接影响到哈希冲突的发生频率。如果哈希函数设计得好，可以使得数据在哈希表中的分布更均匀，从而减少冲突。
2. 扩大哈希表的大小：如果哈希表的大小固定，那么当插入的元素数量超过哈希表的大小时，冲突的概率就会大大增加。因此，可以通过扩大哈希表的大小来减少冲突。
3. 使用二级哈希：当冲突发生时，可以使用另一个哈希函数进行二次哈希，以此来减少冲突。
4. 链表优化：对于链表过长的问题，可以考虑将链表替换为其他更高效的数据结构，如红黑树、跳表等。
5. 动态调整哈希表大小：当哈希表的负载因子 (已存元素数量/哈希表大小) 超过一定阈值时，可以考虑将哈希表的大小进行扩容，以减少冲突。

以上就是解决哈希表冲突严重时的一些常见策略，具体采取哪种策略需要根据实际情况来决定。

假如在处理某个请求时，触发了哈希表的扩容，因为需要复制整个哈希表的所有元素，需要一次 O(N) 时间复杂度的操作，会导致这个请求超时，有没有办法解决或规避？ ​

在处理哈希表扩容时，确实需要一次 O(N) 的时间复杂度来复制所有元素，这可能导致处理请求的时间过长。为了解决这个问题，可以采用一种叫做 "渐进式哈希"(Incremental Hashing) 或 "动态哈希"(Dynamic Hashing) 的技术。

在渐进式哈希中，当哈希表需要扩容时，不是一次性将所有元素复制到新的更大的哈希表中，而是将这个操作分散到接下来的各个插入操作中。具体来说，每次插入新元素时，除了将新元素插入到哈希表中，还会将旧哈希表中的一部分元素复制到新哈希表中。这样，扩容操作的开销就被均摊到了多次插入操作中，避免了一次性的大量开销。

这种方法的优点是可以避免单次请求处理时间过长的问题，但是它也有一个缺点，那就是在扩容期间，哈希表的性能可能会稍微下降，因为每次插入操作都需要额外做一些复制元素的工作。但是，只要扩容的速度和插入新元素的速度匹配得当，这种性能下降通常是可以接受的。

Redis 的 zset (有序集合) 内部是什么数据结构？ ​

Redis 的 Zset(有序集合) 内部主要使用了两种数据结构：跳表 (Skip List) 和哈希表 (Hash Table)。

1. 哈希表：用于存储元素及其分数，实现了快速查找元素和更新分数的功能。
2. 跳表：用于存储有序的元素，实现了快速的插入、删除、查找元素，以及按照分数范围查找元素的功能。跳表是一种可以进行二分查找的有序链表，通过增加多级索引来提高查询效率。

这两种数据结构的结合使得 Zset 既可以快速读取元素，又可以维护元素的排序状态，因此在功能上比 List 和 Set 更加强大。

树 ​

什么是完全二叉树？一棵深度为 10 的完全二叉树，至少有多少个节点？ ​

完全二叉树是一种特殊的二叉树，它的定义是：对于一棵深度为 k 的二叉树，除了第 k 层外，其它各层的节点数都达到最大个数，第 k 层所有的节点都连续集中在最左边。

对于一棵深度为 10 的完全二叉树，至少有多少个节点，我们需要考虑到完全二叉树的特性。在完全二叉树中，如果树的深度为 d，那么前 d-1 层的节点数都是满的，即每一层的节点数都是 2 的 n 次方减 1，其中 n 为该层的层数。而第 d 层的节点数至少有 1 个。

所以，一棵深度为 10 的完全二叉树，前 9 层至少有 1 + 2^1 + 2^2 + ... + 2^8 + 2^9 = 2^10 - 1 = 1023 个节点，第 10 层至少有 1 个节点。

因此，一棵深度为 10 的完全二叉树至少有 1023 + 1 = 1024 个节点。

二叉树有哪几种实现方式，分别有什么优势和劣势？ ​

二叉树是一种非常常见的数据结构，主要有以下两种实现方式：

1. 链式存储结构：每个节点由一个数据元素和两个指向左右子树的指针组成。这是最常见的实现方式。
   • 优势：链式存储结构的优点是结构清晰，易于理解和操作，可以方便地进行插入、删除和查找操作。
   • 劣势：但是，链式存储结构的缺点是空间利用率不高，因为每个节点都需要额外的空间来存储两个指针。此外，链式存储结构也不利于序列化和反序列化。
2. 顺序存储结构：将二叉树的节点按照层序遍历的顺序存储在一个数组中，对于数组中的任意一个元素，其左子节点的位置是 2n+1，右子节点的位置是 2n+2，其中 n 是该元素在数组中的位置。
   • 优势：顺序存储结构的优点是空间利用率高，因为每个节点只需要一个数组元素的空间。此外，顺序存储结构也方便于序列化和反序列化。
   • 劣势：但是，顺序存储结构的缺点是插入和删除操作复杂，可能需要移动大量的元素。此外，如果二叉树是一个斜树 (即所有的节点都只有左子树或者只有右子树)，那么顺序存储结构的空间利用率会大大降低。

说说二叉树的前序遍历、中序遍历、后序遍历 ​

二叉树的遍历主要有四种方法：前序遍历、中序遍历、后序遍历和层次遍历。

1. 前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。
2. 中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。
3. 后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。

什么是哈夫曼树？给定 n 个叶子节点的权重 w1,w2,...,wn, 如何构造一棵哈夫曼树 ​

哈夫曼树，也称为最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶子节点的权值乘以其到根节点的路径长度 (即树的深度) 之和。树的带权路径长度越小，说明效率越高。

构造哈夫曼树的步骤如下：

1. 将 n 个权值作为 n 棵二叉树的根节点，构成森林。
2. 在森林中选出两个根节点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根节点权值为其左、右子树根节点权值之和。
3. 从森林中删除选取的两棵树，并将新树加入森林。
4. 重复 2、3 步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。

这种构造方法保证了树中权值较大的节点离根节点较近，权值较小的节点离根节点较远，从而使得整体的带权路径长度最小。

哈夫曼树在数据压缩和编码中有广泛的应用，例如哈夫曼编码就是利用哈夫曼树进行的，它是一种十分高效的编码方式。

哈夫曼编码的原理是什么？如何实现？有哪些应用场景？ ​

哈夫曼编码是一种用于无损数据压缩的贪心算法。其基本原理是：给定一组字符及其出现的频率，哈夫曼编码算法可以生成一种最优的字符编码方式，使得整个字符串的编码长度最短。

实现哈夫曼编码的步骤如下：

1. 创建一个空的优先队列 (通常使用最小堆实现)。将每个字符及其出现的频率作为一个节点，放入优先队列中。
2. 当队列中还有多于一个节点时，从队列中取出两个频率最小的节点，然后合并它们，生成一个新的节点。新节点的频率是这两个节点的频率之和。将新节点放回队列中。
3. 重复步骤 2，直到队列中只剩下一个节点。这个节点就是哈夫曼树的根节点。
4. 从哈夫曼树的根节点开始，向左的边标记为 0，向右的边标记为 1。这样，每个字符的哈夫曼编码就是从根节点到该字符的路径上的边的标记序列。

哈夫曼编码的应用场景主要包括：

1. 数据压缩：哈夫曼编码是一种无损压缩算法，广泛应用于文件压缩，如 ZIP 文件。
2. 通信编码：在无线通信中，为了提高传输效率，常常使用哈夫曼编码对数据进行编码。
3. 存储优化：在存储有限的情况下，可以使用哈夫曼编码对数据进行压缩，以节省存储空间。
4. 图像和音频编码：在 JPEG 和 MP3 等格式中，也使用了哈夫曼编码。

总的来说，哈夫曼编码是一种非常实用的编码方式，它能够有效地减少数据的存储空间和传输时间，而且是无损的，不会丢失任何信息。

说说堆的数据结构，以及如何构建最大堆？ ​

堆是一种树，且每个父节点的值都只是大于或等于 (最大堆) 或小于或等于 (最小堆) 其子节点的值。

对所有非叶子节点，自底向上，顺序地堆化。 如果叶子节点的值大于父节点，则进行交换，直到根节点。

搜索树 ​

说说平衡二叉树与红黑树 ​

平衡二叉树和红黑树都是自平衡的二叉搜索树，它们在插入和删除操作后能自动调整，保持树的高度尽可能小，从而达到高效的搜索性能。但是，它们的平衡策略和实现方式有所不同。

1. 平衡二叉树 (AVL 树)：平衡二叉树是一种高度平衡的二叉搜索树，即任何节点的两个子树的高度差最多为 1。这种严格的平衡策略使得 AVL 树的查找效率非常高，但是在插入和删除操作时可能需要频繁的旋转来维持这种高度平衡，因此，如果数据更新非常频繁，AVL 树可能不是最佳选择。
2. 红黑树：红黑树是一种稍微放松了平衡条件的二叉搜索树，它通过引入节点颜色 (红或黑) 和一系列颜色规则来保持树的大致平衡，而不是严格的高度平衡。这使得红黑树在插入和删除操作时的旋转次数相对较少，性能更优。红黑树的平衡规则包括：每个节点要么是红色，要么是黑色；根节点是黑色；所有叶子节点 (NIL 节点) 是黑色；如果一个节点是红色，那么它的子节点必须是黑色；从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

总的来说，如果搜索操作远多于插入和删除操作，那么 AVL 树可能是更好的选择；如果插入和删除操作也很频繁，那么红黑树可能更有优势。

说说 B 树与 B+树 ​

B 树和 B+树是两种常用的数据结构，主要用于大量数据的存储和检索。它们都是自平衡的多路搜索树，可以处理大量数据的高效查找和插入操作。然而，它们之间存在一些关键的区别。

B 树 (Balanced Tree) 是一种自平衡的搜索树，可以在 O(log n) 的时间复杂度内完成查找、插入和删除操作。在 B 树中，所有的值都存储在树的节点中，每个节点可以有多个子节点。B 树的一个重要特性是它的所有叶子节点都在同一层，这保证了查找任何元素的时间复杂度都是相等的。

B+树是 B 树的一种变体，主要的区别在于它的数据存储方式。在 B+树中，数据只存储在叶子节点，非叶子节点只存储关键字信息。这意味着，查找一个元素需要从根节点开始，一直查找到叶子节点。这种结构的优点是每个叶子节点都可以包含更多的元素，因此 B+树的高度通常比 B 树低。

此外，B+树的所有叶子节点都通过指针相连，这使得范围查询更加高效。因为一旦找到范围的开始，就可以通过指针顺序访问所有在范围内的元素，而无需回溯。

图 ​

图有哪几种存储方式，及分别的适用场景 ​

图 (Graph) 是一种非线性数据结构，主要用于表示物件之间的关系。图的存储方式主要有两种：邻接矩阵和邻接表。

1. 邻接矩阵：邻接矩阵是一个二维数组，其中的行和列都代表图中的节点，如果节点 i 和节点 j 之间存在边，那么数组的第 i 行第 j 列的位置 (记为 a[i][j]) 就是 1(或者是边的权重)，否则就是 0。邻接矩阵的主要优点是查询两个节点之间是否存在边非常快，时间复杂度是 O(1)。但是，邻接矩阵的空间复杂度是 O(n^2)，其中 n 是图中节点的数量，因此，如果图是稀疏的 (即边的数量远小于 n^2)，邻接矩阵就会浪费很多空间。此外，如果要获取一个节点的所有邻居，需要遍历一整行或一整列，时间复杂度是 O(n)。
2. 邻接表：邻接表是一个数组，数组的每个元素都是一个链表，数组的第 i 个元素的链表包含了所有与节点 i 相连的节点。邻接表的主要优点是空间复杂度只与图中的边的数量有关，因此，对于稀疏图来说，邻接表比邻接矩阵更节省空间。此外，获取一个节点的所有邻居的时间复杂度只与该节点的度 (即邻居的数量) 有关。但是，如果要查询两个节点之间是否存在边，需要在链表中进行查找，时间复杂度是 O(m)，其中 m 是边的数量。

总的来说，如果图是稠密的，或者需要频繁查询两个节点之间是否存在边，那么邻接矩阵可能是更好的选择。如果图是稀疏的，或者需要频繁获取一个节点的所有邻居，那么邻接表可能是更好的选择。

什么是广度优先遍历，什么是深度优先遍历？ ​

广度优先遍历 (Breadth-First Search，BFS) 和深度优先遍历 (Depth-First Search，DFS) 是两种常见的图或树的遍历算法。

广度优先遍历是一种层次遍历的方法，它的基本思想是从图的某一节点开始，访问尽可能靠近它的节点。具体的操作是先访问起始节点，然后访问它的所有邻接节点，再访问这些邻接节点的所有未被访问过的邻接节点，以此类推，直到所有的节点都被访问过。在实现广度优先遍历时，通常会使用一个队列来存储待访问的节点。

深度优先遍历则是尽可能深地搜索图的分支。当节点 v 的所有边都已被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。在实现深度优先遍历时，通常会使用一个栈来存储待访问的节点。

这两种遍历方法各有优势，适用于不同的场景。广度优先遍历可以用于找到最短路径，而深度优先遍历则可以用于路径搜索，寻找所有可能的路径。

说说最短路径的 Dijkstra 算法 ​

Dijkstra 算法是一种用于寻找图中两点之间最短路径的算法。这种算法由荷兰计算机科学家艾兹格·迪科斯彻在 1956 年发明，并在 1959 年发表。Dijkstra 算法使用了广度优先搜索策略，以找到从源节点到所有其他节点的最短路径。

Dijkstra 算法的基本步骤如下：

1. 创建一个集合，用于存储已经找到最短路径的节点。
2. 将源节点的距离设为 0，将所有其他节点的距离设为无穷大。
3. 对于源节点的每一个邻居，更新其距离 (如果从源节点到该邻居的距离小于当前记录的距离)。
4. 从未处理的节点中选择距离最小的节点，将其添加到已处理节点的集合中。
5. 对于新处理的节点的每一个邻居，更新其距离 (如果从源节点经过新处理的节点到该邻居的距离小于当前记录的距离)。
6. 重复步骤 4 和 5，直到所有的节点都被处理。

Dijkstra 算法的时间复杂度为 O(V^2)，其中 V 是图中节点的数量。如果图中的边使用优先队列 (如二叉堆) 来存储，那么时间复杂度可以降低到 O((V+E)logV)，其中 E 是图中边的数量。

需要注意的是，Dijkstra 算法假设所有的边的权重都是非负的。如果图中存在负权重的边，那么 Dijkstra 算法可能无法找到正确的最短路径。在这种情况下，可以使用其他算法，如贝尔曼-福德算法。

说说最小生成树的 Kruskal 算法 ​

Kruskal 算法是一种用于找到连通图的最小生成树的算法。最小生成树是一个图的子图，它包含了图的所有顶点，并且是边权值总和最小的树。

Kruskal 算法的步骤如下：

1. 将图的所有边按照权值从小到大排序。
2. 初始化一个空的最小生成树。然后，按照边的权值从小到大的顺序，考虑每一条边：如果这条边连接的两个顶点在最小生成树中不在同一连通分量中，就将这条边加入最小生成树。
3. 重复第二步，直到最小生成树中包含了原图的所有顶点。

Kruskal 算法的关键在于，它始终选择当前最小的边，并且确保这条边不会在生成树中形成一个环。这是通过检查边的两个顶点是否已经在同一连通分量中来实现的。如果是，这条边就会被忽略。否则，就将这条边加入最小生成树，并将这两个顶点合并到同一连通分量中。

Kruskal 算法的时间复杂度是 O(ElogE)，其中 E 是图的边的数量。这是因为算法的主要开销在于对边的排序。在实际应用中，Kruskal 算法通常用于稀疏图，即边的数量远小于顶点的数量的平方的图，因为在这种情况下，Kruskal 算法比其他最小生成树算法更有效。

说说最小生成树的 Prim 算法 ​

Prim 算法是一种用于解决最小生成树问题的贪心算法。最小生成树是一个图中的一个子图，它包含了图中的所有顶点，并且所有的边都是图中权值最小的边。Prim 算法的基本思想是从一个顶点开始，每次都添加一条权值最小的边，直到所有的顶点都被添加到生成树中。

Prim 算法的步骤如下：

1. 初始化：选择一个起始点，将其添加到最小生成树的集合中。
2. 选择一条连接已在最小生成树集合中的顶点和不在集合中的顶点的最小边，将这条边以及其对应的顶点添加到集合中。
3. 重复步骤 2，直到所有的顶点都被添加到最小生成树的集合中。

Prim 算法的时间复杂度为 O(ElogE)，其中 E 是图中边的数量。这是因为算法需要对所有的边进行排序，并且每次添加一条边时，都需要更新与新添加的顶点相连的边的权值。

Prim 算法的优点是它能够保证找到的是全局最优的最小生成树，而不是局部最优解。但是，如果图中包含负权值的边，Prim 算法可能无法找到最小生成树。此外，Prim 算法只适用于连通图，如果图不连通，算法将无法找到最小生成树。