数据结构疑难解析
数组与链表的区别
数组在内存中连续存储，支持随机访问，时间复杂度为O(1)；插入/删除元素需移动后续元素，时间复杂度为O(n)。链表通过指针非连续存储，访问需遍历，时间复杂度为O(n)；插入/删除仅需修改指针，时间复杂度为O(1)。
哈希表冲突解决
- 开放定址法：线性探测、二次探测探测空闲位置。
- 链地址法：冲突元素以链表形式存储在同一桶中。
- 再哈希法：使用第二个哈希函数计算新位置。
树结构的平衡性
AVL树通过旋转保持严格平衡（任意节点左右子树高度差≤1），适合读密集型场景。红黑树通过颜色标记放宽平衡条件（确保最长路径不超过最短路径两倍），适合写密集型场景。
图遍历算法对比
- BFS：队列实现，适用于无权图最短路径。
- DFS：栈或递归实现，适用于拓扑排序、连通分量检测。
堆的应用场景
优先队列、Dijkstra算法中提取最小边、海量数据TopK问题（时间复杂度O(nlogk)）。
代码示例：快速排序
def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr)//2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quicksort(left) + middle + quicksort(right)动态规划要点
- 状态定义明确（如dp[i][j]表示子问题解）。
- 状态转移方程需覆盖所有可能情况。
- 初始化边界条件（如dp[0][0] = 1）。
时空复杂度优化技巧
- 空间换时间：预计算、备忘录模式。
- 时间换空间：原地操作、滚动数组。
常见误区
- 忽视数据规模对算法选择的影响（如1e3可用O(n²)，1e5需O(nlogn)）。
- 混淆稳定排序（归并排序）与非稳定排序（快速排序）。
