FAQ?

如何分析一道算法题的时间复杂度与空间复杂度？

时间复杂度用大 O 表示法描述算法运行时间随输入规模 n 的增长量级，常关注最坏情况。分析方法：

1. 看循环嵌套层数：单层循环 O(n)，双层嵌套 O(n²)，但要看是否每次减半——for (i = 1; i < n; i *= 2) 是 O(log n) 而非 O(n)。
2. 看递归深度 × 每层工作量：递归树每个节点的工作量乘节点数。如归并：每层 O(n)，共 log n 层 → O(n log n)。
3. 主定理（Master Theorem）：T(n) = a * T(n/b) + f(n)，分治类标准工具。
4. 均摊分析：如动态数组 push 平均 O(1)，但扩容时 O(n) 摊到 n 次操作上仍为均摊 O(1)。

空间复杂度看额外内存：

• 原地操作：O(1)
• 递归：递归栈深度 O(h)
• DP：状态数组大小 O(n) 或 O(n²)，可滚动数组优化
• BFS 队列：最坏 O(宽)，回溯递归：最坏 O(深)

复杂度	含义	典型算法
O(1)	常数	哈希查找、位运算
O(log n)	对数	二分查找、平衡树操作
O(n)	线性	单次遍历、双指针
O(n log n)	线性对数	排序、归并、分治
O(n²)	平方	朴素 DP、双重循环
O(2^n)	指数	子集枚举、朴素回溯
O(n!)	阶乘	全排列、N 皇后

面试经验：n <= 10 大概率 O(n!)；n <= 20 是 O(2^n)；n <= 100 是 O(n³)；n <= 1000 是 O(n²)；n <= 10^5 是 O(n log n)；n >= 10^9 要 O(log n) 或 O(1)。

算法的稳定性是什么意思，为什么重要？

稳定性指排序后两个相等元素的相对顺序是否保持不变。若排序前 A 在 B 前，且 A == B，排序后 A 仍在 B 前，则称该排序稳定。

稳定的排序：冒泡、插入、归并、计数、基数、TimSort。 不稳定的排序：选择、快排、堆排、希尔。

重要场景：多关键字排序。比如先按次要字段排序（稳定），再按主字段排序，主字段相同时次要字段顺序自然保留。例如：员工按工资排序，工资相同时保持工龄顺序——只需先按工龄排（稳定），再按工资排（稳定）。

为什么快排/堆排不稳定？ 因为它们通过交换不相邻元素实现排序，可能跨越相等元素。如选择排序 [5a, 5b, 2] → 选最小 2 与 5a 交换 → [2, 5b, 5a]，5a/5b 顺序被破坏。

ES2019 后：JS 的 Array.prototype.sort 规范明确要求稳定，所有主流浏览器现已实现稳定排序（V8 用 TimSort）。所以业务代码中按多字段排序可放心链式 sort。

递归和迭代如何转换？什么时候必须用递归？

递归 → 迭代有两条路径：

1. 直接改循环：尾递归可以直接改写成 while。如阶乘 fact(n, acc=1) → while (n > 0) { acc *= n; n--; }。斐波那契用两个变量滚动。
2. 显式栈模拟：任意递归都能用栈模拟——把"函数调用栈"换成"显式栈"。DFS 的递归版改迭代版就是经典例子：把节点压栈，pop 处理，子节点压栈。

// 递归版前序遍历
function preorderRec(root: TreeNode | null): number[] {
  if (!root) return [];
  return [root.val, ...preorderRec(root.left), ...preorderRec(root.right)];
}

// 迭代版（显式栈）
function preorderIter(root: TreeNode | null): number[] {
  if (!root) return [];
  const res: number[] = [];
  const stack: TreeNode[] = [root];
  while (stack.length) {
    const node = stack.pop()!;
    res.push(node.val);
    if (node.right) stack.push(node.right); // 先压右，后压左
    if (node.left) stack.push(node.left);
  }
  return res;
}

什么时候必须用递归（或显式栈）？

• 问题天然是递归结构：树的遍历、分治、回溯、表达式求值、文件系统遍历。
• 需要保存"上下文"的：回溯的"做选择—递归—撤销"模式，转迭代需手动维护 path 状态。

为什么不直接用递归？

• 性能：递归有函数调用开销，常数比循环大。
• 栈溢出：JS 默认递归深度约 1 万左右（V8 实测约 10000~15000），大数据量 DFS 必须改迭代或用尾调用优化（但 V8 对非严格模式尾调用支持有限）。

工程上：能用循环就别用递归；递归更易读时用递归；深度大时改显式栈。

拿到一道陌生算法题，应该如何分析？

建议按"读题—举例—暴力—优化—编码—验证"六步走：

1. 读题：明确输入输出、约束、边界（空、单元素、重复、负数、极大值）。把题目的关键词圈出来："有序"、"无重复"、"子串/子序列"、"连续"等暗示算法。
2. 举例：手画一两个例子，验证对题意的理解，例子还能作为后续测试用例。
3. 暴力解：先想最朴素的解法，通常 O(n²) 或 O(2^n)，作为保底和复杂度上界。暴力解的正确性能帮助理解问题。
4. 优化：从暴力解出发找冗余。常见方向：
   • 重复计算 → 记忆化 / DP
   • 二重循环找配对 → 哈希表 / 双指针 / 排序
   • 搜索 → BFS（最短）/ DFS（连通）/ 回溯（枚举）
   • 单调性 → 二分查找
   • 局部最优 → 贪心
5. 编码：先写整体骨架（状态定义、循环结构），再填细节。代码风格清晰，变量名有意义。
6. 验证：跑例子，特判边界（空数组、单元素、已有序、全相等）。讨论时间/空间复杂度。

追问技巧：面试官问"能不能优化"时，先问"是优化时间还是空间？"通常用空间换时间（哈希表、记忆化）或换数据结构（堆、单调栈）能进一步提升。

算法刷题的顺序建议是什么？

按"模板优先、由浅入深、专题突破"的原则：

第一阶段：基础模板（2~4 周）

• 数组/字符串：遍历、双指针、滑动窗口
• 二分查找：标准模板、左右边界、旋转数组
• 排序：快排、归并（手写）、堆排
• 链表：反转、合并、判环、删除

第二阶段：搜索与回溯（2~3 周）

• BFS：层序、最短步数
• DFS：岛屿、连通分量
• 回溯：全排列、子集、组合、N 皇后

第三阶段：动态规划（3~4 周）

• 一维 DP：爬楼梯、打家劫舍、最大子段和
• 二维 DP：路径、LCS、编辑距离
• 背包 DP：0-1 背包、完全背包
• 树形 DP、区间 DP、状态压缩 DP

第四阶段：进阶（按需）

• 贪心（区间调度、跳跃游戏）
• 单调栈/队列、并查集、Trie
• 图论（最短路、拓扑排序、最小生成树）
• 高级数据结构（线段树、字典树、跳表）

第五阶段：冲刺

• 高频题二刷、按公司题库刷、模拟面试。

资源建议：LeetCode Hot 100、LeetCode 精选 Top 面试 150、剑指 Offer。刷题重在"质量"而非"数量"——一道题想清楚状态定义和转移，胜过刷十道不求甚解。

用 JavaScript/TypeScript 写算法有哪些常见坑？

一、大数精度 JS 数字是 IEEE 754 双精度浮点，超过 Number.MAX_SAFE_INTEGER（2^53 - 1）会失精度。题目给 n > 2^53 时用 BigInt：

const big = 9007199254740993n; // 加 n 后缀
console.log(big + 1n); // 9007199254740994n
// 注意：BigInt 与 Number 不能直接混合运算
// console.log(big + 1); // TypeError

位运算 >> 把操作数转 32 位有符号整数，对 > 2^31 - 1 的数会出错，应改用 Math.floor：

// 错误：(lo + hi) >> 1 在大数下溢出
// 正确：
const mid = lo + Math.floor((hi - lo) / 2);
// 或
const mid = lo + (((hi - lo) / 2) | 0);

二、数组引用与拷贝 JS 数组是引用类型，传参和赋值都是引用：

const a = [1, 2, 3];
const b = a;          // 引用，b === a
b.push(4);            // a 也变成 [1,2,3,4]
const c = [...a];     // 浅拷贝
const d = a.slice();  // 浅拷贝
// 嵌套数组需要深拷贝：
const e = JSON.parse(JSON.stringify(a));
const f = structuredClone(a); // 现代浏览器支持

回溯中 res.push(path) 推的是引用，path 后续会被 pop 改掉，必须 [...path] 拷贝。

三、位运算符 JS 位运算把操作数转 32 位有符号整数。>>> 是无符号右移，可把负数转成正数。常见技巧：

// 取整
const x = 3.7 | 0;          // 3
// 判断奇偶
const isOdd = (n & 1) === 1;
// 交换
[a, b] = [b, a]; // ES6 解构，比 ^ 异或交换更易读
// 异或性质：a ^ a = 0, a ^ 0 = a
// 找唯一出现一次的数：全部异或一遍

四、shift() 性能 Array.prototype.shift() 是 O(n) 操作（后续元素全部前移）。BFS 大队列用 shift 会让整体复杂度变 O(n²)。优化：

// 用 head 指针模拟双端队列
const queue: number[] = [];
let head = 0;
queue.push(1);
const front = queue[head++]; // O(1)
// queue[head] 之后的元素是有效部分，最后清理

五、字符串不可变 JS 字符串不可变，s[i] = 'x' 不生效。需要修改字符串要先转数组：

const arr = s.split('');
arr[0] = 'X';
const newStr = arr.join('');

字符串拼接 += 在循环中可能 O(n²)（部分引擎会优化），大数据量用数组 push 后 join。

六、Map vs Object 做哈希

• Map 的键可以是任意类型（对象、数字），保留插入顺序，size 属性。
• Object 的键只能是字符串/Symbol，数字键会被转成字符串，obj[1] 与 obj['1'] 是同一个。
• 算法中需要数字/对象作键时用 Map。

七、sort 默认按字典序 [10, 2, 1].sort() 默认返回 [1, 10, 2]（按字符串字典序），必须传比较函数：

arr.sort((a, b) => a - b);  // 数字升序
arr.sort((a, b) => b - a);  // 数字降序

八、递归深度限制 V8 默认递归深度约 10000~15000，超过会栈溢出。深度大的 DFS（如 1000×1000 网格全 1）必须改迭代或 BFS。

链表题为什么要用 dummy 哨兵节点？

链表题里需要修改头节点（如删除头、插入新头）时，没有前驱节点需要特殊处理。引入 dummy 哨兵节点指向 head，所有节点都有了"前驱"，统一处理逻辑。

function removeElements(head: ListNode | null, val: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let cur = dummy;
  while (cur.next) {
    if (cur.next.val === val) {
      cur.next = cur.next.next; // 删除
    } else {
      cur = cur.next;
    }
  }
  return dummy.next; // 真正的头
}

好处：

1. 不用特判头节点是否被删/换。
2. 返回 dummy.next 即新头，统一处理。

链表题 90% 都该用 dummy，省去繁琐的边界判断。

滑动窗口和双指针是一回事吗？

关系：滑动窗口是双指针的一种特例。双指针是一个大类，包含：

• 快慢指针（同向）：slow / fast 同向走，用于链表判环、原地修改。
• 左右指针（对撞）：从两端向中间走，用于有序数组两数之和、回文。
• 滑动窗口（同向）：left / right 同向走，维护一个区间，right 扩张 left 收缩。

区别：

维度	普通双指针	滑动窗口
指针关系	两指针相对独立或对撞	两指针共同定义一个窗口
移动方式	按规则同步移动	右端固定扩张、左端按条件收缩
维护状态	通常只看指针所指元素	需维护窗口内状态（计数、和、Map）
典型题	两数之和、回文	最长无重复子串、最小覆盖子串

口诀：看到"子串/子数组 + 最长/最短" → 滑动窗口；看到"有序 + 配对/对称" → 双指针。