跳到主要内容

算法基础热门面试题

使用说明​

本篇共 45 道题。

本篇只覆盖算法知识与方法论，不重复“算法题”分类中的具体手写题。口头回答要能说清复杂度、适用条件和取舍。

Q1: 时间复杂度和空间复杂度是什么？​

答案：

它们描述输入规模增长时，运行步骤和额外内存的增长趋势，通常用 Big O 表示上界量级，忽略常数和低阶项。

复杂度不是实际耗时，缓存、数据分布和常数也重要；面试中还应说明平均、最坏和摊还情况。

  • 时间复杂度描述输入规模增长时操作次数的数量级，空间复杂度描述额外内存增长；通常讨论最坏或均摊情况，并忽略常数与低阶项。
  • 分析时要先定义 n 的含义，再看循环、递归和数据结构操作；相同大 O 仍可能因常数、缓存和输入分布表现不同。

Q2: 什么是摊还复杂度？​

答案：

把一系列操作的总成本平均到每次操作。例如动态数组偶尔扩容很贵，但多次追加的平均成本仍可视为 O(1) 摊还。

它不是概率平均，而是对操作序列的成本分析。

  • 摊还分析关注一串操作的平均成本，不是依赖随机输入的平均复杂度。例如动态数组偶尔扩容是 O(n)，但 n 次追加总成本 O(n)，单次摊还 O(1)。
  • 常用方法有聚合法、记账法和势能法；前提是昂贵操作不会在每次调用都发生。

Q3: 数组和链表怎么选？​

答案：

对比项数组链表
内存连续内存空间不连续，通过指针连接
读取O(1)O(1)，按下标随机访问O(n)O(n)，必须从头遍历
插入/删除O(n)O(n)，需移动元素O(1)O(1)，只修改指针（已知位置时）
缓存友好好（连续内存，CPU 预取）差（内存分散）

选择建议：

  • 频繁随机读取 → 数组
  • 频繁头部/中间插入删除 → 链表
  • 实际开发中，数组的缓存友好性使其在大多数场景下性能更好

Q4: 栈和队列分别适合什么场景？​

答案：

栈是后进先出，适合调用、括号、撤销和 DFS；队列是先进先出，适合任务调度、缓冲和 BFS。

优先使用提供 O(1) 头尾操作的数据结构，避免用数组头部频繁移动大批元素。

  • 栈是后进先出，适合调用栈、括号匹配、撤销和单调栈；队列是先进先出，适合 BFS、任务调度和消息缓冲。
  • 需要两端操作使用双端队列；JavaScript 不应频繁 shift() 实现大队列，可用头指针或环形数组避免 O(n) 移动。

Q5: 哈希表为什么平均查找是 O(1)？​

答案：

哈希函数把键映射到桶，分布均匀且装载因子受控时只需访问少量位置。冲突通过链、开放寻址等解决。

最坏可退化到 O(n)，还要考虑扩容、键相等和哈希攻击。它也不天然保持排序。

  • 哈希函数把键映射到桶，负载因子受控且冲突分布良好时，定位桶和比较少量候选的期望成本是 O(1)。
  • 最坏情况下大量冲突会退化到 O(n) 或树化后的 O(log n)。扩容也有 O(n) 成本，但通常按一系列操作摊还。

Q6: 二叉搜索树、平衡树和堆有什么区别？​

答案：

二叉搜索树维护左小右大，未平衡时会退化；平衡树限制高度，使查找/插入/删除保持 O(log n)；堆只保证父子优先级，擅长快速取最值。

要有序遍历和查任意键选搜索树，要维护 Top K/优先队列选堆。

  • BST 保持左小右大，理想查询 O(log n) 但可能退化；平衡树通过旋转控制高度，保证 O(log n)；堆只保证父子顺序，适合快速取极值。
  • 需要有序查找选平衡树，需要优先队列选堆；堆不能高效查任意值，BST 也不能 O(1) 取任意优先级更新。

Q7: 图有哪些常见表示方式？​

答案：

邻接表空间约 O(V+E)，适合稀疏图并便于遍历邻居；邻接矩阵空间 O(V²)，判断两点是否有边快，适合稠密图或矩阵算法。

还要根据有向/无向、权重和多重边设计结构。

  • 邻接表空间 O(V+E)，适合稀疏图并便于遍历邻居；邻接矩阵空间 O(V²)，判断两点是否相连 O(1)，适合稠密或节点少的图。
  • 带权图在边上存权重；如果需要频繁删除或去重，可用 Map/Set，但要考虑额外内存。

Q8: 稳定排序是什么意思？​

答案：

相等键的元素排序后保持原相对顺序。多字段分阶段排序和带附加信息的数据可能依赖稳定性。

归并排序通常稳定，常见原地快速排序不稳定。选择还要看时间、额外空间、数据规模和近乎有序等特征。

  • 稳定排序保证相等关键字元素的相对顺序不变。例如先按姓名排序再按部门做稳定排序，可以保留部门内姓名顺序。
  • 归并排序通常稳定，原地快速排序通常不稳定；稳定性是否重要取决于多字段排序和对象身份，不能只看时间复杂度。

Q9: 快速排序和归并排序怎么比较？​

答案：

对比项快速排序归并排序
思想先分区再递归先递归再合并
稳定性不稳定稳定
最坏时间O(n2)O(n^2)O(nlog⁡n)O(n \log n)
空间O(log⁡n)O(\log n)O(n)O(n)
适用场景一般场景需要稳定排序

Q10: 二分查找的适用条件是什么？​

答案：

搜索空间必须具有可利用的单调性或有序边界，每次比较能排除一半。它不只用于数组找值，也用于“答案是否可行”的单调判定。

实现重点是区间定义、循环条件、mid 和返回边界保持一致，防止 off-by-one。

  • 二分要求搜索空间具有单调性，不一定非得是数组查值；“答案是否可行”随答案单调变化时也能做答案二分。
  • 循环要明确闭区间还是半开区间，并统一更新与返回条件。遇到重复值还要区分找任意、左边界还是右边界。

Q11: 递归有哪些风险？​

答案：

递归把子问题自然映射到调用栈，但深度大时可能栈溢出，并有函数调用开销。没有缩小问题和终止条件会无限递归。

可用显式栈改写迭代，或根据运行环境验证尾调用是否真正优化，不能想当然。

  • 风险包括递归深度导致栈溢出、重复子问题导致指数复杂度，以及基线或状态恢复错误。JavaScript 引擎通常不能依赖尾调用优化。
  • 深树/图遍历可改显式栈；重复子问题加记忆化。每个递归都要说明终止条件、规模如何缩小和返回值含义。

Q12: 动态规划的核心是什么？​

答案：

问题具有重叠子问题和最优子结构时，定义状态和转移，把重复计算缓存下来。可以自顶向下记忆化，也可自底向上填表。

最难的是状态含义、初始条件和遍历顺序。先写出暴力递归关系，再优化通常更清楚。

  • 动态规划适用于最优子结构和重叠子问题。先定义状态含义，再写转移、初始化、遍历顺序和最终答案，而不是先背模板。
  • 从暴力递归画出选择树更容易发现重复状态；随后记忆化或自底向上，并根据依赖关系做滚动数组等空间优化。

Q13: 贪心算法什么时候正确？​

答案：

每一步选当前局部最优，并且能证明这种选择可以扩展为全局最优时才正确，常用交换论证或不变量证明。

“看起来合理”不是证明。若局部选择会影响未来且无法证明，可能需要 DP 或搜索。

  • 贪心每一步只做局部最优且不回退，只有问题具备贪心选择性质时才正确。通常用交换论证、反证或 cut property 说明局部选择不损失全局最优。
  • 如果当前选择会影响后续且无法证明安全，应考虑动态规划或搜索。面试不能因为样例通过就宣称贪心成立。

Q14: BFS 和 DFS 怎么选？​

答案：

BFS 按层扩展，无权图中首次到达通常是最短步数，但队列可能占内存；DFS 沿路径深入，适合回溯、连通性、拓扑等，空间取决于深度。

两者都要维护访问状态，图中遗漏会导致重复甚至死循环。

  • BFS 按层扩展，适合无权图最短步数、层序和最近目标；DFS 适合连通性、路径枚举、拓扑/环检测和回溯。
  • 二者时间通常都是 O(V+E)，差异在访问顺序和空间：BFS 队列可能保存整层，DFS 深度大时要防递归栈溢出。

Q15: 面试中拿到算法题应该如何分析？​

答案：

先复述输入输出和边界，给暴力方案与复杂度，再从数据规模、重复计算、单调性和数据结构寻找优化，写前用样例走一遍。

编码后检查空输入、重复值、溢出和复杂度，并主动说明取舍。清晰沟通通常和最终代码同样重要。

  • 先复述题意并确认输入规模、重复值、是否有序和边界，再给一个朴素解法作为正确性基线。
  • 然后识别瓶颈、选择数据结构并说明复杂度，写代码时持续说不变量；最后用空输入、单元素、极值和典型样例手动验证。

Q16: O(n)O(n) 和 O(2n)O(2n) 有区别吗？​

答案：

从大 O 表示法角度，它们是相同的，都是 O(n)O(n)。因为大 O 关注的是增长趋势，常数系数会被忽略。

Q17: 动态数组扩容为什么常说插入是摊还 O(1)O(1)？​

答案：

大部分尾部插入只把元素写到下一个空位，成本是 O(1)O(1)；容量不足时需要申请更大空间并复制已有元素，单次成本是 O(n)O(n)。

如果容量按倍数增长，昂贵复制不会每次发生。把一段连续插入的总复制成本相加，它与插入次数同阶，因此平均到每次操作是摊还 O(1)O(1)。

摊还复杂度不等于每一次都快，也不涉及随机概率。对延迟敏感的实时场景仍要关注扩容尖峰，可提前预留容量或选择分块结构。

Q18: 动态规划和贪心算法的区别是什么？怎么判断用哪个？​

答案：

对比项动态规划贪心算法
决策方式考虑所有子问题，找全局最优每步选局部最优，不回头
子问题有重叠子问题无需回看之前的选择
最优性保证全局最优不一定全局最优
复杂度通常更高通常更低

判断方法：

  • 如果问题具有最优子结构且贪心选择性质（局部最优能推出全局最优），用贪心
  • 如果问题具有重叠子问题且无法用贪心保证全局最优，用 DP
  • 拿不准时，先尝试贪心（简单），行不通再用 DP
// 贪心适用：活动选择问题（选结束时间最早的）
// DP 适用：0-1 背包（不能贪心选性价比最高的）

// 同一道题的不同变体可能用不同方法：
// 买卖股票（最多 1 次）→ 贪心
// 买卖股票（最多 k 次）→ DP

Q19: 归并排序为什么适合外部排序？​

答案：

数据大于内存时，可以先把数据分成若干能装入内存的块，各块在内存中排序后写回磁盘，再使用多路归并按顺序读取少量缓冲区并生成最终结果。

归并过程主要是顺序 I/O，比频繁随机访问更适合磁盘和对象存储。实际实现还要根据内存、文件句柄和 I/O 带宽决定归并路数，并处理临时文件、失败恢复和稳定性。

这也是数据库排序、日志处理和大文件去重中常见的基础思路。

Q20: 求 Top K 时，堆和快速选择怎么选？​

答案：

  • 维护大小为 K 的堆：时间约 O(nlog⁡K)O(n\log K)，空间 O(K)O(K)，适合流式数据、K 较小或不能修改原数组。
  • 快速选择：平均 O(n)O(n)、最坏 O(n2)O(n^2)，通常可原地处理，适合一次性数组且只需要找到分界。
  • 全量排序：O(nlog⁡n)O(n\log n)，当还需要完整有序结果或数据量不大时更简单。

面试时要先确认是否需要结果内部有序、数据是否流式、能否修改输入，以及最坏情况是否有严格保证。

Q21: 为什么要用大 O 而不是具体运行时间？​

答案：

  1. 运行时间受硬件影响，不同电脑跑出来不一样
  2. 大 O 描述的是可扩展性，当数据量变大时的表现
  3. 更方便比较不同算法的优劣

Q22: 栈和队列分别在前端有哪些应用？​

答案：

栈的应用：

  • 浏览器前进/后退：用两个栈分别管理历史和前进记录
  • 函数调用栈：JavaScript 执行上下文栈
  • 括号匹配：编辑器语法检查
  • 撤销/重做：编辑器的 undo/redo

队列的应用：

  • 事件循环：宏任务队列、微任务队列
  • 消息队列：异步任务处理
  • BFS：层序遍历 DOM 树
  • 打印队列：按顺序处理任务

Q23: 双向 BFS 什么时候比普通 BFS 更合适？​

答案：

当起点和终点都明确、状态转移可以反向生成，并且求的是无权图最短路径时，可以从两端同时 BFS，在两侧访问集合相遇时得到最短距离。若每层分支数约为 b、路径深度为 d，搜索规模可能从 b 的 d 次方降到两侧约 b 的 d/2 次方。

实现要点：

  • 每次优先扩展节点更少的一侧。
  • 两侧分别维护距离或层级，发现交集时正确合并。
  • 有向图需要能获得反向邻接关系。
  • 目标集合很多时，可把全部目标作为一侧的多源起点。

没有明确终点、反向转移困难或图很小时，普通 BFS 更简单。

Q24: 为什么快排比堆排序快？​

答案：

虽然都是 O(nlog⁡n)O(n \log n)，但快排的常数因子更小：

  1. 快排的内存访问是连续的，缓存命中率高
  2. 堆排序需要频繁跳跃访问，缓存不友好

Q25: 二分查找中 left <= right 和 left < right 怎么选？​

答案：

写法right 初始值循环条件更新方式适用场景
左闭右闭 [l, r]length - 1left <= rightright = mid - 1精确查找目标值
左闭右开 [l, r)lengthleft < rightright = mid查找边界（lower_bound）
// 左闭右闭：搜索区间为空时停止 [left, right] 当 left > right 时为空
while (left <= right) {
  // left === right 时仍有一个元素需要检查
}

// 左闭右开：搜索区间为空时停止 [left, right) 当 left === right 时为空
while (left < right) {
  // left === right 时区间已空
}

建议：先熟练掌握左闭右闭写法，再学左闭右开写法用于找边界。

Q26: 空间换时间是什么意思？​

答案：

用更多内存来减少计算时间。例如两数之和：

  • 暴力解法：O(n2)O(n^2) 时间，O(1)O(1) 空间
  • 哈希表解法：O(n)O(n) 时间，O(n)O(n) 空间

Q27: 哈希表的哈希冲突怎么解决？​

答案：

哈希冲突是指不同的 key 经过哈希函数计算后得到相同的位置。常见解决方式：

  1. 链地址法（Chaining）：每个位置存储一个链表，冲突的元素追加到链表中。JavaScript 的 Map 底层就采用类似策略。

  2. 开放寻址法（Open Addressing）：冲突时，按照某种规则寻找下一个空位置。

// 链地址法简单示意
class SimpleHashMap<V> {
  private buckets: [string, V][][] = new Array(16).fill(null).map(() => []);

  private hash(key: string): number {
    let h = 0;
    for (const char of key) {
      h = (h * 31 + char.charCodeAt(0)) % this.buckets.length;
    }
    return h;
  }

  set(key: string, value: V): void {
    const index = this.hash(key);
    const bucket = this.buckets[index];
    const existing = bucket.find(([k]) => k === key);
    if (existing) {
      existing[1] = value;
    } else {
      bucket.push([key, value]);
    }
  }

  get(key: string): V | undefined {
    const index = this.hash(key);
    const pair = this.buckets[index].find(([k]) => k === key);
    return pair?.[1];
  }
}

Q28: 滑动窗口和双指针有什么关系？​

答案：

滑动窗口本质上是双指针的一种特殊形式：

  • 双指针是通用概念，两个指针可以同向、反向、快慢移动
  • 滑动窗口是双指针的子集，特指两个指针同向移动且维护一个连续区间
// 双指针（左右指针） —— 两端向中间移动
function twoSumSorted(nums: number[], target: number): number[] {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

// 滑动窗口 —— 两个指针同向右移，维护窗口
function maxSumK(nums: number[], k: number): number {
  let sum = 0;
  let maxSum = -Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    if (right >= k - 1) {
      maxSum = Math.max(maxSum, sum);
      sum -= nums[right - k + 1];
    }
  }
  return maxSum;
}

Q29: 什么时候用计数排序/桶排序/基数排序？​

答案：

这些是非比较排序，适用于特定场景：

  • 计数排序：数据范围小（如 0-100 的整数）
  • 桶排序：数据分布均匀
  • 基数排序：整数或字符串排序

Q30: 如何用二分查找解决「在答案上二分」类型的题目？​

答案：

有些题目不是在数组中查找元素，而是在答案的范围上进行二分。核心思路是：如果答案具有单调性（答案越大越容易满足/越难满足条件），就可以二分。

// 例：木材切割 - 将 n 根木头切成 k 段等长的，求最大长度
function maxLength(woods: number[], k: number): number {
  let left = 1;
  let right = Math.max(...woods);

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    // 以 mid 为长度能切出多少段？
    const count = woods.reduce((sum, w) => sum + Math.floor(w / mid), 0);

    if (count >= k) {
      left = mid + 1;   // 还能切更长
    } else {
      right = mid - 1;  // 切太长了，段数不够
    }
  }

  return right;
}

这类题目的特征：

  • 答案有明确的上下界
  • 给定答案可以快速验证是否可行
  • 答案具有单调性（可行/不可行的分界线）

Q31: 回溯算法的时间复杂度怎么分析？​

答案：

回溯的时间复杂度取决于搜索树的大小（节点数）：

题型时间复杂度说明
全排列（n 个不同元素）O(n!)O(n!)第一层 n 个选择，第二层 n-1，...
组合（n 选 k）O(C(n,k))O(C(n,k))即 O(n!k!(n−k)!)O(\frac{n!}{k!(n-k)!})
子集（2^n 个）O(2n)O(2^n)每个元素选或不选
N 皇后O(n!)O(n!)（有剪枝）实际远小于 nnn^n
// 分析方法：看搜索树的分支因子和深度
// 排列：分支因子递减 n × (n-1) × ... × 1 = n!
// 组合/子集：每个元素选或不选，2 × 2 × ... × 2 = 2^n
// 剪枝可以大幅降低实际运行时间，但不改变最坏复杂度

Q32: 什么是记忆化搜索？和动态规划有什么关系？​

答案：

记忆化搜索是自顶向下的 DP，本质相同，实现方式不同：

对比项记忆化搜索（自顶向下）DP（自底向上）
实现递归 + 缓存循环 + dp 数组
思路从大问题拆到小问题从小问题推到大问题
优点直观，只计算需要的子问题无递归开销，方便空间优化
缺点有递归栈开销可能计算不需要的子问题
面试建议适合快速出解适合优化空间
// 同一个问题的两种写法——最长递增子序列

// 记忆化搜索
function lisMemo(nums: number[]): number {
  const memo = new Map<number, number>();

  function dfs(i: number): number {
    if (memo.has(i)) return memo.get(i)!;
    let maxLen = 1;
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        maxLen = Math.max(maxLen, dfs(j) + 1);
      }
    }
    memo.set(i, maxLen);
    return maxLen;
  }

  let result = 0;
  for (let i = 0; i < nums.length; i++) {
    result = Math.max(result, dfs(i));
  }
  return result;
}

// 自底向上 DP（完全等价）
function lisDP(nums: number[]): number {
  const dp = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  return Math.max(...dp);
}

Q33: 如何设计 DP 的状态定义？​

答案：

状态定义是 DP 最难的一步，常见套路：

1. 线性 DP：dp[i] = 以第 i 个元素结尾的最优解
   或：dp[i] = 前 i 个元素的最优解

2. 二维 DP：
   - dp[i][j] = 用前 i 个物品，容量为 j 的背包的最大价值（背包）
   - dp[i][j] = s1 前 i 个字符和 s2 前 j 个字符的最优解（字符串）
   - dp[i][j] = 区间 [i, j] 的最优解（区间 DP）

3. 状态需要额外信息时增加维度：
   - dp[i][0/1] = 第 i 天持有/不持有股票的最大利润
   - dp[i][j][k] = 第 i 天最多 j 次交易，状态 k 的最大利润
状态定义的验证方法

定义完状态后，检查：

  1. 能否写出转移方程？如果写不出来，可能状态定义不对
  2. 初始值能否确定？
  3. 最终答案是 dp[n] 还是 max(dp[...])？

Q34: 贪心算法怎么证明正确性？面试需要证明吗？​

答案：

面试中不需要严格数学证明，但需要说清楚直觉：

常用论证方式：
1. 交换论证："如果不选当前最优的，换成其他的只会更差或一样"
2. 反证法："假设贪心选择不对，那最优解中用了什么？交换后呢？"
3. 直觉解释："选最早结束的活动，剩余时间最多，能安排更多活动"
// 例：合并区间为什么按左端点排序？
// 答：排序后保证相邻区间的左端点递增，
//     只需看当前区间的左端点是否在前一个区间的右端点内，
//     就能判断是否重叠。如果不排序，需要两两比较 O(n²)

// 例：跳跃游戏为什么维护 maxReach？
// 答：只要最远能跳到的位置 >= 终点，就一定能到达。
//     不需要关心具体怎么跳，因为中间经过的每个位置都能贡献跳跃距离

Q35: 回溯算法中如何去重？​

答案：

当输入包含重复元素时，回溯可能产生重复结果。核心思路：排序 + 同一层跳过相同元素。

// 关键代码（以组合为例）
candidates.sort((a, b) => a - b); // 步骤 1：排序

function backtrack(start: number, path: number[]) {
  for (let i = start; i < candidates.length; i++) {
    // 步骤 2：同一层中，跳过和前一个相同的元素
    if (i > start && candidates[i] === candidates[i - 1]) continue;

    path.push(candidates[i]);
    backtrack(i + 1, path);
    path.pop();
  }
}

理解"同一层 vs 同一树枝"：

candidates = [1, 1, 2], target = 3

       []
     / | \
    1  1  2     ← 同一层：第二个 1 要跳过！
   / \  |
  1   2 2       ← 不同层（树枝方向）：第二个 1 不跳过
  |
  2

结果：[1,1,2]（不会出现重复的 [1,2]）
  • i > start（不是 i > 0！）：只在同一层去重，树枝方向的重复是允许的

Q36: DP 中的背包问题有哪些类型？怎么区分？​

答案：

背包类型每个物品遍历顺序（一维优化）典型题目
0-1 背包只能选 1 次容量从大到小分割等和子集
完全背包可以选无限次容量从小到大零钱兑换
多重背包有数量限制二进制优化面试少见
// 0-1 背包（一维优化）
function knapsack01(weights: number[], values: number[], capacity: number): number {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let j = capacity; j >= weights[i]; j--) { // 从大到小！
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

// 完全背包（一维优化）
function knapsackComplete(weights: number[], values: number[], capacity: number): number {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let j = weights[i]; j <= capacity; j++) { // 从小到大！
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}
背包遍历顺序的本质
  • 0-1 背包从大到小：保证每个物品只用一次（dp[j-w] 还是上一行的值）
  • 完全背包从小到大：允许重复使用（dp[j-w] 是本行已更新的值）

Q37: 递归和迭代怎么互相转换？​

答案：

所有递归都可以改成迭代（用显式栈模拟调用栈），但不是所有场景都值得转换。

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

// 迭代版前序遍历（用栈模拟）
function preorderIterative(root: TreeNode | null): number[] {
  if (!root) return [];
  const result: number[] = [];
  const stack: TreeNode[] = [root];

  while (stack.length) {
    const node = stack.pop()!;
    result.push(node.val);
    // 先压右子树，后压左子树（栈是后进先出）
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
}

转换原则：

  • 尾递归 → 直接改成循环（最简单）
  • 线性递归（如链表反转）→ 循环 + 几个变量
  • 树递归（如二叉树遍历）→ 显式栈
  • 复杂回溯 → 通常保持递归更清晰，不强行转换

Q38: 如何用滑动窗口解决子串/子数组问题？​

答案：

滑动窗口的通用模板：

function slidingWindow(s: string): number {
  const window = new Map<string, number>(); // 窗口内的统计
  let left = 0;
  let result = 0;

  for (let right = 0; right < s.length; right++) {
    const charIn = s[right];
    // 1. 扩大窗口（右指针右移）
    window.set(charIn, (window.get(charIn) || 0) + 1);

    // 2. 收缩窗口（左指针右移，直到窗口合法）
    while (窗口不满足条件) {
      const charOut = s[left];
      window.set(charOut, window.get(charOut)! - 1);
      if (window.get(charOut) === 0) window.delete(charOut);
      left++;
    }

    // 3. 更新结果
    result = Math.max(result, right - left + 1);
  }
  return result;
}

关键判断：

  • 求最长 → 在窗口合法时更新结果，while 收缩到合法为止
  • 求最短 → 在窗口合法时收缩并更新结果
  • 窗口什么时候合法/不合法 → 取决于题目条件

Q39: 快慢指针为什么能检测链表有环？​

答案：

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true; // 相遇说明有环
  }
  return false; // fast 到了 null，说明无环
}

原理：想象两个人在环形跑道上跑步，快的人一定会追上慢的人（在环上套圈）。

数学证明：假设环长为 C，进入环时快指针在慢指针前方 k 步。每走一步，距离缩小 1。经过 k 步后，两者必然相遇。

找环入口：相遇后，一个指针回到 head，两指针都以步长 1 前进，再次相遇点就是环入口。原因：设头到环入口距离为 a，环入口到相遇点距离为 b，环长为 C，则 a = C - b。

Q40: 什么是单调队列？它适合解决哪些问题？​

答案：

单调队列通常用双端队列维护候选元素的单调性，使队首始终是当前窗口的最大值或最小值。每个元素最多入队、出队一次，因此滑动窗口最值可以从朴素 O(nk) 降到 O(n)。

以窗口最大值为例：

  1. 新元素进入前，从队尾移除所有不大于它的元素。
  2. 队首索引离开窗口时将其移除。
  3. 窗口形成后，队首就是当前最大值。

队列通常保存索引而不是值，才能判断过期位置。它和单调栈都维护单调结构，但单调队列还要处理窗口左边界。

Q41: 二维 DP 怎么优化空间？​

答案：

当 dp[i][j] 只依赖于上一行 dp[i-1][...] 时，可以压缩为一维数组：

// 二维 DP：最长公共子序列
function lcsOriginal(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n]; // 空间 O(m×n)
}

// 空间优化为一维
function lcsOptimized(s1: string, s2: string): number {
  const n = s2.length;
  const dp = new Array(n + 1).fill(0);

  for (let i = 1; i <= s1.length; i++) {
    let prev = 0; // 保存 dp[i-1][j-1]
    for (let j = 1; j <= n; j++) {
      const temp = dp[j]; // 保存被覆盖前的值
      if (s1[i - 1] === s2[j - 1]) {
        dp[j] = prev + 1;
      } else {
        dp[j] = Math.max(dp[j], dp[j - 1]);
      }
      prev = temp;
    }
  }
  return dp[n]; // 空间 O(n)
}

优化技巧总结：

  • dp[i] 只依赖 dp[i-1] → 用两个变量滚动（如爬楼梯）
  • dp[i][j] 只依赖上一行 → 压缩为一维数组 + prev 变量
  • 0-1 背包一维优化 → 逆序遍历容量

Q42: 前端面试中最常考的算法思维有哪些？​

答案：

按频率排序：

排名算法思维高频题目
1哈希表两数之和、字符频次、去重
2双指针反转链表、合并有序、移动零
3DFS/BFS二叉树遍历、岛屿数量、层序
4滑动窗口无重复最长子串、最小覆盖子串
5动态规划爬楼梯、零钱兑换、最长递增子序列
6排序+贪心合并区间、会议室
7回溯全排列、组合、子集
8栈/队列有效括号、最小栈、滑动窗口最大值
9二分查找旋转数组搜索、第 K 大元素
前端面试算法特点
  • 难度集中在 Easy ~ Medium，Hard 较少
  • 偏爱实际开发场景的题（LRU 缓存、扁平化、深度比较）
  • 手写题也算算法（Promise.all、防抖节流、深拷贝）
  • 重在思路清晰、代码规范，不追求极致优化

Q43: 什么是单调栈？适合解决哪些问题？​

答案：

单调栈在入栈时维护元素单调性，使每个元素最多入栈、出栈一次，整体通常是 O(n)。

它适合寻找“左边或右边第一个更大/更小元素”、柱状图最大矩形、每日温度等问题。关键是先确定栈里保存索引还是值，以及弹栈时能结算什么答案。

Q44: 什么是并查集？​

答案：

并查集维护若干不相交集合，核心操作是查询两个元素是否连通以及合并两个集合。

  • 用父指针表示集合树。
  • 路径压缩降低后续查询高度。
  • 按秩或按大小合并避免树退化。

它常用于连通分量、冗余边和 Kruskal 最小生成树，优化后单次操作接近常数时间。

Q45: 什么是拓扑排序？什么时候不存在结果？​

答案：

拓扑排序给有向无环图安排一个顺序，使每条边的起点都在终点之前。可以用入度为零的队列，也可以用 DFS 后序完成。

如果最终处理的节点数小于总节点数，说明图中存在环，不存在合法拓扑序。常见场景包括课程依赖、任务调度和构建依赖。

相关链接​