数据结构与算法 - 面试题库

一、基础题 ⭐

Q1. 数组和链表的主要区别是什么？各自适合什么场景？

答案：数组连续内存，支持 O(1) 随机访问，但插入/删除需 O(n) 移动元素。链表非连续内存，插入/删除 O(1)，但随机访问 O(n)。数组适合频繁按索引访问、数据量稳定的场景；链表适合频繁插入/删除、数据量变化大的场景。数组缓存友好，链表内存分散。 关联知识点：内存布局、缓存局部性

Q2. 如何实现一个支持 getMin 的栈，且所有操作都是 O(1)？

答案：使用两个栈，一个存数据，一个存最小值。push 时数据栈正常压入，最小值栈只在元素 ≤ 当前最小值时压入。pop 时数据栈弹出，若等于最小值栈顶则最小值栈也弹出。getMin 返回最小值栈顶。空间复杂度 O(n)，所有操作 O(1)。 关联知识点：栈、辅助数据结构

Q3. 用两个栈如何实现队列？

答案：用 inStack 处理入队，outStack 处理出队。入队时直接 push inStack。出队时若 outStack 为空，将 inStack 全部弹出压入 outStack，然后 pop outStack；若不为空直接 pop。均摊时间复杂度 O(1)，因为每个元素最多被移动两次。 关联知识点：栈、队列、均摊分析

Q4. 哈希表解决冲突的两种主要方法是什么？

答案：链地址法：每个桶是一个链表，冲突的元素链在后面。Java HashMap 8 个元素后转红黑树。开放地址法：冲突时按探测序列找空位，包括线性探测、二次探测、双重哈希。链地址法实现简单，开放地址法缓存友好但删除复杂。 关联知识点：哈希函数、负载因子

Q5. 如何判断一个链表是否有环？

答案：快慢指针法（Floyd 判圈）。慢指针每次走一步，快指针每次走两步。若有环，快指针会追上慢指针；若无环，快指针先到末尾。时间复杂度 O(n)，空间 O(1)。找到环后，将一个指针放回起点，两个指针每次各走一步，相遇点即为环入口。 关联知识点：双指针、Floyd 判圈

Q6. 冒泡排序和插入排序的区别是什么？

答案：冒泡排序每次比较相邻元素，大的往后冒，每轮确定一个最大值。插入排序将数组分为已排序和未排序，将未排序元素插入已排序部分合适位置。两者都是 O(n²)，但插入排序在近乎有序时接近 O(n)，且是稳定的。插入排序实际性能通常优于冒泡。 关联知识点：排序稳定性、适应性

Q7. 二叉树的前序、中序、后序遍历分别是什么顺序？

答案：前序：根→左→右，用于复制树。中序：左→根→右，BST 中序得到有序序列。后序：左→右→根，用于删除树。递归实现简单，迭代实现用栈。层序遍历用队列，用于找最短路径。 关联知识点：递归、栈、队列

Q8. 什么是完全二叉树？它有什么特点？

答案：完全二叉树除最后一层外每层都满，最后一层节点靠左排列。特点是可用数组紧凑存储（节点 i 的子节点为 2i+1 和 2i+2），无需指针。堆是完全二叉树。高度为 log n，适合优先队列和堆排序。 关联知识点：堆、数组存储

Q9. 如何判断两棵二叉树是否相同？

答案：递归比较：两棵树都空返回 true；一棵空一棵不空返回 false；值不同返回 false；否则递归比较左子树和右子树。时间复杂度 O(n)，n 为节点数。也可用迭代 BFS/DFS 逐层比较。 关联知识点：递归、树的遍历

Q10. 二分查找的前提条件是什么？时间复杂度是多少？

答案：前提是数组有序（升序或降序）。每次比较中间元素，缩小一半搜索范围。时间复杂度 O(log n)，空间 O(1)。变体包括找第一个/最后一个出现位置、旋转数组查找、找峰值等。注意 mid = left + (right - left) / 2 防止溢出。 关联知识点：有序数组、分治

二、进阶题 ⭐⭐

Q11. 快速排序的原理是什么？最坏情况是什么？如何优化？

答案：选基准（pivot），将数组分为小于和大于基准的两部分，递归排序。平均 O(n log n)，最坏 O(n²)（已有序且选首元素为基准）。优化：随机选基准、三数取中、小数组用插入排序、尾递归优化。原地分区空间 O(log n)。 关联知识点：分治、分区策略

Q12. 归并排序和快速排序的区别是什么？

答案：归并先递归再合并，保证 O(n log n)，稳定，需 O(n) 额外空间。快速先分区再递归，平均 O(n log n) 但最坏 O(n²)，不稳定，原地分区空间 O(log n)。归并适合链表和外排序，快排适合数组且常数因子更小。 关联知识点：分治、稳定性、空间复杂度

Q13. 如何实现 LRU 缓存？

答案：哈希表 + 双向链表。哈希表 O(1) 查找，双向链表维护访问顺序。get 时找到节点移到链表头部；put 时若满则删除尾部节点，新节点插入头部。时间复杂度 O(1)。Python 可用 OrderedDict 实现。 关联知识点：哈希表、双向链表、缓存策略

Q14. 二叉树的最大深度如何求解？

答案：递归：maxDepth(root) = 1 + max(maxDepth(left), maxDepth(right))，空节点返回 0。迭代：BFS 层序遍历，层数即深度。时间复杂度 O(n)，空间递归 O(h)，迭代 O(w)，h 为高度，w 为最大宽度。 关联知识点：递归、BFS

Q15. 什么是并查集？它的应用场景有哪些？

答案：并查集维护不相交集合，支持 find（查代表）和 union（合并）操作。优化：路径压缩 + 按秩合并，均摊接近 O(1)。应用：Kruskal 最小生成树、连通分量、动态连通性、朋友圈问题。 关联知识点：路径压缩、按秩合并

Q16. 如何找到数组中的第 K 大元素？

答案：方法一：排序后取第 K 个，O(n log n)。方法二：最小堆维护 K 个最大元素，O(n log K)。方法三：快速选择（快排分区思想），平均 O(n)，最坏 O(n²)。方法四：BFPRT 算法，最坏 O(n)。面试推荐堆或快速选择。 关联知识点：堆、快速选择、Top K

Q17. 岛屿数量问题如何解决？

答案：遍历网格，遇到 ‘1’ 计数加一并用 BFS/DFS 将相连的 ‘1’ 标记为 ‘0’。BFS 用队列，DFS 用递归。时间复杂度 O(m×n)，每个格子访问常数次。也可用并查集，将相邻 ‘1’ 合并，最后集合数即岛屿数。 关联知识点：BFS、DFS、并查集、Flood Fill

Q18. 如何验证二叉搜索树的合法性？

答案：中序遍历应为严格递增序列。递归验证：每个节点有上下界，左子树所有节点 < 根 < 右子树所有节点。初始根节点范围为 (-∞, +∞)。递归时左子树上界为根值，右子树下界为根值。时间 O(n)，空间 O(h)。 关联知识点：BST 性质、递归、中序遍历

三、高级题 ⭐⭐⭐

Q19. 动态规划的核心思想是什么？如何判断一个问题是否适合用 DP？

答案：DP 核心是将问题分解为重叠子问题，通过记忆化或递推避免重复计算。适合 DP 的问题需满足：重叠子问题（子问题被多次求解）和最优子结构（最优解包含子问题最优解）。解题四步：定义状态 → 状态转移方程 → 初始化 → 计算顺序。常见类型：背包、路径、子序列、字符串编辑。 关联知识点：重叠子问题、最优子结构、记忆化

Q20. 请解释 0-1 背包问题的 DP 解法。

答案：定义 dp[i][j] 为前 i 个物品容量 j 的最大价值。状态转移：不选第 i 个物品 dp[i][j] = dp[i-1][j]；选第 i 个物品 dp[i][j] = dp[i-1][j-w[i]] + v[i]。取两者最大值。空间优化为一维数组，倒序遍历避免重复使用。时间复杂度 O(n×W)，空间 O(W)。 关联知识点：状态定义、空间优化

Q21. 最长公共子序列（LCS）如何求解？

答案：定义 dp[i][j] 为 text1[:i] 和 text2[:j] 的 LCS 长度。若字符相同 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。最终 dp[m][n] 为答案。时间复杂度 O(m×n)，空间可优化为 O(min(m,n))。与最长递增子序列不同，LCS 针对两个序列。 关联知识点：双序列 DP、字符串

Q22. Dijkstra 算法的原理是什么？为什么不能处理负权边？

答案：Dijkstra 基于贪心，每次选距离起点最近的未访问节点，更新其邻居距离。用优先队列优化到 O((V+E)log V)。不能处理负权边因为一旦节点被标记为”已确定最短距离”，后续负权边可能使其更短，但算法不会重新考虑。负权边需用 Bellman-Ford。 关联知识点：优先队列、贪心、Bellman-Ford

Q23. 红黑树的五条性质是什么？它如何保证平衡？

答案：1）节点是红色或黑色；2）根是黑色；3）叶子（NIL）是黑色；4）红色节点的子节点必须是黑色（不能有连续红节点）；5）从任一节点到叶子的所有路径黑节点数相同。性质 4 和 5 保证最长路径不超过最短路径的两倍，近似平衡。插入/删除通过变色和旋转维护性质。 关联知识点：自平衡树、旋转操作

四、实战场景题 🛠️

Q24. 海量数据中找 Top K（如 10 亿个数找最大的 100 个），如何设计？

答案：用最小堆维护 K 个最大元素。遍历数据，堆未满直接插入；堆满后若当前元素 > 堆顶，替换堆顶并调整。时间复杂度 O(n log K)，空间 O(K)。若数据分布在多台机器，每台找局部 Top K 后合并。也可用快速选择平均 O(n)。内存不足时分块处理。 关联知识点：堆、分治、外部排序

Q25. 如何设计一个支持高频插入和查询的计数器（如 UV 统计）？

答案：小规模用哈希表 O(1)。大规模用布隆过滤器预判是否已存在，再用 HyperLogLog 估算基数，空间极小。精确计数用 Redis HyperLogLog 或 Bitmap。时间敏感用分段锁哈希表。权衡精度、空间和时间。 关联知识点：布隆过滤器、HyperLogLog、Bitmap

Q26. 编辑距离问题：给定两个单词，求将一个转换成另一个的最少操作数（插入、删除、替换）。

答案：经典 DP。dp[i][j] 表示 word1[:i] 转 word2[:j] 的最少操作。若字符相同 dp[i][j] = dp[i-1][j-1]；否则 dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])，分别对应删除、插入、替换。时间复杂度 O(m×n)，空间可优化为 O(n)。 关联知识点：字符串 DP、双序列

Q27. 如何实现一个支持撤销/重做的文本编辑器？

答案：用两个栈：撤销栈和重做栈。每次编辑将状态压入撤销栈，清空重做栈。撤销时弹出撤销栈压入重做栈。重做时弹出重做栈压入撤销栈。为节省空间，可用命令模式只存操作而非全量状态，或用差分存储。空间复杂度取决于存储策略。 关联知识点：栈、命令模式、Memento 模式

Q28. 会议室调度问题：给定一组会议时间，求最少需要多少会议室。

答案：贪心 + 最小堆。按开始时间排序会议。遍历会议，若堆顶（最早结束时间）≤ 当前开始时间，说明可复用该会议室，弹出堆顶。将当前会议结束时间压入堆。最终堆大小即最少会议室数。时间复杂度 O(n log n)，空间 O(n)。 关联知识点：贪心、堆、区间问题

Q29. 如何判断一个数独是否合法？

答案：遍历 81 个格子，对每个非空格子检查：同行、同列、同 3×3 宫是否有重复。用 9 个哈希表分别记录每行、每列、每宫的数字。一次遍历完成，时间复杂度 O(1)（固定 81 格），空间 O(1)（固定 27 个集合）。也可用位运算优化空间。 关联知识点：哈希表、位运算、回溯

Q30. 实现一个 Trie（前缀树），支持 insert、search、startsWith 操作。

答案：每个节点包含子节点映射和结束标记。insert 逐字符创建节点，末尾标记结束。search 逐字符查找，末尾需是结束节点。startsWith 逐字符查找，不要求结束标记。时间复杂度 O(m)，m 为字符串长度。应用：自动补全、拼写检查、IP 路由。 关联知识点：前缀树、字符串匹配