:whale:touchstone_2025/03/06

1.数组和链表的区别

答：

特性	数组	链表
存储方式	连续存储	非连续存储
访问效率	O(1)（随机访问）	O(n)（顺序访问）
插入/删除	O(n)（需移动元素）	O(1)（只需修改指针）
内存利用率	100% 高（无需指针）	<100% 低（需要存储指针域）
内存分配	栈区，固定大小	堆区，动态分配
适用场景	数据量固定，频繁访问	数据动态变化，频繁插入/删除

2.简述快速排序的过程

答：

快速排序（Quick Sort）是一种基于分治法的高效排序算法，其核心思想是通过递归地将数据划分为两部分，逐步实现排序。以下是快速排序的主要步骤：

1.选择基准元素（Pivot）

从待排序数组中选择一个基准元素，通常选择第一个元素、最后一个元素或中间元素。

2.分区（Partition）

将数组分为两部分：
1. 左边部分包含小于或等于基准元素的值。
2. 右边部分包含大于基准元素的值。
具体操作：
1. 使用两个指针（i 和 j），分别从数组的左右两端开始扫描。
2. j 从右向左找到第一个小于基准的元素，i 从左向右找到第一个大于基准的元素。
3. 交换这两个元素的位置。
4. 重复上述过程，直到i 和j相遇。

3. 递归排序

对基准元素左边和右边的子数组分别递归调用快速排序，直到子数组长度为1或0（即已经有序）。

4. 合并结果

由于每次分区后基准元素的位置已经确定，最终所有子数组有序时，整个数组即有序。

特点

时间复杂度：平均情况下为 O(n log n)，最坏情况下为 O(n²)（如数组已有序）。
空间复杂度：O(log n)（递归栈空间）。
稳定性：不稳定（相同元素可能改变相对位置）。

总结

快速排序通过分治策略高效地将数组排序，其核心在于分区操作和递归调用。尽管最坏情况下效率较低，但通过优化基准元素的选择（如随机化或三数取中），可以显著提升性能。

3.快速排序的改进

答：快速排序（Quick Sort）是一种高效的排序算法，但在某些情况下（如数据已有序或包含大量重复元素）可能退化为 O(n²) 的时间复杂度。以下是几种常见的改进方式：

1. 优化基准元素（Pivot）选择

随机化选择：
- 随机选择基准元素，避免固定选择（如第一个或最后一个元素）导致的最坏情况。
- 示例：
  1
  pivot = arr[rand() % (right - left + 1)]
三数取中法：
- 选择左端、右端和中间位置的三个元素的中值作为基准，减少不平衡分区的概率。
- 示例：取arr[left]、arr[right]、arr[mid]的中值。

2.处理重复元素

三向分区（Dutch National Flag）：
- 将数组分为三部分：小于基准、等于基准和大于基准，减少重复元素的重复交换。
- 示例：使用lt（小于基准的边界）和gt（大于基准的边界）指针。
跳过重复元素：
- 在分区过程中，跳过与基准相等的元素，避免不必要的交换。

3. 优化递归深度

尾递归优化：
- 对较大的子数组递归调用，较小的子数组使用迭代，减少栈空间开销。
- 示例：先处理左子数组，然后迭代处理右子数组。
混合排序：
- 对小规模数组（如长度 < 10）切换到插入排序，减少递归调用次数。

4. 分区策略改进

双指针分区：
- 使用左右指针从两端向中间扫描，减少交换次数。
- 示例：
  1
  while (i < j)
  循环中，i从左向右找大于基准的元素，j从右向左找小于基准的元素。
Lomuto 分区与 Hoare 分区：
- Lomuto 分区简单但效率较低，Hoare 分区更高效但实现复杂。可根据需求选择。

5. 其他优化

并行化：
- 在多核处理器上，将子数组的排序任务分配到不同线程，提升性能。
缓存优化：
- 优化数据访问模式，减少缓存未命中，提升局部性。

总结

通过优化基准选择、处理重复元素、改进分区策略和递归深度，可以显著提升快速排序的性能和稳定性。实际应用中，常结合多种优化方式以适应不同数据特征。

4.常见算法效率对比

答：

排序算法对比表

排序算法	平均时间复杂度	最好时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n)	O(n²)	O(1)	稳定
希尔排序	O(n^1.3^-n^1.5^)	O(n)	O(n²)	O(1)	不稳定
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	稳定
基数排序	O(N * M)	O(N * M)	O(N * M)	O(M)	稳定

总结：

稳定性：冒泡、插入、归并、计数、基数排序是稳定的；
- 选择、希尔、快速、堆排序是不稳定的
时间效率：快速排序、归并排序、堆排序在平均情况下效率较高。
空间开销：归并排序和计数排序需要较多额外空间，其他算法空间复杂度较低。

5.邻接矩阵与邻接表对比

答：

特性	邻接矩阵	邻接表
存储结构	二维数组	链表或动态数组
空间复杂度	𝑂(n^2^)	𝑂(𝑛+𝑒)
查找边效率	𝑂(1)	𝑂(𝑑𝑒𝑔𝑟𝑒𝑒)
插入/删除顶点	𝑂(𝑛^2^)	𝑂(1)
适用场景	稠密图、矩阵运算	稀疏图、遍历算法

1. 存储结构

邻接矩阵：
1. 使用二维数组存储，数组的行和列分别表示图的顶点，矩阵元素表示顶点之间是否存在边（或边的权值）。
2. 无向图的邻接矩阵是对称矩阵，有向图则不一定。
3. 空间复杂度为 𝑂(𝑛^2^)，其中 𝑛 为顶点数。
邻接表：
1. 使用链表或动态数组存储，每个顶点对应一个链表，链表中存储其邻接顶点。
2. 空间复杂度为 𝑂(𝑛+𝑒)，其中 e 为边数，适合稀疏图。

2. 性能对比

操作	邻接矩阵	邻接表
查找边是否存在	𝑂(1)	𝑂(𝑑𝑒𝑔𝑟𝑒𝑒)（需遍历链表）
查找顶点的邻接点	𝑂(𝑛)（扫描整行/列）	𝑂(𝑑𝑒𝑔𝑟𝑒𝑒)
插入/删除边	𝑂(1)	𝑂(1)（链表操作）
插入/删除顶点	𝑂(𝑛^2^)（需扩展矩阵）	𝑂(1)（动态调整链表）
空间利用率	浪费空间（稀疏图）	节省空间（稀疏图）

3. 优缺点

邻接矩阵：
1. 优点：
  - 查找边是否存在或获取边的权值效率高。
  - 适合稠密图，便于实现矩阵运算（如最短路径算法）。
2. 缺点：
  - 空间复杂度高，不适合稀疏图。
  - 插入/删除顶点代价高。
邻接表：
1. 优点：
  - 空间利用率高，适合稀疏图。
  - 插入/删除顶点和边效率高。
2. 缺点：
  - 查找边是否存在效率较低。
  - 实现复杂，需要额外指针开销。

4. 适用场景

邻接矩阵：
1. 稠密图（边数接近 𝑛2n2）。
2. 需要频繁查询边是否存在或获取权值的场景。
3. 基于矩阵运算的算法（如 Floyd-Warshall 算法）。
邻接表：
1. 稀疏图（边数远小于 𝑛2n2）。
2. 需要频繁插入/删除顶点或边的场景。
3. 基于遍历的算法（如深度优先搜索、广度优先搜索）。

通过以上对比，可以根据图的性质和操作需求选择合适的存储方式：

若图稠密且需要高效查询边信息，选择邻接矩阵。
若图稀疏且需要频繁插入/删除操作，选择邻接表。

6.递归和迭代的对比

答：

递归和迭代是编程中两种常见的重复执行代码的方式，它们在实现方式、性能、适用场景等方面有显著区别。以下是详细对比：

1. 定义与实现方式

递归：
1. 递归是函数直接或间接调用自身的过程，通过将复杂问题分解为更小的子问题来解决。
2. 递归包含两个阶段：递推（将问题分解）和回归（逐步求解并返回结果）。
3. 递归需要明确的终止条件（递归出口），否则会导致无限递归。
迭代：
1. 迭代是通过循环结构（如 for、while）重复执行代码块，每次迭代利用变量的旧值更新新值，直到满足终止条件。
2. 迭代是一种显式的重复过程，通常通过循环变量控制执行次数。

2. 优点与缺点

特性	递归	迭代
代码简洁性	代码简洁，逻辑清晰	代码较长，逻辑较直接
性能	效率较低，频繁函数调用导致栈开销	效率高，无函数调用开销
空间占用	可能因递归深度过大导致栈溢出	不占用额外栈空间
适用场景	分治算法、树/图遍历、动态规划等问题	固定次数重复、简单迭代

3. 适用场景

递归：
1. 分治算法（如快速排序、归并排序）。
2. 动态规划问题（如斐波那契数列、背包问题）。
3. 树和图的遍历（如深度优先搜索）。
4. 具有自相似性质的问题（如汉诺塔问题）。
迭代：
1. 固定次数的重复操作（如遍历数组、打印数字）。
2. 条件满足时重复执行（如用户输入验证）。
3. 简单迭代任务（如模拟递归过程）。

4. 性能与优化

递归：
1. 可能因重复计算导致性能低下（如斐波那契数列的朴素递归）。
2. 可通过尾递归优化或备忘录（Memoization）提升性能。
迭代：
1. 高效，适合处理大规模数据或性能敏感场景。
2. 无栈溢出风险，适合深度较大的迭代任务。

5. 总结

选择依据	递归	迭代
代码简洁性	较高	较低
性能	较低	较高
适用场景	分治算法、树/图遍历、动态规划	简单迭代、固定次数重复

建议：

若问题规模较大或性能要求高，优先使用迭代。
若问题具有递归结构（如树遍历、分治算法），且代码简洁性更重要，可选择递归。

7.解决哈希冲突的方法

答：

哈希冲突是指在使用哈希表时，不同的键通过哈希函数计算后映射到同一个位置的情况。以下是常见的解决哈希冲突的方法：

1. 开放定址法（Open Addressing）

当发生哈希冲突时，通过一定的探测方法寻找下一个空闲的哈希地址，直到找到合适的位置。常见的探测方法包括：

线性探测法（Linear Probing）：
- 公式：ℎ(𝑥)=(Hash(𝑥)+𝑖) mod Hashtable.length
- 每次冲突后，向后移动一个位置，直到找到空位。
- 缺点：容易产生“聚集现象”，即多个冲突元素集中在某一区域。
平方探测法（Quadratic Probing）：
- 公式：ℎ(𝑥)=(Hash(𝑥)+𝑖2) mod Hashtable.length
- 每次冲突后，移动的步长按平方数递增，减少聚集现象。
双重哈希法（Double Hashing）：
- 使用两个哈希函数，第二个哈希函数用于计算探测步长。
- 公式：ℎ(𝑥)=(Hash1(𝑥)+𝑖⋅Hash2(𝑥)) mod Hashtable.length
- 优点：减少聚集现象，分布更均匀。

2. 链地址法（Separate Chaining）

将哈希表的每个槽位（bucket）作为一个链表的头节点，所有哈希冲突的元素都存储在同一个链表中。

实现方式：
- 插入时，将冲突元素添加到链表中。
- 查找时，遍历链表找到目标元素。
优点：
- 简单易实现，适合冲突较少的情况。
- 链表长度不受限制，适合动态数据。
缺点：
- 链表过长时，查找效率退化为 O(n)。
- 需要额外的存储空间维护链表。

3. 再哈希法（Rehashing）

当发生哈希冲突时，使用另一个哈希函数重新计算哈希值，直到找到空位。

实现方式：
- 使用多个哈希函数，依次计算直到解决冲突。
优点：
- 减少冲突概率，分布更均匀。
缺点：
- 增加计算开销，哈希函数设计复杂。。

4. 建立公共溢出区

将哈希表分为基本表和溢出表，所有冲突元素都存储在溢出表中。

实现方式：
- 基本表存储无冲突元素，溢出表存储冲突元素。
优点：
- 简单易实现，适合冲突较少的情况。
缺点：
- 查找冲突元素需要遍历溢出表，效率较低。

5. 其他优化方法

增加哈希表大小：
- 通过扩大哈希表容量，减少冲突概率。
动态调整负载因子：
- 当负载因子超过阈值时，重新哈希并扩展表容量。
使用多重哈希函数：
- 结合多个哈希函数，进一步减少冲突。

总结

方法	优点	缺点
开放定址法	无需额外空间，适合小规模数据	容易产生聚集现象，效率可能降低
链地址法	简单易实现，适合动态数据	链表过长时效率降低，需要额外空间
再哈希法	减少冲突概率，分布均匀	计算开销大，哈希函数设计复杂
公共溢出区	简单易实现	查找冲突元素效率低

根据具体场景选择合适的方法，例如：

若冲突较少且内存有限，选择开放定址法或链地址法。
若冲突较多且需要高效查找，选择再哈希法或多重哈希法。

8.哈希表VS二叉排序树（二叉搜索树BST）

答：

特性	哈希表	二叉搜索树（BST）
查找效率	平均 O(1)，最坏 O(n)（冲突时）	平均 O(log n)，最坏 O(n)（退化为链）
插入/删除效率	平均 O(1)，最坏 O(n)	平均 O(log n)，最坏 O(n)
有序性	无序	中序遍历可得有序序列
内存开销	需要预分配空间，可能存在浪费	动态分配，每个节点需额外存储指针
适用场景	快速查找、无需有序数据（如缓存）	需有序遍历或范围查询（如数据库索引）

应用场景：

哈希表：缓存系统（如Redis）、快速键值查询。
BST：有序字典、范围查询（如统计区间数据）。

9.优先队列VS普通队列

答：

特性	堆（优先队列）	普通队列
元素顺序	按优先级排序（最大/最小元素优先）	先进先出（FIFO）
插入效率	O(log n)	O(1)（链表实现）
删除效率	O(log n)（弹出堆顶）	O(1)（链表实现）
实现方式	数组（完全二叉树结构）	链表或循环数组
应用场景	任务调度、Top K问题、Dijkstra算法	消息队列、广度优先搜索（BFS）

10.动态数组VS链表

答：

特性	动态数组（如C++vector）	链表
内存分配	连续内存块，扩容时需重新分配	非连续内存，动态分配节点
随机访问	O(1)	O(n)
尾部插入	均摊 O(1)（可能触发扩容）	O(1)（需遍历到尾节点）
中间插入/删除	O(n)（需移动元素）	O(1)（找到位置后修改指针）
内存开销	可能预留冗余空间	每个节点需额外存储指针
应用场景	需要频繁随机访问、数据规模动态增长	频繁在任意位置插入/删除（如文本编辑器中的撤销操作）。