算法与数据结构面试题
时间复杂度与空间复杂度
Q1: 什么是时间复杂度？
衡量算法执行时间随输入规模增长的增长率的函数，常用大 O 表示法。
常见复杂度：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
Q2: 什么是空间复杂度？
算法在运行过程中临时占用存储空间大小的度量。
常见数据结构
Q3: 数组和链表的区别
| 维度 | 数组 | 链表 |
|---|---|---|
| 内存 | 连续内存 | 分散存储 |
| 访问 | O(1) 随机访问 | O(n) 顺序访问 |
| 插入/删除 | O(n) | O(1)（已知位置） |
| 大小 | 固定 | 动态 |
Q4: 栈和队列的区别
- 栈：后进先出（LIFO），如函数调用栈
- 队列：先进先出（FIFO），如消息队列
Q5: 哈希表的工作原理
通过哈希函数将 key 映射到数组下标，解决冲突常用链地址法或开放寻址法。Java 的 HashMap 使用链地址法 + 红黑树（链表长度 >8 时转树）。
常见算法
Q6: 排序算法对比
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) | ✓ |
| 选择 | O(n²) | O(n²) | O(1) | ✗ |
| 插入 | O(n²) | O(n²) | O(1) | ✓ |
| 快排 | O(n log n) | O(n²) | O(log n) | ✗ |
| 归并 | O(n log n) | O(n log n) | O(n) | ✓ |
| 堆排 | O(n log n) | O(n log n) | O(1) | ✗ |
Q7: 二分查找
js
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1
while (left <= right) {
const mid = (left + right) >> 1
if (arr[mid] === target) return mid
if (arr[mid] < target) left = mid + 1
else right = mid - 1
}
return -1
}Q8: 二叉树遍历
- 前序：根 → 左 → 右
- 中序：左 → 根 → 右
- 后序：左 → 右 → 根
- 层序：逐层从左到右
Q9: 动态规划
核心思想：将问题分解为子问题，缓存子问题的解避免重复计算。
经典题：斐波那契数列、背包问题、最长公共子序列、最长递增子序列
Q10: 常见算法思想
- 贪心：每一步选当前最优，如找零问题
- 回溯：尝试所有可能，不满足时回溯，如 N 皇后
- 分治：分而治之，如归并排序、快排
- 双指针：快慢指针、左右对撞
- 滑动窗口：维护可变窗口解决子串/子数组问题