JavaScript 算法题库实战指南：从数据结构到边界测试

逐项整理 18 类 JavaScript 算法主题，配套不变量、复杂度、边界测试和 4 个可运行示例。

本文围绕 ConardLi/awesome-coding-js 做原创工程整理。项目来自 腾讯新闻前端团队 2022 年的 25 个 Awesome 项目推荐；上游 README 固定到 2022-05-29 commit 80ab1916e75057ad900c2b22a7e9a694b9214350；README 声明 CC BY-NC 4.0，本文不复制原文或代码 下方保留固定版本入口。

仓库内容地图

• 语言专题：手写 API、Promise、事件、数组与异步行为
• 基础结构：排序、数组、字符串、链表、栈/队列、哈希表和堆
• 树与图：二叉树操作、DFS、BFS、可达性和最短无权路径
• 算法范式：二分、分治、递归、回溯、动态规划与贪心
• 数学专题：位运算、整数精度、数字转换和数论类练习
• 实践迁移：把复杂度、测试和运行时边界连接到前端场景

怎么读才有收获

按“契约 -> 基线 -> 不变量 -> 复杂度 -> 边界测试”推进。不要背代码；说明状态为何正确，测试空值、重复值和极限规模。JavaScript 还要注意数组副作用、Map/Set、Number 安全整数、BigInt、UTF-16 和递归栈。

题库全景：按能力而不是按文件名学习

上游目录可以完整归为 18 个主题。下面保留主题范围，解释每一组要掌握的模型；示例和讲解均为重新编写，不是逐题复制原仓库代码。

1. JavaScript 专题：手写 call/apply/bind、EventEmitter、防抖与节流、浅拷贝和深拷贝、数组去重/扁平化/极值、随机洗牌、柯里化、JSONP、Promise、ES5 继承、instanceof、Promise Ajax、单例、异步循环打印和图片懒加载。重点不是背手写实现，而是理解 this、闭包、队列、引用图和清理时机。
2. 排序：复杂度和排序概览，以及冒泡、插入、选择、堆、快速、归并排序。要能说清稳定性、原地性、最好/平均/最坏复杂度和输入分布的影响。
3. 二叉树：节点操作、前/中/后序遍历、由遍历序列重建、层序与分层打印、对称/镜像、深度和平衡、BST 第 K 小与后序验证、路径和、转双向链表、锯齿遍历、序列化、后继节点和子树判断。
4. 链表：删除节点和重复节点、逆序输出、倒数第 K 个、反转、复杂链表复制、相交节点、环入口与约瑟夫环。练习指针重连前先画出 next 关系。
5. 字符串：替换空格、判断数字串、字符流首个不重复字符、排列、反转和正则匹配。要区分字节、UTF-16 code unit、Unicode code point 与用户看到的 grapheme。
6. 栈和队列：两个栈实现队列、最小栈、压入/弹出序列合法性、滑动窗口最大值。单调栈和双端队列是进一步处理“最近更大/更小值”的常用工具。
7. 数组：奇偶分区、排序数组计数、众数、最大子数组和、最小拼接数、首个不重复字符、扑克牌顺子、配对和、两数/三数/四数之和、和为目标值的连续区间、乘积数组、顺时针矩阵遍历和逆序对。注意是否允许排序改变原顺序。
8. 堆：堆的插入、删除和调整；数据流中位数；第 K 小或最小的 K 个数。堆解决的是动态极值，不等同于把全部数据排序。
9. 哈希表：键到值的索引、频次计数、去重和补数查询；关注键的等价规则、冲突由实现处理，以及空间换时间的成本。
10. 分治：把规模拆成子问题、递归求解并合并；归并统计逆序对是典型例子，拆分与合并都要证明不漏不重。
11. 数学运算：位计数、幂、异或找唯一数、无加号求和、字符串转整数、数字 1 的计数、1 到 n 求和和丑数。必须把溢出、负数、非法字符和精度边界写进契约。
12. 查找：二维有序矩阵、排序数组中的计数、数字 1 的计数。二分的关键是区间定义和循环不变量，而不是记某一份模板。
13. DFS 和 BFS：用栈/递归探索深度，用队列按层扩展；图和网格都需要明确访问标记何时写入，避免重复入队或循环。
14. 递归和循环：斐波那契、普通/不规则台阶、矩形覆盖。递推关系之外，还要看重复子问题、调用栈、初始条件和数值增长。
15. 回溯算法：路径和、排列、若干数求和、矩阵路径、机器人移动、N 皇后及其计数版本。递归进入时做选择，返回时撤销；剪枝必须有正确性理由。
16. 动态规划：斐波那契、最小路径和、打家劫舍。定义状态、写转移、设边界、确定遍历顺序，最后再判断能否压缩空间。
17. 贪心算法：分配饼干一类的局部选择。每次选择都要证明不会排除全局最优，不能因为样例通过就称它为贪心正确。
18. 其他专栏：上游还有作者的其他内容入口。本文只保留主题层面的定位，不搬运个人联系方式、社交资料或未核实的外部正文。

先建立一套解题工作流

1. 把题目改写成输入输出契约

写清输入规模、空值/空集、重复项、是否排序、是否原地修改、返回值和错误输入如何处理。比如“返回第 K 小”要先问 K 从 0 还是 1 开始、重复值是否分别计数、输入是否可能为空。契约不明确，复杂度再漂亮也可能解错问题。

2. 先做可证明的基线，再优化

两层循环的 O(n²) 版本常常是很好的参照。先验证它符合契约，再观察重复工作：查找是否能缓存、是否可排序、是否存在单调性、是否有重叠子问题。优化不是把代码写短，而是用明确的数据结构降低成本，并保留正确性依据。

3. 用不变量组织循环

对每个循环写一句“每轮开始时什么条件一定成立”。二分可以说答案边界已被夹在半开区间内；反转链表可以说已处理部分始终指向原后缀；滑动窗口可以说窗口内所有元素满足题设约束。循环结束时由不变量推出结果，而不是靠手工跟踪碰巧正确。

4. 复杂度同时看时间、空间和输出

说明变量 n、m、V、E 的含义。图遍历通常是 O(V + E)，归并排序是 O(n log n) 时间并需 O(n) 辅助空间；列举所有排列本身就有阶乘级输出，不能承诺多项式时间。递归还要单独考虑栈深度。

5. 让测试逼近边界

至少覆盖空集、一个元素、全部相同、严格递增/递减、重复边界、极大值/极小值、不可达路径、退化树和大输入。小规模随机输入可以把优化解与简单基线做差分测试；固定随机种子并打印失败样本，便于复现。

常见算法模式与适用信号

这些信号只是候选解法。最终仍要用约束和证明确认模式成立；同一道题经常有多个解法，复杂度不是唯一的工程取舍。

JavaScript 实现中容易被忽略的边界

sort 的顺序、稳定性和副作用

Array.sort 会原地改动数组；不传比较函数时按字符串序比较，所以数字数组不能依赖默认排序。比较函数应当是纯函数并满足自反、反对称、传递等关系，遇到 NaN 要先定义策略。ECMAScript 2019 起排序稳定，但这不意味着可以忽略比较器的正确性。需要保留输入时先浅拷贝；对象元素仍共享引用。参考 MDN Array.sort。

Number、BigInt 与位运算

Number 只能精确表示 -(2^53 - 1) 到 2^53 - 1 的整数。超过安全范围时，两个数学上不同的整数可能比较为相等。BigInt 可表示任意精度整数，但不能与 Number 直接混合运算，位运算也要先确认操作数类型和题目范围。不要把“位运算更快”当作默认优化。参考 MDN MAX_SAFE_INTEGER 与 MDN BigInt。

数组、哈希与队列

Map/Set 适合表达通用键和值集合；普通对象更适合有明确字段结构的数据。需要频繁从队头取元素时，不要在大数组上反复 shift，可以用 head 下标推进，必要时周期性压缩。数组方法是否原地修改、返回新数组还是浅拷贝，必须看清 API 语义。参考 MDN keyed collections。

字符串不是“一个索引对应一个可见字符”

JavaScript 字符串索引指向 UTF-16 code unit。扩展字符可能占两个 code unit，emoji 组合还可能由多个 code point 构成。反转、截断或按字符计数时，应先明确题意需要 code unit、code point 还是用户感知字符；需要 grapheme 时使用 Intl.Segmenter 等合适工具。参考 MDN UTF-16。

递归、异步和运行环境

深树和极端输入会放大递归栈风险；可改用显式栈或队列。算法练习里的 Promise/异步顺序题要区分同步执行、微任务和任务队列；Web 页面中的计时、动画和懒加载还受渲染帧与可见性影响，不是纯粹的排序或遍历题。实现前确认运行环境、浏览器 API 和 Node API 是否可用。

四个从不变量出发的示例

lowerBound：第一个不小于 target 的位置

使用半开区间 [lo, hi)。每轮丢弃一半候选区间；循环结束时 lo 就是插入位置，复杂度 O(log n)，额外空间 O(1)。

function lowerBound(values, target) {
  let lo = 0;
  let hi = values.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (values[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

反转单链表：先保存未处理后缀

每一步先记住 next，再把当前节点接到已反转前缀。每个节点只处理一次，时间 O(n)，空间 O(1)。空表和单节点都会自然返回。

function reverseList(head) {
  let previous = null;
  let current = head;
  while (current !== null) {
    const next = current.next;
    current.next = previous;
    previous = current;
    current = next;
  }
  return previous;
}

最大子数组和：返回和与区间

以 endingSum 表示“必须以当前位置结尾”的最佳和。若前一段为负，重新从当前元素开始；额外跟踪起点才能返回区间。空数组在本实现中返回 null，明确避免把未定义结果伪装成 0。

function maxSubarrayRange(values) {
  if (values.length === 0) return null;
  let endingSum = values[0];
  let start = 0;
  let best = { sum: values[0], start: 0, end: 0 };
  for (let i = 1; i < values.length; i += 1) {
    if (endingSum < 0) {
      endingSum = values[i];
      start = i;
    } else {
      endingSum += values[i];
    }
    if (endingSum > best.sum) best = { sum: endingSum, start, end: i };
  }
  return best;
}

无权图最短路径：BFS 与父节点重建

BFS 按边数逐层扩展，因此首次访问目标时得到最少边数路径。队列用 head 指针避免反复搬移数组元素；parent 同时承担 visited 和路径回溯。该示例假设图用 Map<节点, 邻居数组> 表示，路径不存在时返回 null。

function shortestPath(graph, start, goal) {
  const parent = new Map([[start, null]]);
  const queue = [start];
  for (let head = 0; head < queue.length; head += 1) {
    const node = queue[head];
    if (node === goal) break;
    for (const next of graph.get(node) || []) {
      if (parent.has(next)) continue;
      parent.set(next, node);
      queue.push(next);
    }
  }
  if (!parent.has(goal)) return null;
  const path = [];
  for (let node = goal; node !== null; node = parent.get(node)) path.push(node);
  return path.reverse();
}

四个例子都应在重复值、边界节点、空输入或不可达输入上补测试。它们展示的是不变量和接口契约，不是对所有性能场景的通用最佳实现。

建议练习顺序与完成标准

1. 第一阶段：数组、字符串、哈希、双指针。先掌握遍历、计数、去重、前缀和与边界控制。完成标准：能解释 O(n²) 基线如何被索引或排序优化，并写差分测试。
2. 第二阶段：链表、栈、队列、二叉树。练指针、迭代/递归遍历、层序遍历和单调结构。完成标准：能画状态变化，并覆盖空结构、退化结构和重复值。
3. 第三阶段：二分、排序、堆、图搜索。练区间不变量、动态极值、可达性和无权最短路。完成标准：复杂度分析包含初始化、邻接结构和输出重建。
4. 第四阶段：回溯、动态规划、贪心、分治。从小规模暴力搜索开始，识别状态或选择，再给剪枝/转移/贪心交换论证。完成标准：每个状态都能用一句话定义，边界值有独立测试。
5. 第五阶段：JavaScript 实用专题。把 Promise、EventEmitter、防抖/节流、复制、懒加载放回浏览器/Node 环境中，补取消、清理、错误和竞态。完成标准：不仅算法结果正确，生命周期也不会泄漏监听器或旧请求覆盖新状态。

练习节奏可按每周 4 次、每次 30–60 分钟安排：独立推导、实现基线、优化并证明、复盘测试。记录错误类型比累计题数有用：边界遗漏、状态定义错误、复杂度判断错误、语言语义误用，分别对应不同补强方法。

与前端工程的连接

• 搜索建议：前缀索引、排序边界、请求去抖与过期响应取消；数据量大时评估 Worker，而非让主线程长时间计算。
• 虚拟列表：可见窗口计算、前缀高度索引、滚动位置和动态测量；算法结构要匹配固定高度或动态高度的实际约束。
• 依赖关系展示：拓扑排序和环检测；节点很多时使用邻接表，渲染层再做视口裁剪。
• 图片懒加载：IntersectionObserver 负责可见性信号，状态机负责 idle/loading/loaded/error，清理 observer 并处理快速滚动与缓存。
• 大量列表筛选：先定义筛选和排序语义，再选索引、缓存或分批计算；任何缓存都必须有失效规则。

参考资料与许可说明

上游 README 固定在 2022-05-29 的 commit 80ab1916e75057ad900c2b22a7e9a694b9214350，列出算法分类与专题题目，并声明 CC BY-NC 4.0。本文保留作者与上游来源归属，采用独立表述和重新编写的例子，不复制题解原文或原仓库代码。许可文本见 Creative Commons BY-NC 4.0。

• MDN：Array.sort
• MDN：Number.MAX_SAFE_INTEGER
• MDN：BigInt
• MDN：Map 与 Set
• MDN：UTF-16
• MDN：Intl.Segmenter

动手路线

1. 每个结构先做一个朴素解，再说明优化依赖的性质，并用小规模随机数据差分验证。
2. 给二分、排序、树/图遍历和动态规划分别写空集、重复值、退化输入与不可达用例。
3. 把算法映射到前端：搜索建议、虚拟列表、图片懒加载、依赖拓扑和大量列表筛选。

使用边界

上游 README 声明 CC BY-NC 4.0。本文保留作者/来源归属并独立撰写说明和示例，不复制原题解代码；题解仍需按具体运行环境验证。

原始入口

• 固定版本 README 与仓库入口
• 发现这份资源的原始推荐
• 返回 25 个开源项目专题目录