收藏本页，算法面试查漏补缺。系统学习 → 古法编程 · 算法与数据结构
精选高频算法与数据结构面试题，覆盖复杂度、经典结构、常见算法思想与高频题型。
1. 什么是时间复杂度？常见量级排序？
时间复杂度描述算法运行时间随输入规模增长的趋势。常见量级由快到慢：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
2. 数组和链表的区别？
- 数组：连续内存，随机访问 O(1)，插入删除 O(n)。
- 链表：非连续，访问 O(n)，头部插入删除 O(1)。
3. 栈和队列的区别与应用？ 栈 LIFO（后进先出），用于函数调用、括号匹配、DFS；队列 FIFO（先进先出），用于 BFS、任务调度。
4. 哈希表如何解决冲突？ 链地址法（拉链）、开放寻址法（线性/二次探测）。负载因子过高时扩容 rehash。平均查找 O(1)。
5. 二叉搜索树、平衡树、红黑树的关系？ BST 左小右大，但可能退化为链表；平衡树（AVL）严格平衡；红黑树是近似平衡的 BST，插入删除更快，被 map/TreeMap 广泛采用。
6. 堆是什么？有什么用？ 完全二叉树，大顶堆/小顶堆。用于优先队列、Top K 问题、堆排序。插入和删除堆顶均为 O(log n)。
7. 双指针适用哪些场景？ 有序数组两数之和、去重、快慢指针判环、滑动窗口（子串问题）。
8. 二分查找的关键点？
数组必须有序。注意边界：left <= right、mid = left + (right-left)/2（防溢出）、循环收缩条件。变体：找左/右边界、旋转数组。
9. 什么是动态规划？三要素？ 把大问题拆成重叠子问题，用状态转移方程递推。三要素：状态定义、转移方程、初始条件。经典题：背包、最长公共子序列、爬楼梯。
10. 回溯法的模板？
def backtrack(路径, 选择列表):
if 满足结束条件:
结果.add(路径); return
for 选择 in 选择列表:
做选择
backtrack(路径, 新选择列表)
撤销选择
应用：全排列、组合、N 皇后、子集。
11. 贪心和动态规划的区别？ 贪心每步取局部最优、不回退，快但不一定全局最优；DP 保存所有子问题解，保证全局最优。
12. 如何判断链表有环？ 快慢指针（Floyd）：快指针走两步、慢指针走一步，相遇即有环。找环入口：相遇后一指针回到头，同速前进再次相遇处即入口。
13. 求数组中第 K 大的数？
- 小顶堆维护 K 个元素，O(n log k)。
- 快速选择（快排 partition 思想），平均 O(n)。
14. 常见排序算法的复杂度与稳定性？
| 算法 | 平均 | 最坏 | 稳定 |
|---|---|---|---|
| 快排 | O(n log n) | O(n²) | 否 |
| 归并 | O(n log n) | O(n log n) | 是 |
| 堆排 | O(n log n) | O(n log n) | 否 |
| 冒泡/插入 | O(n²) | O(n²) | 是 |
15. LRU 缓存怎么实现？ 哈希表 + 双向链表：哈希表 O(1) 定位，双向链表维护访问顺序，访问/插入时移到头部，满了删尾部。
📖 想真正吃透算法、刷题不再靠背？ 完整教程含图解与详细推导：
👉 古法编程 · 算法与数据结构完全教程（10 章，含详细名词解释，完全免费）
更多免费中文编程教程 → www.gufacode.com