外观
算法、编程题与设计模式
1. 实现发布订阅模式
答案：
发布订阅模式由事件中心维护事件与监听器的映射，发布者只负责触发事件，订阅者通过回调接收通知，二者互不依赖。实现时应支持订阅、发布、取消订阅，并复制回调数组后再执行，避免回调中取消订阅影响本轮遍历。
js
class Emitter {
constructor() { this.events = new Map(); }
on(type, fn) {
if (!this.events.has(type)) this.events.set(type, new Set());
this.events.get(type).add(fn);
return () => this.off(type, fn);
}
off(type, fn) {
const set = this.events.get(type);
if (!set) return;
set.delete(fn);
if (!set.size) this.events.delete(type);
}
emit(type, ...args) {
[...(this.events.get(type) || [])].forEach(fn => fn(...args));
}
}2. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。编码规则为：k[encoded_string]，表示 encoded_string 重复 k 次。其中 k 为正整数，encoded_string 不包含数字。
示例：
- 输入：
"3[a]2[bc]" - 输出：
"aaabcbc"
答案：
用两个栈分别保存当前字符串和当前重复次数。遇到数字累积多位数，遇到 [ 将当前上下文入栈并清空片段，遇到 ] 取出上下文拼接，普通字符追加到当前片段。输入 3[a]2[bc] 输出 aaabcbc。时间复杂度为 O(n + 输出长度)，空间复杂度为 O(n)。
js
function decodeString(s) {
const counts = [], texts = [];
let num = 0, cur = '';
for (const ch of s) {
if (/\d/.test(ch)) num = num * 10 + Number(ch);
else if (ch === '[') { counts.push(num); texts.push(cur); num = 0; cur = ''; }
else if (ch === ']') { cur = texts.pop() + cur.repeat(counts.pop()); }
else cur += ch;
}
return cur;
}3. 实现函数parallelRequests(urls, maxConcurrent)
javascript
// 要求：
// 1. 最多同时执行maxConcurrent个请求
// 2. 请求完成（无论成功/失败）后立即补位新请求
// 3. 返回Promise，结果为所有请求响应数组（顺序需与urls一致）
function parallelRequests(urls, maxConcurrent) {
// 请补充实现
}答案：
用共享索引分配任务，每个 worker 完成一次请求后在 finally 中继续领取任务，因此成功或失败都会立即补位；结果按原索引写入，最终统一返回。这里假设 urls 通过 fetch 请求，非法并发数直接报错。
js
async function parallelRequests(urls, maxConcurrent) {
if (!Number.isInteger(maxConcurrent) || maxConcurrent < 1) throw new RangeError('maxConcurrent');
const result = new Array(urls.length);
let next = 0;
async function worker() {
while (true) {
const i = next++;
if (i >= urls.length) return;
try {
const response = await fetch(urls[i]);
if (!response.ok) throw new Error(`HTTP ${response.status}`);
result[i] = await response.json();
} catch (e) { result[i] = e; }
}
}
await Promise.all(Array.from({ length: Math.min(maxConcurrent, urls.length) }, worker));
return result;
}复杂度为 O(n)，额外空间为 O(n)，并发峰值不超过 maxConcurrent。
4. 最大公共前缀
编写一个函数，接收一个字符串数组作为输入，找出这些字符串的最大公共前缀。如果没有公共前缀，则返回空字符串。
输入输出要求：
- 输入：一个字符串数组。
- 输出：一个字符串，表示最大公共前缀。
示例：
javascript
const input = ["flower", "flow", "flight"];
const result = longestCommonPrefix(input);
console.log(result); // 输出：'fl'答案：
从第一个字符串开始维护前缀，依次与其余字符串比较；比较到首个不同字符时截断前缀，截空即可提前返回。输入 ["flower", "flow", "flight"] 输出 "fl"；空数组或包含空字符串时返回空串。设字符串总长度为 N，时间复杂度 O(N)，额外空间 O(1)。
js
function longestCommonPrefix(strs) {
if (!strs.length) return '';
let prefix = strs[0];
for (let i = 1; i < strs.length && prefix; i++) {
let j = 0;
while (j < prefix.length && j < strs[i].length && prefix[j] === strs[i][j]) j++;
prefix = prefix.slice(0, j);
}
return prefix;
}5. 实现一个支持撤销/重做功能的React Hook，并说明设计思路
答案：
用 past 保存当前状态及其历史，用 future 保存撤销后可重做的状态。每次提交新状态时清空 future；撤销和重做都把当前状态移动到另一栈。状态若是对象，应由调用方保证不可变，或在 set 时做深拷贝，避免历史被原地修改。
jsx
import { useCallback, useState } from 'react';
export function useUndo(initial) {
const [past, setPast] = useState([]);
const [present, setPresent] = useState(initial);
const [future, setFuture] = useState([]);
const set = useCallback(next => {
setPresent(current => {
const value = typeof next === 'function' ? next(current) : next;
setPast(history => [...history, current]);
setFuture([]);
return value;
});
}, []);
const undo = useCallback(() => {
setPast(history => { if (!history.length) return history; const prev = history.at(-1); setPresent(p => { setFuture(f => [p, ...f]); return prev; }); return history.slice(0, -1); });
}, []);
const redo = useCallback(() => {
setFuture(history => { if (!history.length) return history; const next = history[0]; setPresent(p => { setPast(h => [...h, p]); return next; }); return history.slice(1); });
}, []);
return { value: present, set, undo, redo, canUndo: !!past.length, canRedo: !!future.length };
}6. 使用 reduce 实现 map
答案：
map 的关键是按原数组索引执行回调并收集结果，同时跳过稀疏数组的空槽。reduce 的初始累加器应设为新数组，不能修改原数组；回调参数依次为元素、索引和原数组。
js
function mapByReduce(arr, callback, thisArg) {
return arr.reduce((result, value, index, source) => {
result[index] = callback.call(thisArg, value, index, source);
return result;
}, new Array(arr.length));
}时间复杂度 O(n)，结果空间 O(n)。空数组返回同长度空数组；非数组类对象可用 Array.prototype.reduce.call 扩展，但应先处理 null。
7. 实现一个 animate 方法，能够驱动元素从一个位置移动到另一个位置，要求支持动画的开始、暂停和取消功能。
答案：
用 requestAnimationFrame 根据时间比例插值位置，并把控制状态封装成 start、pause、cancel。暂停保留已运行时间，继续时重新记录时间基准；取消停止帧并恢复到起点。
js
function animate(el, from, to, duration) {
let startTime = 0, elapsed = 0, raf = 0, state = 'idle';
const render = x => { el.style.transform = `translateX(${x}px)`; };
const frame = now => {
if (state !== 'running') return;
if (!startTime) startTime = now;
elapsed = Math.min(now - startTime, duration);
render(from + (to - from) * (elapsed / duration));
if (elapsed < duration) raf = requestAnimationFrame(frame);
else state = 'finished';
};
return { start() { if (state === 'finished') return; state = 'running'; startTime = performance.now() - elapsed; raf = requestAnimationFrame(frame); }, pause() { if (state === 'running') { state = 'paused'; cancelAnimationFrame(raf); } }, cancel() { state = 'cancelled'; cancelAnimationFrame(raf); elapsed = 0; startTime = 0; render(from); } };
}时间复杂度 O(f)，额外空间 O(1)；需防止 duration 为 0 时除零。
8. 对英文句子进行逆序处理（例如：how old are you => you are old how）。分析该算法的空间复杂度，并说明如何将空间复杂度降到 O(1)。
答案：
若允许新字符串或数组，先按空格切分，再反转单词并连接，例如 how old are you 得到 you are old how，时间 O(n)，空间 O(n)。要把额外空间降到 O(1)，应在可变字符数组上操作：先整体反转，再逐词反转，最后清理多余空格。JS 字符串不可变，所以只能用字符数组模拟原地处理；严格意义上数组本身仍占 O(n)，O(1) 是相对于可变输入缓冲区的额外空间。
js
function reverseWords(s) {
return s.trim().split(/\s+/).reverse().join(' ');
}9. 不重复最大子串
给定一个字符串，请实现一个函数来找到其中的不重复最大子串。例如，对于字符串"abcabcbb"，不重复最大子串是"abc"，长度为3。
- 请写出实现该功能的代码，并说明其时间复杂度。
- 考虑到性能优化，你认为还有哪些改进空间？请提出优化思路并实现优化后的代码。
答案：
使用滑动窗口维护无重复区间，并记录每个字符最近一次位置。右指针向右扫描，若字符已在窗口内，就把左边界跳到其上次位置之后；每次更新最长长度。abcabcbb 的结果为 abc，长度 3。
js
function longestUnique(s) {
const last = new Map();
let left = 0, bestStart = 0, bestLen = 0;
for (let right = 0; right < s.length; right++) {
if (last.has(s[right])) left = Math.max(left, last.get(s[right]) + 1);
last.set(s[right], right);
if (right - left + 1 > bestLen) { bestLen = right - left + 1; bestStart = left; }
}
return { value: s.slice(bestStart, bestStart + bestLen), length: bestLen };
}时间 O(n)，空间 O(min(n, 字符集大小))；按 Unicode 码点处理时可改用 Array.from。
10. 实现一个双向链表， 具备添加节点、删除节点、在特定位置插入节点、查找节点、遍历等功能
答案：
双向链表节点保存 prev 和 next，链表保存 head、tail 与 size。插入或删除时同时更新相邻节点和首尾指针，空链表、头尾位置及越界位置必须单独处理。查找和遍历为 O(n)，头尾增删为 O(1)，指定索引插入若先定位则为 O(n)。
js
class DoublyList {
constructor() { this.head = this.tail = null; this.size = 0; }
add(value) { const n = { value, prev: this.tail, next: null }; if (this.tail) this.tail.next = n; else this.head = n; this.tail = n; this.size++; }
find(value) { for (let p = this.head; p; p = p.next) if (p.value === value) return p; return null; }
remove(node) { if (!node) return false; if (node.prev) node.prev.next = node.next; else this.head = node.next; if (node.next) node.next.prev = node.prev; else this.tail = node.prev; this.size--; return true; }
insertAt(index, value) { if (index < 0 || index > this.size) throw new RangeError('index'); if (index === this.size) return this.add(value); let p = this.head; for (let i = 0; i < index; i++) p = p.next; const n = { value, prev: p.prev, next: p }; if (p.prev) p.prev.next = n; else this.head = n; p.prev = n; this.size++; }
*values() { for (let p = this.head; p; p = p.next) yield p.value; }
}11. 实现银行卡号每隔四位加一个空格， 例如：6222023100014763381 -->6222 0231 0001 4763 381
答案：
银行卡号应按字符串处理，不能转成 Number，否则长号码可能发生精度丢失。先移除已有空格，再按每四位切分并用空格连接；这样也能保留前导零。示例 6222023100014763381 输出 6222 0231 0001 4763 381。
js
function formatCardNumber(value) {
return String(value).replace(/\s+/g, '').replace(/(.{4})/g, '$1 ').trim();
}时间复杂度 O(n)，额外空间 O(n)。如果还要校验银行卡格式，应另行限制字符只能为数字，避免把任意文本静默格式化。
12. 常见数组排序算法有哪些？
答案：
常见排序包括冒泡、选择、插入、希尔、归并、快速、堆排序，以及非比较的计数、桶排序和基数排序。工程中通常使用内置排序；手写时，快速排序平均 O(n log n)、最坏 O(n²)，归并排序稳定且 O(n log n) 但需 O(n) 额外空间，堆排序稳定为 O(n log n) 且额外空间 O(1)。是否稳定、是否原地、数据是否近乎有序，是选择算法的重要依据。
13. 虚拟 dom 原理是什么，手写一个简单的虚拟 dom 实现
答案：
虚拟 DOM 是用 JS 对象描述真实 DOM 的树结构。状态变化时生成新树，与旧树做差异比较，再把必要的增删改批量应用到真实 DOM，减少直接操作。下面实现元素创建和简单属性、子节点更新；生产框架还会处理 key、事件、文本节点和更精细的 diff。
js
const h = (type, props = {}, ...children) => ({ type, props, children: children.flat() });
function create(v) {
if (v == null || v === false) return document.createTextNode('');
if (typeof v !== 'object') return document.createTextNode(String(v));
const el = document.createElement(v.type);
Object.entries(v.props).forEach(([k, val]) => el.setAttribute(k, val));
v.children.forEach(c => el.appendChild(create(c)));
return el;
}
function patch(parent, oldV, newV, index = 0) {
const oldEl = parent.childNodes[index];
if (oldV == null) parent.appendChild(create(newV));
else if (newV == null) oldEl.remove();
else if (typeof oldV !== typeof newV || (typeof newV === 'object' && oldV.type !== newV.type)) parent.replaceChild(create(newV), oldEl);
else if (typeof newV !== 'object') { if (oldV !== newV) oldEl.nodeValue = String(newV); }
else newV.children.forEach((c, i) => patch(oldEl, oldV.children[i], c, i));
}14. 实现：setObjectValue(obj: object, keys: string[], value: any) 方法， 支持安全设置对象的值
答案：
沿着 keys 逐层创建对象，最后一层赋值。遇到中间属性不存在或不是对象时创建普通对象；若需要支持数组路径，可根据下一段是否为整数创建数组。实现还应拒绝 __proto__、constructor、prototype 等危险键，避免原型污染。
js
function setObjectValue(obj, keys, value) {
if (!obj || !Array.isArray(keys) || !keys.length) throw new TypeError('invalid arguments');
const blocked = new Set(['__proto__', 'constructor', 'prototype']);
let cur = obj;
keys.forEach((key, i) => {
if (blocked.has(key)) throw new Error('unsafe key');
if (i === keys.length - 1) cur[key] = value;
else {
if (!cur[key] || typeof cur[key] !== 'object') cur[key] = /^\d+$/.test(keys[i + 1]) ? [] : {};
cur = cur[key];
}
});
return obj;
}时间复杂度 O(keys.length)，额外空间 O(1)。
15. 手写实现 Promise.allSettled
答案：
allSettled 不因单个 Promise 失败而拒绝，而是为每个输入记录 fulfilled 或 rejected 结果，并按输入顺序返回。用 Promise.resolve 兼容普通值，用索引写结果，计数归零时完成外层 Promise。
js
function allSettled(iterable) {
return new Promise(resolve => {
const list = Array.from(iterable), result = new Array(list.length);
if (!list.length) return resolve(result);
let left = list.length;
list.forEach((item, i) => Promise.resolve(item).then(
value => { result[i] = { status: 'fulfilled', value }; },
reason => { result[i] = { status: 'rejected', reason }; }
).finally(() => { if (--left === 0) resolve(result); }));
});
}时间复杂度 O(n)，结果空间 O(n)；输入迭代器抛错时，生产实现应捕获并拒绝外层 Promise。
16. 如何实现可过期的 localStorage 数据?
答案：
localStorage 只保存字符串且没有过期机制，可以把值和过期时间一起序列化保存。读取时先判断 expiresAt，过期就删除并返回默认值；写入时用当前时间加 TTL。注意 localStorage 可能因容量或隐私模式抛异常，敏感数据也不应直接存储。
js
function setWithExpiry(key, value, ttl) {
localStorage.setItem(key, JSON.stringify({ value, expiresAt: Date.now() + ttl }));
}
function getWithExpiry(key) {
const raw = localStorage.getItem(key);
if (!raw) return null;
try {
const item = JSON.parse(raw);
if (item.expiresAt <= Date.now()) { localStorage.removeItem(key); return null; }
return item.value;
} catch { localStorage.removeItem(key); return null; }
}17. 介绍下深度优先遍历和广度优先遍历，如何实现？
答案：
深度优先遍历（DFS）沿一条分支尽可能深入，再回溯，适合回溯、路径搜索；可用递归或显式栈。广度优先遍历（BFS）按层访问，使用队列，适合求无权图最短路径。图遍历必须维护 visited，否则会因环重复访问。两者对邻接表的时间复杂度都是 O(V+E)，空间复杂度为 O(V)。
js
function dfs(graph, start) {
const seen = new Set(), stack = [start], out = [];
while (stack.length) { const v = stack.pop(); if (seen.has(v)) continue; seen.add(v); out.push(v); for (const n of graph[v] || []) stack.push(n); }
return out;
}
function bfs(graph, start) {
const seen = new Set([start]), queue = [start], out = [];
for (let i = 0; i < queue.length; i++) { const v = queue[i]; out.push(v); for (const n of graph[v] || []) if (!seen.has(n)) { seen.add(n); queue.push(n); } }
return out;
}18. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
- 输入: [0,1,0,3,12]
- 输出: [1,3,12,0,0]
说明:
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
答案：
使用双指针 write 指向下一个非零元素的位置，扫描数组时遇到非零就与 write 位置交换并递增。这样非零元素保持原有相对顺序，所有零自然被移到末尾；输入 [0,1,0,3,12] 原地变为 [1,3,12,0,0]。时间 O(n)，额外空间 O(1)。
js
function moveZeroes(nums) {
let write = 0;
for (let read = 0; read < nums.length; read++) {
if (nums[read] !== 0) {
[nums[write], nums[read]] = [nums[read], nums[write]];
write++;
}
}
return nums;
}19. 实现 (5).add(3).minus(2) 功能
答案：
在 Number.prototype 上增加 add 和 minus 方法，并返回新的数值。示例 (5).add(3).minus(2) 的结果是 6。原生 Number 存在浮点精度问题，例如 0.1 + 0.2，金额场景应使用整数最小单位或专用精度库。
js
Number.prototype.add = function (n) { return this.valueOf() + n; };
Number.prototype.minus = function (n) { return this.valueOf() - n; };
console.log((5).add(3).minus(2)); // 6面试实现可以这样展示链式调用；业务代码一般不建议污染全局原型。
20. 给定两个数组，写一个方法来计算它们的交集？
答案：
若题目要求集合交集且结果去重，可把第一个数组放入 Set，遍历第二个数组命中时加入结果集；若要求保留重复次数，则改用频次表。下面实现无重复交集，例如 [1,2,2,3] 与 [2,2,4] 返回 [2]。平均时间 O(m+n)，空间 O(m+n)。
js
function intersection(a, b) {
const source = new Set(a), result = new Set();
for (const value of b) if (source.has(value)) result.add(value);
return [...result];
}NaN 在 Set 中可正确匹配自身；对象按引用判断，若要按内容比较需先定义键。
21. 请实现一个 add 函数
满足以下功能：
add(1).getValue(); // 1
add(1)(2).getValue(); // 3
add(1)(2)(3).getValue()； // 6
add(1)(2, 3).getValue(); // 6
add(1, 2)(3).getValue(); // 6
add(1, 2, 3).getValue(); // 6答案：
利用闭包保存累计和，并让返回函数既能继续接收参数，又提供 getValue 方法。每次调用都累加所有实参，因此 add(1)(2, 3).getValue() 返回 6。
js
function add(...initial) {
let total = initial.reduce((sum, n) => sum + n, 0);
const next = (...args) => { total += args.reduce((sum, n) => sum + n, 0); return next; };
next.getValue = () => total;
return next;
}闭包让状态在调用链中保持；若要求不可变，可每次返回携带新和的新函数。数字运算仍遵循 JS 的浮点规则。
22. base64 的编码原理是什么？
答案：
Base64 把二进制数据按每 3 个字节（24 位）分成 4 组，每组 6 位，用 64 个字符映射，常用字符集是 A-Z、a-z、0-9、+、/，不足 3 字节时用 = 补位。它是编码而不是加密，任何人都能还原，体积通常增加约三分之一。浏览器可用 btoa/atob，但处理 Unicode 要先转换为 UTF-8 字节，不能直接把中文传给 btoa。
23. 如何做 promise 缓存？上一次调用函数的 promise 没有返回， 那么下一次调用函数依然返回上一个 promise
答案：
把正在执行的 Promise 缓存在闭包变量中；有缓存就直接返回同一个 Promise，没有缓存才发起请求。为避免失败后永久占用，应在 finally 中清除；如果还要缓存成功结果，则需另设结果缓存和过期策略。
js
function promiseCache(fn) {
let pending = null;
return (...args) => {
if (pending) return pending;
pending = Promise.resolve().then(() => fn(...args)).finally(() => { pending = null; });
return pending;
};
}
const cachedFetch = promiseCache(url => fetch(url).then(r => r.json()));这适合所有调用共享同一请求；若参数不同，应使用按参数序列化的 Map。
24. 深度遍历与广度遍历有什么区别？
答案：
深度遍历先走到底再回退，典型实现是递归或栈，空间主要取决于最大深度；广度遍历逐层扩展，典型实现是队列，空间主要取决于最大宽度。DFS 适合回溯和连通性判断，BFS 在无权图中可保证首次到达即为最短边数。邻接表下二者时间复杂度均为 O(V+E)，都要避免重复访问。
25. 如何判断一个单向链表是否是循环链表？
答案：
使用 Floyd 快慢指针：慢指针每次走一步，快指针每次走两步。若存在环，两者最终会在环内相遇；若快指针到达 null，链表无环。空链表也应返回 false。时间复杂度 O(n)，额外空间 O(1)，比用 Set 记录访问节点更节省空间。
js
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}26. 手写实现一个缓存函数 memoize
缓存函数（memoize）是一个优化技术，用于缓存函数的计算结果，以避免重复计算相同的输入。
答案：
memoize 用缓存保存函数输入与输出，再次遇到相同输入直接返回结果。简单版本可用参数序列化作为键；对象参数应定义稳定的键策略，否则按引用缓存更可靠。还需注意函数 this、异常是否缓存，以及缓存无限增长问题。
js
function memoize(fn) {
const cache = new Map();
return function (...args) {
const key = JSON.stringify(args);
if (cache.has(key)) return cache.get(key);
const value = fn.apply(this, args);
cache.set(key, value);
return value;
};
}命中时平均 O(1) 查找，但键序列化本身是 O(k)；生产实现可加入容量上限或 LRU。
27. 手写实现 Object.create
答案：
Object.create(proto) 创建一个空对象，并把其内部 [[Prototype]] 指向 proto，因此对象自身没有继承属性。proto 必须是对象或 null，否则应抛出 TypeError。旧环境可用临时构造函数模拟。
js
function objectCreate(proto) {
if (proto !== null && typeof proto !== 'object' && typeof proto !== 'function') {
throw new TypeError('prototype must be object or null');
}
function Empty() {}
Empty.prototype = proto;
const obj = new Empty();
Empty.prototype = null;
return obj;
}现代 JS 直接使用 Object.create；这里的实现不处理第二个属性描述符参数。
28. 实现数组的flat方法，支持深度层级参数
答案：
递归展开数组：当前深度大于 0 且元素是数组时继续展开，否则把元素放入结果。Infinity 表示全部展开，深度小于等于 0 时返回浅拷贝。下面使用 reduce，会保留数组中的显式 undefined，但与原生 flat 一样会跳过稀疏空槽。
js
function flat(arr, depth = 1) {
return arr.reduce((out, item) => {
if (Array.isArray(item) && depth > 0) out.push(...flat(item, depth === Infinity ? Infinity : depth - 1));
else out.push(item);
return out;
}, []);
}设输出元素总数为 N，时间 O(N)，递归栈空间为 O(d)；极深嵌套可改成显式栈避免调用栈溢出。
29. 斐波拉契数列是什么，用 JS 实现，用尾调优化斐波拉契数列
答案：
斐波那契数列通常定义为 F(0)=0、F(1)=1、F(n)=F(n-1)+F(n-2)。朴素递归会重复计算，时间 O(2^n)；迭代或尾递归可降到 O(n)，空间 O(1)。尾调用是否真正消除栈帧取决于 JS 引擎，主流 Node.js/V8 并不保证尾调用优化，因此大 n 更应使用循环。
js
function fib(n) {
if (!Number.isInteger(n) || n < 0) throw new RangeError('n');
let a = 0, b = 1;
for (let i = 0; i < n; i++) [a, b] = [b, a + b];
return a;
}
function fibTail(n, a = 0, b = 1) {
return n === 0 ? a : fibTail(n - 1, b, a + b);
}30. 实现管道函数
答案：
管道函数把前一个函数的返回值作为后一个函数的输入，按从左到右的顺序组合函数。实现用 reduce 依次调用；空函数列表可返回恒等函数，异步函数则需要 Promise.resolve 版本。
js
const pipe = (...fns) => value => fns.reduce((result, fn) => fn(result), value);
const doubleThenText = pipe(x => x * 2, x => x + 1, String);
console.log(doubleThenText(3)); // "7"
const pipeAsync = (...fns) => value => fns.reduce((p, fn) => p.then(fn), Promise.resolve(value));同步管道调用次数为函数数量，时间复杂度 O(k)，额外空间 O(1)（不计函数闭包）。
31. 实现一个可以用 for...of 遍历的对象
答案：
对象要支持 for...of，必须实现 [Symbol.iterator]，该方法返回一个迭代器；迭代器每次调用 next() 返回 { value, done }。
js
const range = {
start: 1,
end: 3,
*[Symbol.iterator]() {
for (let i = this.start; i <= this.end; i++) yield i;
}
};
console.log([...range]); // [1, 2, 3]生成器会自动实现 next 协议，适合惰性产出，避免一次性创建完整数组；边界应明确是包含还是不包含 end，这里采用闭区间。
32. 实现一个方法，可以对两个数组的维数进行对比
答案：
通常“数组维数”指嵌套层级，而不是元素总数。可递归遍历数组，取所有分支的最大嵌套深度；空数组可约定维数为 1，非数组为 0。比较两个数组时返回深度是否相等，也可以返回各自维数供调用方使用。
js
function dimensions(value) {
if (!Array.isArray(value)) return 0;
if (!value.length) return 1;
return 1 + Math.max(...value.map(dimensions));
}
function sameDimensions(a, b) {
return dimensions(a) === dimensions(b);
}遍历所有嵌套元素的时间复杂度 O(n)，递归空间 O(d)；若要求形状完全相同，还需逐层比较长度而不只是比较最大深度。
33. 请在不使用 setTimeout 的前提下，实现 setInterval
答案：
可以递归使用 setTimeout，每次回调结束后再安排下一次，因此不依赖 setInterval，也能避免任务执行时间超过间隔时的堆积。
js
function setIntervalByTimeout(fn, delay) {
let stopped = false;
const run = () => {
if (stopped) return;
fn();
if (!stopped) timer = setTimeout(run, delay);
};
let timer = setTimeout(run, delay);
return () => { stopped = true; clearTimeout(timer); };
}返回停止函数；delay 小于 0 时按 0 处理。每次只保留一个定时器，时间复杂度为每次回调 O(1)。
34. 基于 axios 实现请求超时后，自动重试
答案：
用 axios 的 timeout 触发超时异常，在循环中按次数重试；每次请求都创建新的 Promise，成功立即返回，达到上限后抛出最后一次错误。
js
async function requestWithRetry(config, retries = 3) {
let lastError;
for (let i = 0; i <= retries; i++) {
try { return await axios({ ...config, timeout: config.timeout ?? 5000 }); }
catch (error) { lastError = error; if (i === retries) throw error; }
}
throw lastError;
}生产中可在两次尝试之间加入指数退避，并区分超时、网络错误和业务状态码；重试次数为 0 时只请求一次。
35. 实现一个函数， 通过 id 来查找 tree 数据结构对应的节点
js
// 数据如下：
const tree = [
{
name: "数据1",
id: 1,
children: [
{
name: "数据2",
id: 2,
children: [
{
name: "数据3",
id: 3,
children:
{
name: "数据4",
id: 4,
children: [],
},
],
},
],
},
],
},
];
function findNodeById(tree, id) {
// ....
}
const res = findNodeById(tree, 3);
// res 的结果为
// {
// name: "数据3",
// id: 3,
// children: [
// {
// name: "数据4",
// id: 4,
// children: [],
// },
// ],
// }答案：
对每个节点做深度优先遍历，命中 id 就立即返回。children 即使是单个对象也统一转成数组，避免题干数据形态不一致导致遍历失败；找不到时返回 undefined。
js
function findNodeById(tree, id) {
const nodes = Array.isArray(tree) ? tree : [tree];
for (const node of nodes) {
if (node.id === id) return node;
if (node.children) {
const found = findNodeById(node.children, id);
if (found) return found;
}
}
return undefined;
}时间复杂度 O(n)，递归栈空间 O(h)，其中 h 是树高。
36. 实现一个 cookies 解析函数，输出结果要求是一个对象
答案：
Cookie 字符串按分号切分，再只在第一个等号处分割键和值；值需要 decodeURIComponent，这样可以保留值中的等号，并忽略空片段。
js
function parseCookies(cookie = '') {
return cookie.split(';').reduce((result, part) => {
const index = part.indexOf('=');
if (index < 0) return result;
const key = part.slice(0, index).trim();
const value = part.slice(index + 1).trim();
if (key) result[key] = decodeURIComponent(value);
return result;
}, {});
}例如 a=1; b=hello%20world 得到 { a: '1', b: 'hello world' }；非法编码可按项目需要捕获异常。
37. 请使用 js 实现 isEmpty 方法
要求传入的参数是空数组、空对象、空字符串、0、undefined、null、空 map、空 set时，返回 true，否则返回 false
js
function isEmpty(value) {
}答案：
先处理 null、undefined 和数值 0，再按类型检查长度或元素数量。普通对象只判断自身可枚举键；非空数组、字符串、Map、Set 或对象都返回 false。
js
function isEmpty(value) {
if (value == null || value === 0 || value === '') return true;
if (Array.isArray(value) || typeof value === 'string') return value.length === 0;
if (value instanceof Map || value instanceof Set) return value.size === 0;
if (typeof value === 'object') return Object.keys(value).length === 0;
return false;
}这里的对象判断不把原型链属性算入自身内容；函数、非零数字和布尔值按非空处理。
38. 实现 isObjectEmpty 方法，判断一个对象是否为空
要求：如果其原型链上有自定义数据或者方法，认为是非空对象。
答案：
判断对象是否为空时，既要检查自身属性，也要检查原型链上的自定义属性或方法。使用 Object.getOwnPropertyNames 可包含不可枚举属性，并逐层排除 Object.prototype；只剩原生对象原型才算空。
js
function isObjectEmpty(value) {
if (value === null || typeof value !== 'object') return true;
for (let current = value; current && current !== Object.prototype; current = Object.getPrototypeOf(current)) {
if (Object.getOwnPropertyNames(current).length) return false;
}
return true;
}若要求把 Object.create(null) 视为空，该实现也满足；自定义原型上任意数据或方法都会返回 false。
39. 请仅使用 css，实现类似 ChatGPT 中，文案一个个输出的打字机效果
答案：
纯 CSS 无法逐字修改 DOM 文本，只能用 steps() 配合固定宽度的裁剪实现逐字符显现；文本必须有不换行的容器，并根据字符数设置动画步数。
html
<span class="typing">你好，欢迎使用</span>
<style>
.typing {
display: inline-block; white-space: nowrap; overflow: hidden;
width: 0; border-right: 2px solid currentColor;
animation: typing 2.8s steps(7, end) forwards, blink .7s step-end infinite;
}
@keyframes typing { to { width: 7em; } }
@keyframes blink { 50% { border-color: transparent; } }
</style>中文等宽假设下示例可用；比例字体或中英文混排时应改用实际宽度/JS 测量。
40. 编写一个vue组件，组件内部使用插槽接收外部内容，v-model双向绑定，实现折叠展开的功能
答案：
Vue 2 中通过 model 把 v-model 映射为 collapsed 属性和 toggle 事件，插槽负责承载外部内容，v-show 保留 DOM 但切换可见性。
vue
<template><section><button @click="toggle">{{ collapsed ? '展开' : '折叠' }}</button><div v-show="!collapsed"><slot /></div></section></template>
<script>
export default {
model: { prop: 'collapsed', event: 'toggle' },
props: { collapsed: { type: Boolean, default: true } },
methods: { toggle() { this.$emit('toggle', !this.collapsed); } }
};
</script>父组件使用 <collapse-panel v-model="isCollapsed">...</collapse-panel>。Vue 3 则改用 modelValue 与 update:modelValue。
41. 实现lodash的set和get方法
答案：
路径先拆成键数组，set 逐层创建缺失对象，get 遇到空值或缺失键立即返回 undefined。下面支持点路径，并避免把 null 当作可继续遍历的对象。
js
function set(obj, path, value) {
const keys = Array.isArray(path) ? path : String(path).split('.');
let cur = obj;
keys.forEach((key, i) => {
if (i === keys.length - 1) cur[key] = value;
else { if (cur[key] == null || typeof cur[key] !== 'object') cur[key] = {}; cur = cur[key]; }
});
return obj;
}
function get(obj, path, defaultValue) {
const keys = Array.isArray(path) ? path : String(path).split('.');
let cur = obj;
for (const key of keys) { if (cur == null) return defaultValue; cur = cur[key]; }
return cur === undefined ? defaultValue : cur;
}路径为空时应由调用方约束；n 个路径片段的时间和额外空间均为 O(n)。
42. 利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3
答案：
连续压缩而不是统计全局频次：扫描相邻字符，记录当前字符的连续次数，段结束时追加“字符+次数”。若压缩结果不更短则返回原串。
js
function compressString(str) {
if (!str) return str;
const out = []; let count = 1;
for (let i = 1; i <= str.length; i++) {
if (str[i] === str[i - 1]) count++;
else { out.push(str[i - 1] + count); count = 1; }
}
const compressed = out.join('');
return compressed.length < str.length ? compressed : str;
}aabcccccaaa 的压缩结果是 a2b1c5a3；时间复杂度 O(n)，空间复杂度 O(n)。
43. 计算出下面数组中的平均时间
js
const arr = ["8:15", "6:35", "11:22"]答案：
先把每个 H:mm 转成从 00:00 起的分钟数求和，再取平均并向下取整，最后还原成小时和两位分钟。给定数组输出 8:44。
js
function averageTime(arr) {
if (!arr.length) return null;
const total = arr.reduce((sum, time) => {
const [h, m] = time.split(':').map(Number);
return sum + h * 60 + m;
}, 0);
const avg = Math.floor(total / arr.length);
return `${Math.floor(avg / 60)}:${String(avg % 60).padStart(2, '0')}`;
}
console.log(averageTime(['8:15', '6:35', '11:22'])); // 8:44跨午夜的时间若表示时刻而非时长，需要先约定日期或使用圆周平均，不能直接按上述算法处理。
44. 请按以下要求实现方法 fn ：遇到退格字符就删除前面的字符，遇到两个退格就删除两个字符
js
// 比较含有退格的字符串，"<-"代表退格键，"<"和"-"均为正常字符
// 输入："a<-b<-", "c<-d<-"，结果：true，解释：都为""
// 输入："<-<-ab<-", "<-<-<-<-a"，结果：true，解释：都为"a"
// 输入："<-<ab<-c", "<<-<a<-<-c"，结果：false，解释："<ac" !== "c"
function fn(str1, str2) {
}答案：
把 '<-' 视为一个退格操作，用栈保存当前有效字符；遇到完整退格就弹出一个字符，栈为空时忽略。最后比较两次处理结果。
js
function fn(str1, str2) {
const build = str => {
const stack = [];
for (let i = 0; i < str.length; i++) {
if (str[i] === '<' && str[i + 1] === '-') { stack.pop(); i++; }
else stack.push(str[i]);
}
return stack.join('');
};
return build(str1) === build(str2);
}例如 a<-b<- 与 c<-d<- 都变成空串；单独的 < 或 - 是普通字符。时间、空间复杂度均为 O(n)。
45. 实现 compose 函数, 类似于 koa 的中间件洋葱模型
js
// 题目需求
let middleware = []
middleware.push((next) => {
console.log(1)
next()
console.log(1.1)
})
middleware.push((next) => {
console.log(2)
next()
console.log(2.1)
})
middleware.push((next) => {
console.log(3)
next()
console.log(3.1)
})
let fn = compose(middleware)
fn()
/*
1
2
3
3.1
2.1
1.1
*/
//实现compose函数
function compose(middlewares) {
}答案：
核心是让每个中间件接收 next，并在调用 next 前后分别执行逻辑；递归返回 Promise 后，调用链自然形成洋葱顺序。
js
function compose(middlewares) {
if (!Array.isArray(middlewares) || middlewares.some(fn => typeof fn !== 'function')) throw new TypeError('invalid middleware');
return function run(context, next) {
let last = -1;
function dispatch(i) {
if (i <= last) return Promise.reject(new Error('next() called twice'));
last = i;
const fn = i === middlewares.length ? next : middlewares[i];
if (!fn) return Promise.resolve();
try { return Promise.resolve(fn(context, () => dispatch(i + 1))); }
catch (error) { return Promise.reject(error); }
}
return dispatch(0);
};
}若中间件是同步 next() 且不等待，示例仍会得到 1、2、3、3.1、2.1、1.1；异步场景应使用 await next()。
46. 有效的变位词
给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。
注意：若 s 和 t中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t互为变位词（字母异位词）。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
示例 3:
输入: s = "a", t = "a"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104sandt仅包含小写字母
js
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isAnagram = function(s, t) {
};答案：
先排除长度不同或两个字符串完全相同的情况，再统计每个小写字母的频次并比较。题目要求字符顺序不能完全相同，所以 isAnagram('a','a') 必须为 false。
js
function isAnagram(s, t) {
if (s.length !== t.length || s === t) return false;
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
count[s.charCodeAt(i) - 97]++;
count[t.charCodeAt(i) - 97]--;
}
return count.every(value => value === 0);
}统计法时间 O(n)、额外空间 O(1)；只适用于题设的小写英文字母范围。
47. 多叉树指定层节点的个数
答案：
按层遍历多叉树，用队列保存当前层节点；每轮先记录队列长度，处理完这一批后计数加一，直到到达目标层。根节点所在层通常记为 0，需和题目约定一致。
js
function countNodesAtLevel(root, level) {
if (!root || level < 0) return 0;
let queue = [root], current = 0;
while (queue.length && current < level) {
const next = [];
for (const node of queue) next.push(...(node.children || []));
queue = next; current++;
}
return current === level ? queue.length : 0;
}只访问目标层之前的节点，时间 O(已访问节点数)，空间为最大层宽 O(w)。
48. 链表中，环的入口节点
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入： head = [3,2,0,-4], pos = 1 输出： 返回索引为 1 的链表节点 解释： 链表中有一个环，其尾部连接到第二个节点。
示例 2：
**输入：**head = [1,2], pos = 0
**输出：**返回索引为 0 的链表节点
**解释：**链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入： head = [1], pos = -1
输出： 返回 null
解释： 链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
进阶： 你是否可以使用 O(1) 空间解决此题？
javascript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
};答案：
用 Floyd 快慢指针且不修改链表：慢指针每次一步，快指针每次两步。两者相遇说明有环；将一个指针放回头节点，然后两者每次一步，再相遇的位置就是环入口。
js
function detectCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next; fast = fast.next.next;
if (slow === fast) {
slow = head;
while (slow !== fast) { slow = slow.next; fast = fast.next; }
return slow;
}
}
return null;
}时间复杂度 O(n)，额外空间 O(1)，空链表或无环时返回 null。
49. 实现一个请求函数：fetchWithRetry，要求会最多自动重试 3 次，任意一次成功就直接返回
答案：
把一次请求封装为 Promise，最多执行初始请求加 3 次重试；任意一次成功立即返回，全部失败则抛出最后一次错误。重试间隔可用指数退避，避免瞬时故障时集中打满服务。
js
async function fetchWithRetry(input, init, retries = 3) {
let error;
for (let attempt = 0; attempt <= retries; attempt++) {
try {
const response = await fetch(input, init);
if (!response.ok) throw new Error(`HTTP ${response.status}`);
return response;
} catch (e) {
error = e;
if (attempt === retries) break;
await new Promise(resolve => setTimeout(resolve, 2 ** attempt * 100));
}
}
throw error;
}实际应用应传入 AbortSignal，并只对可恢复的网络错误或 5xx 重试。
50. 使用 js 实现有序数组原地去重
答案：
有序数组中相同值连续出现，可用快慢双指针原地覆盖：slow 指向下一个待写位置，遍历指针遇到新值就写入。返回去重后的长度，前 slow 项即结果。
js
function removeDuplicates(nums) {
if (nums.length === 0) return 0;
let slow = 1;
for (let fast = 1; fast < nums.length; fast++) {
if (nums[fast] !== nums[slow - 1]) nums[slow++] = nums[fast];
}
nums.length = slow;
return slow;
}例如 [1,1,2,2,3] 变为 [1,2,3]；时间 O(n)，额外空间 O(1)。
51. 请实现一个函数，要求能在页面请求很多时，尽可能快地按照顺序输出返回的结果。
js
const promiseList = [
new Promise((resolve) => {
setTimeout(resolve, 1000)
}),
new Promise((resolve) => {
setTimeout(resolve, 2000)
}),
new Promise((resolve) => {
setTimeout(resolve, 3000)
}),
new Promise((resolve) => {
setTimeout(resolve, 1500)
})
]
fn(promiseList);答案：
需求是并发执行以缩短总耗时，同时按原数组顺序输出结果。Promise.all 正好保持输入顺序，并等待所有 Promise 完成；给定示例会按 1 秒、2 秒、3 秒、1.5 秒对应的数组顺序输出。
js
async function fn(promiseList) {
const results = await Promise.all(promiseList);
for (const result of results) console.log(result);
return results;
}它会并发启动已经创建的 Promise；若需要控制并发，应传入工厂函数并配合队列。任一 Promise reject 时 Promise.all 会立即 reject。
52. 删除链表的一个节点
答案：
若只给出待删除节点而不给头节点，可把后继节点的值和内容复制到当前节点，再跳过后继节点；题目保证删除的不是尾节点。
js
function deleteNode(node) {
if (!node || !node.next) throw new Error('cannot delete tail');
node.val = node.next.val;
node.next = node.next.next;
}该操作只改变局部指针，时间复杂度 O(1)、额外空间 O(1)。若允许传入头节点并删除尾节点，则应从头遍历找到前驱再断开。
53. 实现一个函数, 可以间隔输出
js
function createRepeat(fn, repeat, interval) {}
const fn = createRepeat(console.log, 3, 4);
fn('helloWorld'); // 每4秒输出一次helloWorld, 输出3次答案：
先返回一个可调用函数，调用它时启动定时器；每次输出后累加次数，达到 repeat 就停止。示例中的 interval=4 按秒理解，因此转换为 4000 毫秒；若项目约定毫秒则去掉转换。
js
function createRepeat(fn, repeat, interval) {
return (...args) => {
let count = 0;
const timer = setInterval(() => {
fn(...args);
if (++count >= repeat) clearInterval(timer);
}, interval * 1000);
return () => clearInterval(timer);
};
}repeat <= 0 时可直接不启动定时器；返回的停止函数可取消尚未完成的输出。
54. 两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat" 输出: 2 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入： word1 = "leetcode", word2 = "etco" 输出： 4
提示：
1 <= word1.length, word2.length <= 500word1和word2只包含小写英文字母
js
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
};答案：
设 dp[i][j] 是前 i 个字符和前 j 个字符变相同所需删除数。若末字符相同，直接继承左上角；否则删除 word1 或 word2 的一个字符，取两种方案最小值加一。
js
function minDistance(a, b) {
const dp = Array.from({ length: a.length + 1 }, (_, i) => Array(b.length + 1).fill(0));
for (let i = 0; i <= a.length; i++) dp[i][0] = i;
for (let j = 0; j <= b.length; j++) dp[0][j] = j;
for (let i = 1; i <= a.length; i++) for (let j = 1; j <= b.length; j++)
dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] : Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
return dp[a.length][b.length];
}时间 O(mn)，空间 O(mn)；也可压缩为 O(n)。
55. 数组转树
将下列数组进行转换：
js
const list = [
{id: 1, name: '部门1', pid: 0},
{id: 2, name: '部门1-1', pid: 1},
{id: 3, name: '部门1-2', pid: 1},
{id: 4, name: '部门1-1-1', pid: 2},
{id: 5, name: '部门1-2-1', pid: 3},
{id: 6, name: '部门2', pid: 0},
{id: 7, name: '部门2-1', pid: 6},
{id: 8, name: '部门3', pid: 0},
]期望结果：
js
const listTree = [
{
id: 1,
name: '部门1',
pid: 0,
children: [
{
id: 2,
name: '部门1-1',
pid: 1,
children: [
{
id: 4,
name: '部门1-1-1',
pid: 2,
children: []
}
]
},
{
id: 3,
name: '部门1-2',
pid: 1,
children: [
{
id: 5,
name: '部门1-2-1',
pid: 3,
children: []
}
]
}
]
},
{
id: 6,
name: '部门2',
pid: 0,
children: [
{
id: 7,
name: '部门2-1',
pid: 6,
children: []
}
]
},
{
id: 8,
name: '部门3',
pid: 0,
children: []
}
]答案：
先为每个节点建立副本并初始化 children，再按 pid 建立父节点到子节点的映射，最后取 pid === 0 的节点作为根。这样不依赖输入顺序，也不会修改原数组。
js
function arrayToTree(list, root = 0) {
const nodes = new Map(list.map(item => [item.id, { ...item, children: [] }]));
const result = [];
for (const item of list) {
const node = nodes.get(item.id);
if (item.pid === root) result.push(node);
else nodes.get(item.pid)?.children.push(node);
}
return result;
}时间 O(n)，空间 O(n)；父节点不存在的孤儿节点在此实现中被忽略，可按业务改为报错或提升为根。
56. 两个字符串对比, 得出结论都做了什么操作, 比如插入或者删除
js
pre = 'abcde123'
now = '1abc123'a前面插入了1, c后面删除了de
答案：
可用动态规划求编辑路径，并回溯得到操作：dp[i][j] 表示 pre[0..i) 变成 now[0..j) 的最少编辑次数；相等时继承左上角，否则在插入、删除、替换中取最小。回溯时合并连续操作即可得到题例的“插入 1、删除 de”。
js
function diff(pre, now) {
const dp = Array.from({length: pre.length + 1}, () => Array(now.length + 1).fill(0));
for (let i=0;i<=pre.length;i++) dp[i][0]=i;
for (let j=0;j<=now.length;j++) dp[0][j]=j;
for (let i=1;i<=pre.length;i++) for (let j=1;j<=now.length;j++)
dp[i][j] = pre[i-1]===now[j-1] ? dp[i-1][j-1] : Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
return dp[pre.length][now.length];
}若只需判断变化内容，可沿 DP 矩阵记录并合并相邻同类操作；复杂度 O(mn)。
57. 不定长二维数组的全排列
给定任意二维数组，输出所有的排列组合项。
比如 [['A','B'], ['a','b'], [1, 2]]，输出 ['Aa1','Aa2','Ab1','Ab2','Ba1','Ba2','Bb1','Bb2']
答案：
这是笛卡尔积。递归处理每一列：当前结果分别拼接该列的每个元素，再进入下一列；空二维数组返回空数组，空列会使结果为空。
js
function cartesianProduct(groups) {
if (!groups.length || groups.some(group => group.length === 0)) return [];
const result = [];
const walk = (index, path) => {
if (index === groups.length) { result.push(path.join('')); return; }
for (const value of groups[index]) walk(index + 1, path.concat(String(value)));
};
walk(0, []);
return result;
}
console.log(cartesianProduct([['A','B'],['a','b'],[1,2]]));
// ['Aa1','Aa2','Ab1','Ab2','Ba1','Ba2','Bb1','Bb2']若要保留元素类型，应返回路径数组而不是 join 字符串；结果数量为各列长度之积。
58. 去除字符串中出现次数最少的字符，不改变原字符串的顺序。
实现删除字符串中出现次数最少的字符，若出现次数最少的字符有多个，则把出现次数最少的字符都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。
js
“ababac” —— “ababa”
“aaabbbcceeff” —— “aaabbb”答案：
先统计每个字符在整个字符串中的出现次数，找出最小频次，再过滤掉所有频次等于最小值的字符。一次遍历统计、一次遍历保序输出。
js
function removeLeastFrequent(str) {
const count = new Map();
for (const ch of str) count.set(ch, (count.get(ch) || 0) + 1);
if (!str) return '';
const min = Math.min(...count.values());
return [...str].filter(ch => count.get(ch) !== min).join('');
}
console.log(removeLeastFrequent('ababac')); // ababa
console.log(removeLeastFrequent('aaabbbcceeff')); // aaabbb示例二中 c、e、f 都出现 2 次，全部删除；时间 O(n)，空间 O(k)。
59. 将下面的数组转成树状结构
根据 id 和 parent_id 的对应关系，进行下面的转换。
原始数据：
json
[
{ "id": 12, "parent_id": 1, "name": "朝阳区" },
{ "id": 241, "parent_id": 24, "name": "田林街道" },
{ "id": 31, "parent_id": 3, "name": "广州市" },
{ "id": 13, "parent_id": 1, "name": "昌平区" },
{ "id": 2421, "parent_id": 242, "name": "上海科技绿洲" },
{ "id": 21, "parent_id": 2, "name": "静安区" },
{ "id": 242, "parent_id": 24, "name": "漕河泾街道" },
{ "id": 22, "parent_id": 2, "name": "黄浦区" },
{ "id": 11, "parent_id": 1, "name": "顺义区" },
{ "id": 2, "parent_id": 0, "name": "上海市" },
{ "id": 24, "parent_id": 2, "name": "徐汇区" },
{ "id": 1, "parent_id": 0, "name": "北京市" },
{ "id": 2422, "parent_id": 242, "name": "漕河泾开发区" },
{ "id": 32, "parent_id": 3, "name": "深圳市" },
{ "id": 33, "parent_id": 3, "name": "东莞市" },
{ "id": 3, "parent_id": 0, "name": "广东省" }
]转换后的结构：
json
[{
"id": 2,
"parent_id": 0,
"name": "上海市",
"children": [{
"id": 21,
"parent_id": 2,
"name": "静安区",
"children": []
}, {
"id": 22,
"parent_id": 2,
"name": "黄浦区",
"children": []
}, {
"id": 24,
"parent_id": 2,
"name": "徐汇区",
"children": [{
"id": 241,
"parent_id": 24,
"name": "田林街道",
"children": []
}, {
"id": 242,
"parent_id": 24,
"name": "漕河泾街道",
"children": [{
"id": 2421,
"parent_id": 242,
"name": "上海科技绿洲",
"children": []
}, {
"id": 2422,
"parent_id": 242,
"name": "漕河泾开发区",
"children": []
}]
}]
}]
}, {
"id": 1,
"parent_id": 0,
"name": "北京市",
"children": [{
"id": 12,
"parent_id": 1,
"name": "朝阳区",
"children": []
}, {
"id": 13,
"parent_id": 1,
"name": "昌平区",
"children": []
}, {
"id": 11,
"parent_id": 1,
"name": "顺义区",
"children": []
}]
}, {
"id": 3,
"parent_id": 0,
"name": "广东省",
"children": [{
"id": 31,
"parent_id": 3,
"name": "广州市",
"children": []
}, {
"id": 32,
"parent_id": 3,
"name": "深圳市",
"children": []
}, {
"id": 33,
"parent_id": 3,
"name": "东莞市",
"children": []
}]
}]答案：
先为每条记录创建带空 children 的副本，再按原数组顺序把节点挂到 parent_id 对应的父节点；最后收集 parent_id === 0 的根节点。
js
function toTree(list, root = 0) {
const map = new Map(list.map(item => [item.id, { ...item, children: [] }]));
const roots = [];
for (const item of list) {
const node = map.get(item.id);
if (item.parent_id === root) roots.push(node);
else map.get(item.parent_id)?.children.push(node);
}
return roots;
}该方法对无序输入仍有效，时间和空间复杂度都是 O(n)；父节点缺失时此处忽略该孤儿节点。
60. 实现一个批量请求函数，要求能够限制并发量
答案：
把 URL 按索引分配给最多 maxNum 个 worker；每个 worker 完成后领取下一个任务，并把结果写回原索引，所以并发执行但结果顺序稳定。空数组直接返回空数组。
js
async function multiRequest(urls, maxNum = 1) {
const result = new Array(urls.length); let next = 0;
const worker = async () => {
while (true) {
const index = next++;
if (index >= urls.length) return;
result[index] = await fetch(urls[index]);
}
};
const workers = Array.from({ length: Math.min(Math.max(1, maxNum), urls.length) }, worker);
await Promise.all(workers);
return result;
}默认让失败 reject；若要求收集失败结果，可在 worker 内用 try/catch 存储错误。时间约为总耗时除以并发度，空间 O(n)。
61. 实现一个方法，从某个数值数组中，获取最小正数（非零非负数）的索引值
答案：
线性扫描即可：只接受大于 0 的数，并维护当前最小值和索引；不使用 Math.min(...arr) 可避免大数组展开导致调用栈/参数数量问题。找不到时返回 -1。
js
function findNonZeroMinIndex(arr) {
let min = Infinity, index = -1;
for (let i = 0; i < arr.length; i++) {
if (arr[i] > 0 && arr[i] < min) { min = arr[i]; index = i; }
}
return index;
}重复最小正数时保留首次出现的索引；时间 O(n)，额外空间 O(1)。
62. 树转数组
将以下结构的数据转成数组。
js
const listTree = [
{
id: 1,
name: '部门1',
pid: 0,
children: [
{
id: 2,
name: '部门1-1',
pid: 1,
children: [
{
id: 4,
name: '部门1-1-1',
pid: 2,
children: []
}
]
},
{
id: 3,
name: '部门1-2',
pid: 1,
children: [
{
id: 5,
name: '部门1-2-1',
pid: 3,
children: []
}
]
}
]
},
{
id: 6,
name: '部门2',
pid: 0,
children: [
{
id: 7,
name: '部门2-1',
pid: 6,
children: []
}
]
},
{
id: 8,
name: '部门3',
pid: 0,
children: []
}
]期望结果：
js
const list = [
{id: 1, name: '部门1', pid: 0},
{id: 2, name: '部门1-1', pid: 1},
{id: 3, name: '部门1-2', pid: 1},
{id: 4, name: '部门1-1-1', pid: 2},
{id: 5, name: '部门1-2-1', pid: 3},
{id: 6, name: '部门2', pid: 0},
{id: 7, name: '部门2-1', pid: 6},
{id: 8, name: '部门3', pid: 0},
]答案：
用深度优先遍历按先序展开：先输出当前节点的浅拷贝，再递归处理 children，这样顺序为父节点、子节点、后续兄弟节点；不要删除输入树上的属性。
js
function treeToList(tree, childKey = 'children') {
const result = [];
const visit = nodes => {
for (const node of nodes) {
const { [childKey]: children, ...item } = node;
result.push(item);
if (Array.isArray(children)) visit(children);
}
};
visit(tree);
return result;
}给定示例输出 1、2、3、4、5、6、7、8；时间 O(n)，递归空间 O(h)。
63. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意： 不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入： x = 4
输出： 2
示例 2：
输入： x = 8
输出： 2
解释： 8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
};答案：
平方根满足 mid * mid <= x 的最大整数条件，用二分查找即可。比较时写成 mid <= x / mid，避免 mid * mid 超过 JavaScript 安全范围。
js
function mySqrt(x) {
let left = 1, right = x, answer = 0;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (mid <= x / mid) { answer = mid; left = mid + 1; }
else right = mid - 1;
}
return answer;
}x=0 时循环不执行返回 0，x=8 返回 2；时间 O(log x)，空间 O(1)。
64. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入： head = [3,2,0,-4], pos = 1 输出： true 解释： 链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入： head = [1,2], pos = 0 输出： true 解释： 链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入： head = [1], pos = -1 输出： false 解释： 链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 104] -105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
进阶： 你能用 O(1)（即，常量）内存解决此问题吗？
js
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
};答案：
用 Floyd 算法检测环：慢指针每次走一步，快指针每次走两步。若链表无环，快指针最终到达 null；若有环，两指针必在环内相遇。
js
function hasCycle(head) {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next; fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}只比较节点引用而不是值，避免重复值造成误判；时间复杂度 O(n)，额外空间 O(1)，不修改原链表。
65. 找出数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3]
输出： 2 或 3
限制：
2 <= n <= 100000
js
/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
};答案：
利用 Set 记录已经出现过的数字，遍历时若再次命中即可返回。题目保证数字在 0 到 n-1 之间，但 Set 方案不依赖额外下标修改，时间复杂度 O(n)，空间复杂度 O(n)。\n\njs\nfunction findRepeatNumber(nums) {\n const seen = new Set();\n for (const num of nums) {\n if (seen.has(num)) return num;\n seen.add(num);\n }\n return -1;\n}\n
66. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出： 3
解释： 节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入： root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出： 5
解释： 节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入： root = [1,2], p = 1, q = 2
输出： 1
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
js
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
};答案：
递归返回当前子树中找到的 p 或 q；空节点返回 null，当前节点等于任一目标时直接返回当前节点。若左右子树都返回非空，当前节点就是最近公共祖先，否则返回非空的一侧。题目保证 p、q 存在。时间 O(n)，递归栈空间 O(h)。\n\njs\nfunction lowestCommonAncestor(root, p, q) {\n if (!root || root === p || root === q) return root;\n const left = lowestCommonAncestor(root.left, p, q);\n const right = lowestCommonAncestor(root.right, p, q);\n return left && right ? root : (left || right);\n}\n
67. 实现一个将多维数组展示的方法
答案：
可用递归按深度优先遍历：遇到普通元素就加入结果，遇到数组就继续展开，因此不依赖已知嵌套层数，也不会把字符串等非数组值误拆。结果顺序与原数组一致，时间复杂度 O(n)，n 为所有元素数量，额外空间为递归栈和结果数组。\n\njs\nfunction flatten(arr) {\n const result = [];\n for (const item of arr) {\n if (Array.isArray(item)) result.push(...flatten(item));\n else result.push(item);\n }\n return result;\n}\n
68. 使用正则表达式实现以下需求：筛选出数组中只包含大小写字母的字符串，并将结果转换成大写
答案：
用锚点保证整个字符串都参与匹配：^[a-zA-Z]+$ 只允许一个或多个英文字母，空字符串也会被排除。先 filter 筛选，再 map 转大写；例如输入 ['Abc','DeF','123','_ghI']，输出 ['ABC','DEF']。\n\njs\nfunction onlyLettersToUpper(arr) {\n return arr.filter(s => /^[a-zA-Z]+$/.test(s))\n .map(s => s.toUpperCase());\n}\n
69. 实现一个等待函数，支持让 async 函数在执行时暂停一段时间，函数的入参为暂停的时间
答案：
等待函数返回一个在指定毫秒后完成的 Promise。它不会阻塞线程，async 函数通过 await 暂停自身，定时器完成后才继续执行。时间复杂度 O(1)，需要注意负数延时会按定时器环境规则近似立即执行。\n\njs\nfunction wait(ms) {\n return new Promise(resolve => setTimeout(resolve, Math.max(0, ms)));\n}\n\nasync function run() {\n console.log('start');\n await wait(1000);\n console.log('end');\n}\n
70. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
**输入：**root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
**输入：**root = [1] 输出：[[1]]
示例 3：
**输入：**root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
};答案：
层序遍历使用队列实现广度优先搜索。每轮先记录当前队列长度，只处理这一层的节点，再把它们的左右子节点入队，这样可自然分组。空树返回空数组。时间复杂度 O(n)，队列和结果空间 O(n)。\n\njs\nfunction levelOrder(root) {\n if (!root) return [];\n const result = [], queue = [root];\n let head = 0;\n while (head < queue.length) {\n const size = queue.length - head, level = [];\n for (let i = 0; i < size; i++) {\n const node = queue[head++];\n level.push(node.val);\n if (node.left) queue.push(node.left);\n if (node.right) queue.push(node.right);\n }\n result.push(level);\n }\n return result;\n}\n
71. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
js
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
};答案：
异或满足交换律和结合律，且 x ^ x = 0、x ^ 0 = x。把数组所有元素异或，成对出现的数字会相互抵消，最后只剩唯一元素。时间复杂度 O(n)，额外空间 O(1)，适用于题目规定的恰有一个单次元素、其余出现两次。\n\njs\nfunction singleNumber(nums) {\n let result = 0;\n for (const num of nums) result ^= num;\n return result;\n}\n
72. 如何实现一个轮播图组件？
答案：
组件至少应包含视口、轨道、当前索引、上一张/下一张按钮和指示器。轨道用 transform 配合 transition 移动；自动播放用可清理的定时器，切换时统一处理边界，并在鼠标悬停、页面不可见或手动操作时暂停/重置。图片应有 alt，按钮需支持键盘和无障碍标签。核心逻辑如下：\n\njs\nfunction createCarousel(track, count, interval = 3000) {\n let index = 0, timer;\n const render = () => { track.style.transform = `translateX(-${index * 100}%)`; };\n const go = step => { index = (index + step + count) % count; render(); restart(); };\n const restart = () => { clearInterval(timer); timer = setInterval(() => go(1), interval); };\n restart();\n return { next: () => go(1), prev: () => go(-1), destroy: () => clearInterval(timer) };\n}\n
73. 开发的过程中你用到过哪些设计模式？
答案：
前端常用观察者模式处理事件总线、状态订阅和响应式更新；策略模式把不同校验、排序或请求策略封装并可替换；工厂模式统一创建不同类型对象；单例模式适合全局配置或缓存，但要控制隐式依赖；装饰器模式用于在不改主体代码的情况下增强能力，例如埋点、缓存和权限检查。选择模式应以降低耦合、提升可测试性为目标，避免为模式而模式。
74. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入： root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出： true
解释： 等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入： root = [1,2,3], targetSum = 5
输出： false
解释： 树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入： root = [], targetSum = 0
输出： false
解释： 由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function(root, targetSum) {
};答案：
递归传递剩余目标和。只有当前节点是叶子节点时，才判断 targetSum === node.val；非叶节点即使数值相等也不能提前返回。空树返回 false。每个节点访问一次，时间 O(n)，递归栈空间 O(h)。\n\njs\nfunction hasPathSum(root, targetSum) {\n if (!root) return false;\n if (!root.left && !root.right) return targetSum === root.val;\n const rest = targetSum - root.val;\n return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);\n}\n
75. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入： word1 = "horse", word2 = "ros"
输出： 3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')示例 2：
输入： word1 = "intention", word2 = "execution"
输出： 5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成
js
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
var minDistance = function(word1, word2) {
};答案：
设 dp[i][j] 为 word1 前 i 个字符转换成 word2 前 j 个字符的最少操作数。相等时取 dp[i-1][j-1]，不等时在插入、删除、替换中取最小值加一。初始化空串转换需要插入或删除对应长度。时间 O(mn)，空间可压缩为 O(n)。\n\njs\nfunction minDistance(a, b) {\n const dp = Array.from({length: a.length + 1}, (_, i) => i);\n for (let j = 1; j <= b.length; j++) {\n let diagonal = dp[0]; dp[0] = j;\n for (let i = 1; i <= a.length; i++) {\n const old = dp[i];\n dp[i] = a[i - 1] === b[j - 1] ? diagonal : 1 + Math.min(dp[i], dp[i - 1], diagonal);\n diagonal = old;\n }\n }\n return dp[a.length];\n}\n
76. 数组中的第 k 大的数字
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
提示：
1 <= k <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4
js
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
};答案：
可用快速选择：第 k 大等价于升序下标 n-k，每次按随机枢轴分区，只递归包含目标下标的一侧，平均时间 O(n)，额外空间平均 O(log n)，原地修改数组；最坏时间 O(n²)。若追求实现简单可排序后取值，但复杂度为 O(n log n)。\n\njs\nfunction findKthLargest(nums, k) {\n const target = nums.length - k;\n function select(left, right) {\n const pivot = nums[right]; let p = left;\n for (let i = left; i < right; i++) if (nums[i] < pivot) [nums[i], nums[p++]] = [nums[p], nums[i]];\n [nums[p], nums[right]] = [nums[right], nums[p]];\n if (p === target) return nums[p];\n return p < target ? select(p + 1, right) : select(left, p - 1);\n }\n return select(0, nums.length - 1);\n}\n
77. 怎么实现洗牌算法？
洗牌算法是将原来的数组进行打散，使原数组的某个数在打散后的数组中的每个位置上等概率的出现，即为乱序算法。
请使用 js 实现一个洗牌算法。
答案：
使用 Fisher-Yates 洗牌，从数组末尾向前遍历，在 [0, i] 中均匀随机选一个位置与 i 交换。每个排列得到的概率相同；不要使用 sort(() => Math.random() - 0.5)，它分布不均匀且复杂度、稳定性都不理想。原地时间 O(n)，额外空间 O(1)。\n\njs\nfunction shuffle(arr) {\n for (let i = arr.length - 1; i > 0; i--) {\n const j = Math.floor(Math.random() * (i + 1));\n [arr[i], arr[j]] = [arr[j], arr[i]];\n }\n return arr;\n}\n
78. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入： nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出： [1,2,2,3,5,6]
解释： 需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入： nums1 = [1], m = 1, nums2 = [], n = 0
输出： [1]
解释： 需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
**输入：**nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] **解释：**需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109
**进阶：**你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
js
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
};答案：
从两个数组的有效区间末尾开始比较，把较大值写入 nums1 的末尾。倒序写入不会覆盖 nums1 尚未处理的前缀；若 nums1 已用完，继续复制 nums2 即可。时间 O(m+n)，额外空间 O(1)，直接修改 nums1。\n\njs\nfunction merge(nums1, m, nums2, n) {\n let i = m - 1, j = n - 1, write = m + n - 1;\n while (j >= 0) {\n if (i >= 0 && nums1[i] > nums2[j]) nums1[write--] = nums1[i--];\n else nums1[write--] = nums2[j--];\n }\n}\n
79. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
示例 1：
输入： s = "()"
输出： true
示例 2：
输入： s = "()[]{}"
输出： true
示例 3：
输入： s = "(]"
输出： false
示例 4：
输入： s = "([)]"
输出： false
示例 5：
输入： s = "{[]}"
输出： true
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
js
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
};答案：
括号匹配具有后进先出特征，因此用栈保存左括号。遇到右括号时检查栈顶是否为对应左括号，不匹配或栈为空立即返回 false；遍历结束后栈必须为空。时间 O(n)，空间 O(n)。\n\njs\nfunction isValid(s) {\n const pairs = {')': '(', ']': '[', '}': '{'};\n const stack = [];\n for (const ch of s) {\n if (ch in pairs) {\n if (stack.pop() !== pairs[ch]) return false;\n } else stack.push(ch);\n }\n return stack.length === 0;\n}\n
80. 二叉树中和为某一值的路径
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入： root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出： [[5,4,11,2],[5,8,4,5]]
示例 2：
输入： root = [1,2,3], targetSum = 5 输出： []
示例 3：
输入： root = [1,2], targetSum = 0 输出： []
提示：
- 树中节点总数在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} target
* @return {number[][]}
*/
var pathSum = function(root, target) {
};答案：
深度优先搜索维护当前路径和数组。进入节点就加入路径并扣除节点值，只有到达叶子且剩余目标等于节点值时复制路径到结果；递归返回前弹出节点，保证兄弟分支互不污染。时间 O(n+h·r)，其中 r 为结果路径数，空间 O(h) 不计结果。\n\njs\nfunction pathSum(root, target) {\n const result = [], path = [];\n function dfs(node, rest) {\n if (!node) return;\n path.push(node.val);\n if (!node.left && !node.right && rest === node.val) result.push([...path]);\n dfs(node.left, rest - node.val);\n dfs(node.right, rest - node.val);\n path.pop();\n }\n dfs(root, target);\n return result;\n}\n
81. 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入： root = [3,9,20,null,null,15,7]
输出： [[3],[9,20],[15,7]]
示例 2：
输入： root = [1]
输出： [[1]]
示例 3：
输入： root = []
输出： []
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
};答案：
这是标准的广度优先遍历：队列保存待处理节点，每轮固定处理当前队列中的节点数并形成一层。用下标代替 shift() 可避免反复移动数组元素。空树返回 []，时间 O(n)，空间 O(n)。\n\njs\nfunction levelOrder(root) {\n if (!root) return [];\n const result = [], queue = [root]; let head = 0;\n while (head < queue.length) {\n const end = queue.length, level = [];\n while (head < end) {\n const node = queue[head++]; level.push(node.val);\n if (node.left) queue.push(node.left);\n if (node.right) queue.push(node.right);\n }\n result.push(level);\n }\n return result;\n}\n
82. 实现一个类，其实例可以链式调用，它有一个 sleep 方法，可以 sleep 一段时间后再后续调用
js
const boy = new PlayBoy('Tom')
boy.sayHi().sleep(1000).play('王者').sleep(2000).play('跳一跳')
// 输出
// 大家好我是Tom
// 1s 之后
// 我在玩王者
// 2s 之后
// 我在玩跳一跳答案：
链式调用要求每个同步方法返回实例；sleep 不能阻塞 JavaScript 线程，所以用 Promise 队列串行执行任务，并让后续方法继续追加任务。最终调用 run() 才开始执行，输出顺序和延时可靠。\n\njs\nclass PlayBoy {\n constructor(name) { this.name = name; this.queue = Promise.resolve(); }\n task(fn) { this.queue = this.queue.then(fn); return this; }\n sayHi() { return this.task(() => console.log(`大家好我是${this.name}`)); }\n sleep(ms) { return this.task(() => new Promise(r => setTimeout(() => { console.log(`${ms / 1000}s 之后`); r(); }, ms))); }\n play(name) { return this.task(() => console.log(`我在玩${name}`)); }\n}\n
83. 用es5如何实现 let 和 const ？
答案：
ES5 无法完全复刻 let/const 的词法环境和引擎级 TDZ，只能用函数作用域、闭包和属性描述符近似。let 可用 IIFE 为每次循环创建独立作用域；const 可用闭包隐藏变量并只暴露读取接口，或用 Object.defineProperty 禁止重新赋值，但不能阻止对象内容被修改。\n\njs\nfunction constLike(value) {\n var initialized = true, current = value;\n return { get: function () { return current; }, set: function () { if (initialized) throw new TypeError('Assignment'); } };\n}\nvar answer = constLike(1);\nconsole.log(answer.get());\n
84. 字符串相加
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
示例 1：
输入： num1 = "11", num2 = "123"
输出： "134"
示例 2：
输入： num1 = "456", num2 = "77"
输出： "533"
示例 3：
输入： num1 = "0", num2 = "0"
输出： "0"
提示：
1 <= num1.length, num2.length <= 104num1和num2都只包含数字0-9num1和num2都不包含任何前导零
js
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var addStrings = function(num1, num2) {
};答案：
从两个字符串末尾向前逐位相加，维护进位。字符转数字只需减去字符 0 的编码或使用 charCodeAt，不把整个输入转成 Number，因此支持超长数字。最后反转结果；循环结束后若仍有进位要补上。时间 O(max(m,n))，空间 O(max(m,n))。\n\njs\nfunction addStrings(a, b) {\n let i = a.length - 1, j = b.length - 1, carry = 0, out = [];\n while (i >= 0 || j >= 0 || carry) {\n const sum = (i >= 0 ? a.charCodeAt(i--) - 48 : 0) + (j >= 0 ? b.charCodeAt(j--) - 48 : 0) + carry;\n out.push(String(sum % 10)); carry = Math.floor(sum / 10);\n }\n return out.reverse().join('');\n}\n
85. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入： ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]] 输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入： ["MedianFinder","addNum","findMedian","addNum","findMedian"] [[],[2],[],[3],[]] 输出：[null,null,2.00000,null,2.50000]
限制：
- 最多会对
addNum、findMedian进行50000次调用。
js
/**
* initialize your data structure here.
*/
var MedianFinder = function() {
};
/**
* @param {number} num
* @return {void}
*/
MedianFinder.prototype.addNum = function(num) {
};
/**
* @return {number}
*/
MedianFinder.prototype.findMedian = function() {
};
/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/答案：
用两个堆维护平衡：大顶堆 low 保存较小的一半，小顶堆 high 保存较大的一半，并保证 low.length === high.length 或多一个。插入后先放入 low，再把最大值移到 high，必要时把 high 最小值移回 low；中位数就是 low 堆顶，或两堆堆顶平均值。每次添加 O(log n)，查询 O(1)，空间 O(n)。\n\njs\nclass Heap {\n constructor(cmp) { this.a = []; this.cmp = cmp; }\n get size() { return this.a.length; }\n peek() { return this.a[0]; }\n push(x) { this.a.push(x); this.up(this.size - 1); }\n pop() { const top = this.a[0], last = this.a.pop(); if (this.size) { this.a[0] = last; this.down(0); } return top; }\n up(i) { while (i) { const p = (i - 1) >> 1; if (this.cmp(this.a[p], this.a[i])) break; [this.a[p], this.a[i]] = [this.a[i], this.a[p]]; i = p; } }\n down(i) { for (;;) { let j = i, l = i * 2 + 1, r = l + 1; if (l < this.size && !this.cmp(this.a[j], this.a[l])) j = l; if (r < this.size && !this.cmp(this.a[j], this.a[r])) j = r; if (j === i) return; [this.a[i], this.a[j]] = [this.a[j], this.a[i]]; i = j; } }\n}\nclass MedianFinder {\n constructor() { this.low = new Heap((a,b) => a >= b); this.high = new Heap((a,b) => a <= b); }\n addNum(x) { this.low.push(x); this.high.push(this.low.pop()); if (this.high.size > this.low.size) this.low.push(this.high.pop()); }\n findMedian() { return this.low.size > this.high.size ? this.low.peek() : (this.low.peek() + this.high.peek()) / 2; }\n}\n
86. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入： arr = [3,2,1], k = 2
输出： [1,2] 或者 [2,1]
示例 2：
输入： arr = [0,1,2,1], k = 1
输出： [0]
限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000
js
/**
* @param {number[]} arr
* @param {number} k
* @return {number[]}
*/
var getLeastNumbers = function(arr, k) {
};答案：
题目只要求取最小 k 个数，不要求保持原数组，因此可直接排序后截取，时间 O(n log n)，空间取决于排序实现。k 为 0 时返回空数组；若追求线性平均时间可使用快速选择。\n\njs\nfunction getLeastNumbers(arr, k) {\n if (k === 0) return [];\n return [...arr].sort((a, b) => a - b).slice(0, k);\n}\n
87. 实现 Promise.race 函数
答案：
Promise.race 接收可迭代对象，返回一个新 Promise；其中任一输入先 fulfilled 就以其值兑现，任一输入先 rejected 就以其原因拒绝。用 Promise.resolve 统一处理普通值和 thenable，空数组返回一个永远 pending 的 Promise。\n\njs\nfunction promiseRace(iterable) {\n return new Promise((resolve, reject) => {\n for (const item of iterable) Promise.resolve(item).then(resolve, reject);\n });\n}\n
88. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出： true
示例 2：
输入： matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出： false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
js
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
};答案：
把矩阵视为长度为 m*n 的有序一维数组，虚拟下标 mid 对应行 Math.floor(mid / n)、列 mid % n，对其做二分查找。空矩阵直接返回 false。时间 O(log(mn))，空间 O(1)。\n\njs\nfunction searchMatrix(matrix, target) {\n if (!matrix.length || !matrix[0].length) return false;\n const n = matrix[0].length; let left = 0, right = matrix.length * n - 1;\n while (left <= right) {\n const mid = left + ((right - left) >> 1);\n const value = matrix[Math.floor(mid / n)][mid % n];\n if (value === target) return true;\n if (value < target) left = mid + 1; else right = mid - 1;\n }\n return false;\n}\n
89. 删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入： head = [1,1,2] 输出： [1,2]
示例 2：
输入： head = [1,1,2,3,3] 输出： [1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
};答案：
链表已按升序排列，所以重复节点一定相邻。用指针从头扫描：若当前节点与下一个节点值相同，就跳过下一个节点；否则向后移动。这样原地修改链表，时间 O(n)，空间 O(1)，空链表直接返回 null。\n\njs\nfunction deleteDuplicates(head) {\n let node = head;\n while (node && node.next) {\n if (node.val === node.next.val) node.next = node.next.next;\n else node = node.next;\n }\n return head;\n}\n
90. 实现lodash中的get方法
使用 lodash 中的 get 函数可避免长链的 key 时获取不到属性而出现问题，此时进行异常避免时及其服务，如 o.a && o.a.b && o.a.b.c && o.a.b.c.d
实现类似 lodash.get ，有以下测试用例:
var object = { 'a': [{ 'b': { 'c': 3 } }] };
get(object, 'a[0].b.c');
// => 3
get(object, ['a', '0', 'b', 'c']);
// => 3
get(object, 'a.b.c', 'default');
// => 'default'答案：
先把路径字符串按点号和方括号解析成 key 数组，再逐层读取对象。读取过程中遇到 null 或 undefined 就返回默认值；若最终值本身是 undefined，也应返回默认值。要区分 key 为 0 等合法值，不能用简单的真假判断。\n\njs\nfunction get(object, path, defaultValue) {\n const keys = Array.isArray(path) ? path : String(path).replace(/\[([^\]]+)\]/g, '.$1').split('.').filter(Boolean);\n let value = object;\n for (const key of keys) {\n if (value == null) return defaultValue;\n value = value[key];\n }\n return value === undefined ? defaultValue : value;\n}\n
91. 最大子序和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入： nums = [-2,1,-3,4,-1,2,1,-5,4] 输出： 6 解释： 连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入： nums = [1] 输出： 1
示例 3：
输入： nums = [5,4,-1,7,8] 输出： 23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
js
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
};答案：
使用 Kadane 算法。current 表示必须以当前位置结尾的最大子数组和：若前一段和为负，就从当前元素重新开始；否则接在前面。best 保存全局最大值，因此全为负数时也能返回最大的那个负数。时间 O(n)，空间 O(1)。\n\njs\nfunction maxSubArray(nums) {\n let current = nums[0], best = nums[0];\n for (let i = 1; i < nums.length; i++) {\n current = Math.max(nums[i], current + nums[i]);\n best = Math.max(best, current);\n }\n return best;\n}\n
92. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入： root = [4,2,7,1,3,6,9]
输出： [4,7,2,9,6,3,1]
示例 2：
输入： root = [2,1,3]
输出： [2,3,1]
示例 3：
输入： root = []
输出： []
提示：
- 树中节点数目范围在
[0, 100]内 -100 <= Node.val <= 100
js
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
};答案：
递归翻转每个节点的左右子树：先处理左右子树，再交换引用；空节点直接返回。交换操作是原地的，每个节点只访问一次，时间复杂度 O(n)，递归栈空间 O(h)，链状树最坏为 O(n)。\n\njs\nfunction invertTree(root) {\n if (!root) return null;\n const left = invertTree(root.left);\n root.left = invertTree(root.right);\n root.right = left;\n return root;\n}\n
93. 实现斐波那契数列
斐波那契数，指的是这样一个数列：1、1、2、3、5、8、13、21、……
在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*），用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。
答案：
按题目数学定义取 F(0)=0、F(1)=1，用迭代只保留连续两个状态，避免普通递归的指数级重复计算和深递归。时间复杂度 O(n)，空间 O(1)；n 为 0 时直接返回 0。\n\njs\nfunction fib(n) {\n let prev = 0, curr = 1;\n for (let i = 0; i < n; i++) [prev, curr] = [curr, prev + curr];\n return prev;\n}\n
94. 请按以下要求实现 compose 方法
js
var list = [['热', '冷', '冰'], ['大', '中', '小'], ['重辣', '微辣'], ['重麻', '微麻']];
// 输出所有维度的组合，如 [['热', '冷''], ['大', '中']] => 热+大，热+中，冷+大，冷+中
function compose(list) {
console.log('hello world');
}
compose(list);答案：
这是多个维度的笛卡尔积。维护已经生成的组合，依次与下一维的每个选项拼接；空输入返回空数组，某一维为空时结果也为空。下面返回题目示例所需的带加号字符串；若要数组组合，直接返回 result。设最终组合数为 P，时间 O(P·d)，空间 O(P·d)。\n\njs\nfunction compose(list) {\n let result = [[]];\n for (const options of list) {\n const next = [];\n for (const prefix of result) for (const value of options) next.push([...prefix, value]);\n result = next;\n }\n return result.map(items => items.join('+'));\n}\n
95. 时钟指针的夹角
给你两个数 hour 和 minutes 。请你返回在时钟上，由给定时间的时针和分针组成的较小角的角度（60 单位制）。
示例 1：
输入： hour = 12, minutes = 30
输出： 165
示例 2：
输入： hour = 3, minutes = 30
输出； 75
示例 3：
输入： hour = 3, minutes = 15
输出： 7.5
示例 4：
输入： hour = 4, minutes = 50
输出： 155
示例 5：
输入： hour = 12, minutes = 0
输出： 0
提示：
1 <= hour <= 120 <= minutes <= 59- 与标准答案误差在
10^-5以内的结果都被视为正确结果。
js
/**
* @param {number} hour
* @param {number} minutes
* @return {number}
*/
var angleClock = function(hour, minutes) {
};答案：
分针每分钟转 6 度，时针每小时转 30 度且会随分钟连续移动，因此时针角度为 (hour % 12 + minutes / 60) * 30，分针角度为 minutes * 6。两角差取绝对值，再与其补角 360-diff 取最小值。时间和空间都是 O(1)。\n\njs\nfunction angleClock(hour, minutes) {\n const hourAngle = (hour % 12 + minutes / 60) * 30;\n const minuteAngle = minutes * 6;\n const diff = Math.abs(hourAngle - minuteAngle);\n return Math.min(diff, 360 - diff);\n}\n
96. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入： s = "abc"
输出： 3
解释： 三个回文子串: "a", "b", "c"
示例 2：
输入： s = "aaa"
输出： 6
解释： 6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s由小写英文字母组成
js
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
};答案：
枚举每个可能的回文中心并向两边扩展，中心既包括单字符，也包括相邻字符之间的位置。每成功扩展一次就找到一个子串，因此重复字符在不同位置会分别计数。时间复杂度 O(n²)，额外空间 O(1)。\n\njs\nfunction countSubstrings(s) {\n let count = 0;\n function expand(left, right) {\n while (left >= 0 && right < s.length && s[left] === s[right]) {\n count++; left--; right++;\n }\n }\n for (let i = 0; i < s.length; i++) {\n expand(i, i);\n expand(i, i + 1);\n }\n return count;\n}\n
97. 爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
示例 1：
输入: piles = [3,6,7,11], H = 8
输出: 4
示例 2：
输入: piles = [30,11,23,4,20], H = 5
输出: 30
示例 3：
输入: piles = [30,11,23,4,20], H = 6
输出: 23
提示：
1 <= piles.length <= 10^4piles.length <= H <= 10^91 <= piles[i] <= 10^9
js
/**
* @param {number[]} piles
* @param {number} h
* @return {number}
*/
var minEatingSpeed = function(piles, h) {
};答案：
用二分查找最小可行速度。速度为 k 时，一堆香蕉需要 Math.ceil(p / k) 小时，总小时数不超过 H 即可行；可行性随 k 增大单调成立。
js
function minEatingSpeed(piles, h) {
let lo = 1, hi = Math.max(...piles);
while (lo < hi) {
const k = Math.floor((lo + hi) / 2);
let hours = 0;
for (const p of piles) {
hours += Math.ceil(p / k);
if (hours > h) break;
}
if (hours <= h) hi = k;
else lo = k + 1;
}
return lo;
}时间复杂度 O(n log W)，空间复杂度 O(1)，W 为最大堆；k 从 1 开始避免除零。
98. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入： n = 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： n = 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
提示：
1 <= n <= 45
js
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
};答案：
设 dp[i] 为到达第 i 阶的方法数。最后一步只能从 i-1 走 1 阶或从 i-2 走 2 阶，因此 dp[i] = dp[i-1] + dp[i-2]，边界为 dp[0]=1、dp[1]=1。只保留最近两项即可。
js
function climbStairs(n) {
let prev = 1, cur = 1;
for (let i = 2; i <= n; i++) [prev, cur] = [cur, prev + cur];
return cur;
}时间复杂度 O(n)，空间复杂度 O(1)；题目范围内结果可用 JavaScript 安全整数表示。
99. 使用Promise实现红绿灯交替重复亮
红灯3秒亮一次，绿灯2秒亮一次，黄灯1秒亮一次；如何让三个灯不断交替重复亮灯？
要求：用Promise实现
三个亮灯函数已经存在：
js
function red() {
console.log('red');
}
function green() {
console.log('green');
}
function yellow() {
console.log('yellow');
}答案：
用一个 Promise 表示“亮灯并等待本灯时长”，每次链式执行红、绿、黄，最后递归开启下一轮。递归发生在异步回调之后，不会同步耗尽调用栈。
js
const waitLight = (fn, ms) => new Promise(resolve => {
fn();
setTimeout(resolve, ms);
});
function loop() {
return waitLight(red, 3000)
.then(() => waitLight(green, 2000))
.then(() => waitLight(yellow, 1000))
.then(loop);
}
loop();输出顺序始终是 red、green、yellow，分别间隔 3、2、1 秒；实际项目可保存定时器并在销毁时取消，避免无限任务泄漏。
100. Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I示例 3：
输入：s = "A", numRows = 1
输出："A"提示：
- 1 <= s.length <= 1000
s由英文字母（小写和大写）、',' 和 '.' 组成- 1 <= numRows <= 1000
答案：
逐字符模拟方向。维护当前行 row 和方向 step，到达首行或末行时反向，最后按行拼接。numRows === 1 或行数不少于字符串长度时无需排布，直接返回原串。
js
function convert(s, numRows) {
if (numRows <= 1 || numRows >= s.length) return s;
const rows = Array.from({length: numRows}, () => []);
let row = 0, step = 1;
for (const ch of s) {
rows[row].push(ch);
if (row === 0) step = 1;
else if (row === numRows - 1) step = -1;
row += step;
}
return rows.map(r => r.join('')).join('');
}时间复杂度 O(n)，空间复杂度 O(n)。
101. a == 1 && a == 2 && a == 3 可能为 true 吗？
答案：
可以，但 a 必须是对象。宽松相等比较对象与数字时，会先执行对象到原始值的转换；让 valueOf 每次返回递增数字即可。
js
const a = { value: 1, valueOf() { return this.value++; } };
console.log(a == 1 && a == 2 && a == 3); // true这是利用了有副作用的类型转换，=== 不会触发这种数值转换，因此不能用同样方式成立；实际代码不应依赖该行为。
102. 如何查找一篇英文文章中出现频率最高的单词？
答案：
先统一转小写，再用正则提取英文单词，用 Map 统计频次并记录最大值。空字符串或没有单词时返回空结果；同频时下面实现保留首次出现的单词。
js
function findMostWord(article) {
const words = article.toLowerCase().match(/[a-z]+/g) || [];
const count = new Map();
let best = '', max = 0;
for (const word of words) {
const n = (count.get(word) || 0) + 1;
count.set(word, n);
if (n > max) { max = n; best = word; }
}
return best ? { word: best, count: max } : null;
}时间复杂度 O(n)，空间复杂度 O(u)，u 为不同单词数。
103. 手写一个 jsonp
答案：
JSONP 利用 script 请求不受同源策略限制的特点，通过全局回调接收服务端返回的 JavaScript。它只能发 GET，且服务端必须配合返回 callback(data)；生产实现应处理超时、错误和清理全局回调。
js
function jsonp(url, params = {}, timeout = 5000) {
return new Promise((resolve, reject) => {
const name = `jsonp_${Date.now()}_${Math.random().toString(36).slice(2)}`;
const script = document.createElement('script');
const query = new URLSearchParams({...params, callback: name});
let timer;
const clean = () => { clearTimeout(timer); delete window[name]; script.remove(); };
window[name] = data => { clean(); resolve(data); };
script.onerror = () => { clean(); reject(new Error('JSONP request failed')); };
timer = setTimeout(() => { clean(); reject(new Error('JSONP timeout')); }, timeout);
script.src = `${url}?${query}`;
document.head.appendChild(script);
});
}104. 如何判断一个对象是否为空对象？
答案：
对普通对象，Object.keys 只统计自身可枚举字符串属性，长度为 0 就是空对象；它不会把继承属性误算进去。若还要考虑 Symbol 键，可改用 Reflect.ownKeys。
js
function isEmptyObject(value) {
return value !== null && typeof value === 'object' &&
Object.keys(value).length === 0;
}该实现把数组、日期等“无自身可枚举属性”的对象也判为空；若业务只接受纯对象，应额外检查原型是否为 Object.prototype 或 null。
105. 封装一个 javascript 的类型判断函数
答案：
typeof 对数组、日期、正则等都只返回 object，可用 Object.prototype.toString 获取更准确的内置类型；null 单独处理。
js
function getType(value) {
if (value === null) return 'null';
if (value === undefined) return 'undefined';
return Object.prototype.toString.call(value).slice(8, -1).toLowerCase();
}例如返回 array、date、regexp、function。跨 realm 对象也能正确识别；自定义对象通常返回 object。
106. 什么是 MVVM？比之 MVC 有什么区别？什么又是 MVP ？
答案：
MVC 将模型、视图、控制器分离：Controller 接收输入并协调 Model 与 View；MVP 让 Presenter 持有 View 接口，负责更强的展示逻辑，View 通常更被动，便于测试；MVVM 以 ViewModel 暴露视图所需状态和命令，通过数据绑定同步 View 与 Model。三者都是关注点分离，差别主要在视图更新和交互逻辑由谁承担；现代前端常采用 MVVM 或响应式状态管理，但具体边界取决于框架。
107. 根据运算优先级添加括号
现已知一个字符串是由正整数和加减乘除四个运算符(+ - * /)组成。
例如存在字符串 const str = '11+2-3*4+5/2*4+10/5'，现在需要将高优先级运算，用小括号包裹起来，例如结果为 '11+2-(3*4)+(5/2*4)+(10/5)'。注意可能会出现连续的乘除运算，需要包裹到一起。
请用 javascript 实现这一过程
答案：
先按 +、- 切分加减层级，再把每个连续的乘除片段包在一对括号中；这样 3*4+5/2*4 会分别得到 (3*4)+(5/2*4)，连续乘除不会被拆散。
js
function addParentheses(str) {
return str.replace(/[+-]?[^+-]+/g, term => {
const sign = /^[+-]/.test(term) ? term[0] : '';
const body = sign ? term.slice(1) : term;
return /[*/]/.test(body) ? sign + '(' + body + ')' : term;
});
}
console.log(addParentheses('11+2-3*4+5/2*4+10/5'));
// 11+2-(3*4)+(5/2*4)+(10/5)假设输入只有正整数和四则运算符、无空格和括号；正负号的处理需按题目语法扩展。时间复杂度 O(n)。
108. 实现一个对象的 flatten 方法
实现以下转换：
js
const obj = {
a: {
b: 1,
c: 2,
d: {
e: 5
}
},
b: [1, 3, {a: 2, b: 3}],
c: 3
}flatten(obj){} 结果返回如下
js
// {
// 'a.b': 1,
// 'a.c': 2,
// 'a.d.e': 5,
// 'b[0]': 1,
// 'b[1]': 3,
// 'b[2].a': 2,
// 'b[2].b': 3
// c: 3
// }答案：
深度优先遍历对象和数组，路径中对象属性使用点号，数组下标使用 [i]；遇到原始值就写入结果。空对象和空数组没有叶子键，因此不会产生条目。
js
function flatten(input) {
const out = {};
function visit(value, path) {
if (value !== null && typeof value === 'object') {
for (const key of Object.keys(value)) {
const next = Array.isArray(value) ? `${path}[${key}]` : (path ? `${path}.${key}` : key);
visit(value[key], next);
}
} else if (path) out[path] = value;
}
visit(input, '');
return out;
}时间复杂度 O(n)，空间复杂度 O(h + r)；h 为嵌套深度，r 为结果规模。循环引用需要另加 WeakSet 检测。
109. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
- 示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。- 示例 2：
输入：s = "cbbd"
输出："bb"- 示例 3：
输入：s = "a"
输出："a"- 示例 4：
输入：s = "ac"
输出："a"- 提示：
1 <= s.length <= 1000
s 仅由数字和英文字母（大写和/或小写）组成答案：
以每个字符为中心向两侧扩展，同时处理奇数回文和偶数回文，记录最长区间。扩展遇到边界或字符不等时停止，天然覆盖单字符和空结果边界。
js
function longestPalindrome(s) {
let start = 0, end = 0;
const expand = (l, r) => {
while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
return [l + 1, r - 1];
};
for (let i = 0; i < s.length; i++) {
for (const [l, r] of [expand(i, i), expand(i, i + 1)]) {
if (r - l > end - start) [start, end] = [l, r];
}
}
return s.slice(start, end + 1);
}时间复杂度 O(n^2)，空间复杂度 O(1)；同长度时保留较早出现的结果。
110. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
- 示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2- 示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5- 示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000- 示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000- 示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000- 提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106答案：
可用二分切分较短数组。设 i 个元素在左半部，j=(m+n+1)/2-i，要求 A[i-1] <= B[j] 且 B[j-1] <= A[i]；找到合法切分后，奇数取左侧最大值，偶数取左侧最大与右侧最小的平均值。
js
function findMedianSortedArrays(a, b) {
if (a.length > b.length) return findMedianSortedArrays(b, a);
const m = a.length, n = b.length, half = Math.floor((m + n + 1) / 2);
let lo = 0, hi = m;
while (lo <= hi) {
const i = Math.floor((lo + hi) / 2), j = half - i;
const al = i ? a[i - 1] : -Infinity, ar = i < m ? a[i] : Infinity;
const bl = j ? b[j - 1] : -Infinity, br = j < n ? b[j] : Infinity;
if (al > br) hi = i - 1;
else if (bl > ar) lo = i + 1;
else return (m + n) % 2 ? Math.max(al, bl) : (Math.max(al, bl) + Math.min(ar, br)) / 2;
}
}时间复杂度 O(log(min(m,n)))，空间复杂度 O(1)；至少有一个数组非空。
111. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
- 示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。- 示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。- 示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。- 示例 4:
输入: s = ""
输出: 0- 提示：
- 0 <= s.length <= 5 * 104
- s 由英文字母、数字、符号和空格组成
答案：
滑动窗口维护无重复子串。记录字符最近一次位置；若该位置仍在窗口内，就把左边界跳到它的下一位，再更新最大长度。
js
function lengthOfLongestSubstring(s) {
const last = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const prev = last.get(s[right]);
if (prev !== undefined && prev >= left) left = prev + 1;
last.set(s[right], right);
best = Math.max(best, right - left + 1);
}
return best;
}每个字符最多进出窗口一次，时间复杂度 O(n)，空间复杂度 O(min(n,字符集大小))；空串返回 0。
112. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
- 示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.- 示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]- 示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]- 提示：
- 每个链表中的节点数在范围 [1, 100] 内
- 0 <= Node.val <= 9
- 题目数据保证列表表示的数字不含前导零
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/答案：
两个链表按低位到高位存储，逐节点相加并携带进位；遍历结束后若仍有进位，再补一个节点。用哨兵节点统一处理头节点。
js
function addTwoNumbers(l1, l2) {
const dummy = new ListNode(0);
let tail = dummy, carry = 0;
while (l1 || l2 || carry) {
const sum = (l1?.val || 0) + (l2?.val || 0) + carry;
carry = Math.floor(sum / 10);
tail.next = new ListNode(sum % 10);
tail = tail.next;
l1 = l1?.next || null; l2 = l2?.next || null;
}
return dummy.next;
}设两表长度最大为 n，时间复杂度 O(n)，额外空间 O(n)（结果节点）；空链表不在题目输入范围内。
113. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]提示：
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案
答案：
遍历数组，用 Map 保存已见值到下标。对当前值 x，先查 target-x 是否存在，存在即可返回两个下标，再保存 x，这样不会重复使用同一个元素。
js
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const j = seen.get(target - nums[i]);
if (j !== undefined) return [j, i];
seen.set(nums[i], i);
}
return [];
}时间复杂度 O(n)，空间复杂度 O(n)；重复值如 [3,3] 会在第二次遍历时匹配到第一次下标。
114. 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6示例 2：
输入：lists = []
输出：[]示例 3：
输入：lists = [[]]
输出：[]提示：
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 10^4
javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
};答案：
使用最小堆维护每个链表当前头节点。每次弹出最小节点接到结果尾部，再把它的下一个节点入堆，直到堆为空。
js
function mergeKLists(lists) {
const heap = [];
const push = node => { heap.push(node); let i = heap.length - 1;
while (i) { const p = (i - 1) >> 1; if (heap[p].val <= node.val) break; heap[i] = heap[p]; i = p; } heap[i] = node; };
const pop = () => { const top = heap[0], last = heap.pop(); if (heap.length) { let i = 0; while (i * 2 + 1 < heap.length) { let c = i * 2 + 1; if (c + 1 < heap.length && heap[c + 1].val < heap[c].val) c++; if (heap[c].val >= last.val) break; heap[i] = heap[c]; i = c; } heap[i] = last; } return top; };
for (const node of lists) if (node) push(node);
const dummy = new ListNode(0); let tail = dummy;
while (heap.length) { const node = pop(); tail.next = node; tail = node; if (node.next) push(node.next); }
return dummy.next;
}设总节点数为 N、链表数为 k，时间 O(N log k)，堆空间 O(k)；空数组或全空链表返回 null。
115. 解析url
/**
- 解析一个url，并生成window.location对象包含的域
- location:
- {
href: '包含完整的url',origin: '包含协议到pathname之前的内容',protocol: 'url使用的协议，包含末尾的:',username: '用户名', // 暂时不支持password: '密码', // 暂时不支持host: '完整主机名，包含:和端口',hostname: '主机名，不包含端口'port: '端口号',pathname: '服务器上访问资源的路径/开头',search: 'query string，?开头',hash: '#开头的fragment identifier'- }
- @param {string} url 需要解析的url
- @return {Object} 包含url信息的对象 */
答案：
浏览器环境优先使用标准 URL 解析，避免手写正则遗漏端口、编码或 hash 边界。origin 是协议、主机名和端口组成的源，search 保留 ?，hash 保留 #。
js
function parseUrl(input) {
const u = new URL(input, window.location.href);
return {
href: u.href, origin: u.origin, protocol: u.protocol,
username: u.username, password: u.password, host: u.host,
hostname: u.hostname, port: u.port, pathname: u.pathname,
search: u.search, hash: u.hash
};
}绝对 URL 可直接传入；相对 URL 必须提供基准地址。无效 URL 会抛出 TypeError，调用方应按需捕获。
116. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]示例 2：
输入：head = [1,2]
输出：[2,1]示例 3：
输入：head = []
输出：[]提示：
- 链表中节点的数目范围是 [0, 5000]
- -5000 <= Node.val <= 5000
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
};
**答案：**
迭代反转最稳妥：保存当前节点的下一个引用，把 `next` 指向前驱，再向后推进。
```js
function reverseList(head) {
let prev = null, cur = head;
while (cur) {
const next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}时间复杂度 O(n)，额外空间复杂度 O(1)；空链表直接返回 null，操作会原地改变原链表的指针。
117. 回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false示例 2:
输入: 1->2->2->1
输出: true答案：
用快慢指针找到中点，反转后半段，再与前半段逐项比较。比较完成后可再次反转后半段恢复链表，减少对调用方数据的副作用。
js
function isPalindrome(head) {
let slow = head, fast = head;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
let prev = null;
while (slow) { const next = slow.next; slow.next = prev; prev = slow; slow = next; }
let left = head, right = prev, ok = true;
while (right) { if (left.val !== right.val) { ok = false; break; } left = left.next; right = right.next; }
return ok;
}时间复杂度 O(n)，额外空间 O(1)；空链表和单节点链表都是回文。
118. 实现数字的千分位逗号分割
答案：
把整数部分从右向左每三位插入逗号，小数部分原样保留；用字符串处理可避免大数精度丢失，也能保留负号和小数末尾的 0。
js
function formatThousands(value) {
const s = String(value);
const sign = s.startsWith('-') ? '-' : '';
const body = sign ? s.slice(1) : s;
const [integer, fraction] = body.split('.');
const grouped = integer.replace(/\B(?=(\d{3})+(?!\d))/g, ',');
return sign + grouped + (fraction === undefined ? '' : '.' + fraction);
}
console.log(formatThousands(-1234567.89)); // -1,234,567.89时间复杂度 O(n)；输入应是合法十进制字符串，科学计数法需另行约定。
119. 大数相加
手写一个add方法，实现两个大数相加
答案：
将两个十进制字符串从末位向前相加，保存进位，最后反转结果。全程不转 Number，因此支持超过安全整数范围的大数。
js
function add(a, b) {
let i = a.length - 1, j = b.length - 1, carry = 0, out = [];
while (i >= 0 || j >= 0 || carry) {
const sum = (i >= 0 ? a.charCodeAt(i--) - 48 : 0) +
(j >= 0 ? b.charCodeAt(j--) - 48 : 0) + carry;
out.push(sum % 10); carry = Math.floor(sum / 10);
}
return out.reverse().join('') || '0';
}时间复杂度 O(max(m,n))，空间复杂度同为 O(max(m,n))；输入应为非负整数字符串，若允许前导零可在返回前规范化。
120. 什么是时间复杂度？
答案：
时间复杂度描述算法运行次数随输入规模 n 增长的数量级，通常忽略常数和低阶项，用大 O 表示上界趋势。例如一次遍历是 O(n)，二重独立遍历通常是 O(n²)，二分查找是 O(log n)。分析时应明确输入规模、最坏/平均/最好情况，并区分循环次数与单次操作成本；它不是实际耗时，也不等于空间复杂度。
121. 请手写“基数排序”
答案：
基数排序按位处理整数，从最低位到最高位使用稳定计数分配；每一轮保持前面位的相对顺序，最终得到整体有序。下面实现非负整数，0 和空数组是边界。
js
function radixSort(arr) {
if (arr.length < 2) return arr.slice();
let a = arr.slice(), max = Math.max(...a);
for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
const count = Array(10).fill(0), out = Array(a.length);
for (const x of a) count[Math.floor(x / exp) % 10]++;
for (let i = 1; i < 10; i++) count[i] += count[i - 1];
for (let i = a.length - 1; i >= 0; i--) { const d = Math.floor(a[i] / exp) % 10; out[--count[d]] = a[i]; }
a = out;
}
return a;
}d 为最大位数时，时间复杂度 O(d(n+10))，空间复杂度 O(n+10)；负数需拆分正负部分或改用带符号方案。
122. 请手写“桶排序”
答案：
桶排序先按值域把元素分到多个桶，再分别排序并连接。它依赖数据较均匀，桶内可用插入排序；下面支持任意有限数字并返回新数组。
js
function bucketSort(arr, bucketCount = Math.max(1, Math.ceil(Math.sqrt(arr.length)))) {
if (arr.length < 2) return arr.slice();
const min = Math.min(...arr), max = Math.max(...arr);
const width = (max - min) / bucketCount || 1;
const buckets = Array.from({length: bucketCount}, () => []);
for (const x of arr) buckets[Math.min(bucketCount - 1, Math.floor((x - min) / width))].push(x);
for (const bucket of buckets) {
for (let i = 1; i < bucket.length; i++) { const x = bucket[i]; let j = i - 1; while (j >= 0 && bucket[j] > x) { bucket[j + 1] = bucket[j]; j--; } bucket[j + 1] = x; }
}
return buckets.flat();
}平均时间约 O(n+k) 加桶内排序成本，最坏可达 O(n²)；空间 O(n+k)，k 为桶数。
123. 请手写“计数排序”
答案：
计数排序统计每个整数出现次数，再按值域展开；适合值域 k 不大且为整数的数据。用最小值偏移可支持负数，并返回新数组。
js
function countingSort(arr) {
if (arr.length < 2) return arr.slice();
let min = Math.min(...arr), max = Math.max(...arr);
const count = Array(max - min + 1).fill(0);
for (const x of arr) count[x - min]++;
const out = [];
for (let i = 0; i < count.length; i++) for (let n = count[i]; n--; ) out.push(i + min);
return out;
}时间复杂度 O(n+k)，空间复杂度 O(n+k)；值域远大于元素数量时会浪费内存，不应盲目使用。
124. 请手写“堆排序”
答案：
先自底向上建大顶堆，每次交换堆顶与未排序区末尾，再对缩小后的堆做下沉，最终得到升序数组。
js
function heapSort(arr) {
const a = arr.slice();
const down = (i, n) => {
while (true) { let largest = i, l = i * 2 + 1, r = l + 1;
if (l < n && a[l] > a[largest]) largest = l;
if (r < n && a[r] > a[largest]) largest = r;
if (largest === i) return; [a[i], a[largest]] = [a[largest], a[i]]; i = largest;
}
};
for (let i = (a.length >> 1) - 1; i >= 0; i--) down(i, a.length);
for (let end = a.length - 1; end > 0; end--) { [a[0], a[end]] = [a[end], a[0]]; down(0, end); }
return a;
}建堆 O(n)，排序总时间 O(n log n)，额外空间 O(1)（不计返回副本）；堆排序不稳定。
125. 请手写“快速排序”
答案：
快速排序采用分治：选择基准并原地分区，使较小元素在左、较大元素在右，再递归处理两侧。使用双指针分区并把较短区间先递归，可降低栈深度。
js
function quickSort(arr) {
const a = arr.slice();
function sort(l, r) {
while (l < r) {
let i = l, j = r, pivot = a[l + ((r - l) >> 1)];
while (i <= j) { while (a[i] < pivot) i++; while (a[j] > pivot) j--; if (i <= j) [a[i++], a[j--]] = [a[j], a[i]]; }
if (j - l < r - i) { if (l < j) sort(l, j); l = i; }
else { if (i < r) sort(i, r); r = j; }
}
}
sort(0, a.length - 1); return a;
}平均时间 O(n log n)，最坏 O(n²)，平均栈空间 O(log n)；已复制数组，原数组不变，重复值可正常处理。
126. 请手写“归并排序”
答案：
归并排序把数组递归分成两半，再用双指针合并两个有序数组。合并时相等元素优先取左边，因此算法稳定。
js
function mergeSort(arr) {
if (arr.length < 2) return arr.slice();
const mid = arr.length >> 1, left = mergeSort(arr.slice(0, mid)), right = mergeSort(arr.slice(mid));
const out = []; let i = 0, j = 0;
while (i < left.length && j < right.length) out.push(left[i] <= right[j] ? left[i++] : right[j++]);
return out.concat(left.slice(i), right.slice(j));
}时间复杂度最好、平均、最坏均为 O(n log n)，空间复杂度 O(n)；空数组和单元素数组直接返回。
127. 请手写“希尔排序”
答案：
希尔排序是带间隔的插入排序：先用较大 gap 让元素远距离移动，逐步缩小 gap，最后 gap 为 1 完成普通插入排序。
js
function shellSort(arr) {
const a = arr.slice();
for (let gap = a.length >> 1; gap > 0; gap >>= 1) {
for (let i = gap; i < a.length; i++) {
const x = a[i]; let j = i;
while (j >= gap && a[j - gap] > x) { a[j] = a[j - gap]; j -= gap; }
a[j] = x;
}
}
return a;
}复杂度取决于 gap 序列；上述折半序列最坏可达 O(n²)，额外空间 O(1)，且通常不稳定。
128. 请手写“插入排序”
答案：
插入排序维护一个已排序前缀，取出当前元素，从后向前移动比它大的元素，再插入空位；相等时不移动，因而稳定。
js
function insertionSort(arr) {
const a = arr.slice();
for (let i = 1; i < a.length; i++) {
const x = a[i]; let j = i - 1;
while (j >= 0 && a[j] > x) { a[j + 1] = a[j]; j--; }
a[j + 1] = x;
}
return a;
}最好情况（已有序）时间 O(n)，平均和最坏 O(n²)，额外空间 O(1)（不计返回副本）；数组很小或接近有序时实用。
129. 请手写“选择排序”
答案：
选择排序每轮在未排序区间中寻找最小值，与区间首元素交换：
js
function selectionSort(a) {
for (let i = 0; i < a.length - 1; i++) {
let min = i;
for (let j = i + 1; j < a.length; j++) if (a[j] < a[min]) min = j;
if (min !== i) [a[i], a[min]] = [a[min], a[i]];
}
return a;
}原地排序，空间复杂度 O(1)，最好、平均、最坏时间复杂度均为 O(n²)，通常不稳定。
130. 请手写“冒泡排序”
答案：
冒泡排序反复比较相邻元素，把较大者交换到右侧；每轮确定一个最大值，若一轮没有交换即可提前结束：
js
function bubbleSort(a) {
for (let end = a.length - 1; end > 0; end--) {
let swapped = false;
for (let i = 0; i < end; i++) if (a[i] > a[i + 1]) { [a[i], a[i + 1]] = [a[i + 1], a[i]]; swapped = true; }
if (!swapped) break;
}
return a;
}原地且稳定；最好 O(n)，平均和最坏 O(n²)，空间 O(1)。
131. 实现柯里化
答案：
柯里化把一个接收多个参数的函数转换成连续接收单个或部分参数的函数，参数收集到函数声明的 arity 后执行：
js
function curry(fn, collected = []) {
return (...args) => {
const all = [...collected, ...args];
return all.length >= fn.length ? fn(...all) : curry(fn, all);
};
}
const add = curry((a, b, c) => a + b + c);
add(1)(2, 3); // 6每次调用会创建新闭包，调用链长度为 k 时额外空间约 O(k)；应明确如何处理占位符、超额参数和 this。
132. 观察者模式和发布订阅模式分别是什么？有什么区别？
答案：
观察者模式中，主题对象直接持有观察者并在状态变化时通知它们，二者存在直接依赖，适合进程内响应式更新。发布订阅模式增加事件总线或调度中心：发布者和订阅者彼此不知道对方，通过事件名解耦，适合跨模块、跨应用通信。前者结构简单、调用直接；后者灵活但需处理事件命名、顺序、取消订阅和内存泄漏。
133. 实现一个方法，清除字符串前后的空格。
答案：
使用正则的 \s 可同时处理空格、制表符和换行：
js
function trim(str) {
if (typeof str !== 'string') throw new TypeError('str must be a string');
return str.replace(/^\s+|\s+$/g, '');
}
trim(' hello \n'); // 'hello'现代 JavaScript 直接调用 String.prototype.trim() 更简洁。时间复杂度 O(n)，不应误删字符串中间的空白。
134. 改造下面的代码，让它输出1，2，3，4，5
for(var i = 1; i <= 5; i ++){ setTimeout(function timer(){ console.log(i) }, 0) }
答案：
原代码使用 var，定时器回调共享同一个函数作用域，循环结束时 i 已为 6，所以会输出五次 6。用 let 为每轮创建块级绑定：
js
for (let i = 1; i <= 5; i++) {
setTimeout(() => console.log(i), 0);
}也可在 var 版本中用 IIFE 或 setTimeout(fn, 0, i) 传入当前值。输出顺序为 1、2、3、4、5。
135. 工厂模式
答案：
工厂模式把对象创建逻辑集中到工厂，由工厂依据类型或配置返回具体产品，调用方只依赖产品接口，不直接绑定具体构造函数。简单工厂适合少量类型，工厂方法让子类决定创建哪种产品，抽象工厂负责创建一组相互匹配的产品。优点是隔离创建逻辑、降低耦合；类型持续增加时需注意工厂本身可能变得复杂。
136. 单例模式
答案：
单例模式保证某类在一个作用域内只有一个实例，并提供统一访问入口，常用于配置、日志或共享资源管理。JavaScript 中可用模块闭包实现懒创建：
js
const Singleton = (() => {
let instance;
return { get() { return instance || (instance = { createdAt: Date.now() }); } };
})();优点是共享实例、避免重复初始化；缺点是隐藏全局状态、增加测试和并发隔离难度，不能滥用。
137. 设计模式的六大原则
答案：
设计模式常说的六项原则是：单一职责原则，一个模块只承担一个变化原因；开放封闭原则，对扩展开放、对修改关闭；里氏替换原则，子类型必须能替换父类型而不破坏契约；依赖倒置原则，依赖抽象而非具体；接口隔离原则，使用小而专的接口；迪米特法则，模块只了解必要的协作者，保持低耦合。
138. 设计模式分类
答案：
经典设计模式按目的分三类。创建型关注对象如何创建，包括工厂方法、抽象工厂、单例、建造者和原型；结构型关注类或对象如何组合，包括适配器、装饰器、代理、外观、桥接、组合和享元；行为型关注职责分配与协作，包括策略、模板方法、观察者、迭代器、责任链、命令、备忘录、状态、访问者、中介者和解释器。
139. 实现有并行限制的Promise调度器
答案：
调度器用队列保存任务工厂，用 running 控制并发数；一个任务完成或失败后释放槽位并继续取下一个：
js
class Scheduler {
constructor(limit = 2) { this.limit = limit; this.running = 0; this.queue = []; }
add(task) { return new Promise((resolve, reject) => { this.queue.push({ task, resolve, reject }); this.next(); }); }
next() {
while (this.running < this.limit && this.queue.length) {
const item = this.queue.shift(); this.running++;
Promise.resolve().then(item.task).then(item.resolve, item.reject).finally(() => { this.running--; this.next(); });
}
}
}最多同时运行 limit 个任务；队列空间 O(n)，调度开销 O(n)。
140. 实现 Promise.all
答案：
Promise.all 要等待全部成功，结果顺序与输入一致；任一任务拒绝则立即拒绝，空迭代器应立即成功：
js
function promiseAll(iterable) {
return new Promise((resolve, reject) => {
const values = [], items = [...iterable]; let done = 0;
if (!items.length) return resolve([]);
items.forEach((item, i) => Promise.resolve(item).then(v => {
values[i] = v; if (++done === items.length) resolve(values);
}, reject));
});
}时间复杂度 O(n)，结果数组空间 O(n)，并兼容普通值和可迭代对象。
141. 字符串解析问题
实现函数使得将str字符串中的{}内的变量替换，如果属性不存在保持原样（比如{a.d}）
js
var a = {
b: 123,
c: '456',
e: '789',
}
var str=`a{a.b}aa{a.c}aa {a.d}aaaa`;
// => 'a123aa456aa {a.d}aaaa'答案：
可扫描字符串，在遇到 { 和 } 时取出路径，用点号逐级访问对象；任一层不存在就保留原占位符：
js
function interpolate(str, data) {
return str.replace(/\{([^{}]+)\}/g, (raw, path) => {
const keys = path.split('.'); let value = data;
for (const key of keys) {
if (value == null || !Object.prototype.hasOwnProperty.call(Object(value), key)) return raw;
value = value[key];
}
return String(value);
});
}例如 {a.d} 不存在时原样返回。复杂度为 O(n + p)，其中 p 为路径访问总长度；正则版不处理嵌套花括号。
142. 实现 event模块
实现node中回调函数的机制，node中回调函数其实是内部使用了观察者模式。
观察者模式：定义了对象间一种一对多的依赖关系，当目标对象Subject发生改变时，所有依赖它的对象Observer都会得到通知。
答案：
事件模块用事件名映射监听器数组，提供订阅、取消订阅、一次性订阅和发布：
js
class EventEmitter {
constructor() { this.events = new Map(); }
on(type, fn) { const list = this.events.get(type) || []; list.push(fn); this.events.set(type, list); return this; }
once(type, fn) { const wrap = (...args) => { this.off(type, wrap); fn(...args); }; return this.on(type, wrap); }
off(type, fn) { const list = this.events.get(type) || []; this.events.set(type, list.filter(f => f !== fn)); return this; }
emit(type, ...args) { for (const fn of [...(this.events.get(type) || [])]) fn(...args); return this; }
}复制监听器数组可避免回调中修改集合影响本轮派发；需按需补充 removeAllListeners。
143. 实现AJAX
答案：
AJAX 可封装为 Promise，监听完成状态并区分 HTTP 成功与网络错误：
js
function getJSON(url) {
return new Promise((resolve, reject) => {
const xhr = new XMLHttpRequest();
xhr.open('GET', url, true); xhr.responseType = 'json';
xhr.onload = () => xhr.status >= 200 && xhr.status < 300 ? resolve(xhr.response) : reject(new Error(String(xhr.status)));
xhr.onerror = () => reject(new Error('network error'));
xhr.send();
});
}onload 表示响应完成，不等于业务成功，状态码应单独判断；跨域请求还需服务端 CORS。
144. 实现JSONP
答案：
JSONP 利用 script 不受同源策略限制的特点，请求方传入回调名，服务端返回 回调名(数据)：
js
function jsonp(url, params = {}) {
return new Promise((resolve, reject) => {
const name = `jsonp_${Date.now()}_${Math.random().toString(16).slice(2)}`;
const script = document.createElement('script');
const query = new URLSearchParams({ ...params, callback: name });
const cleanup = () => { delete window[name]; script.remove(); };
window[name] = data => { cleanup(); resolve(data); };
script.onerror = () => { cleanup(); reject(new Error('JSONP failed')); };
script.src = `${url}?${query}`; document.head.appendChild(script);
});
}它只支持 GET，且依赖服务端配合，不能像 CORS 一样安全地进行任意跨域请求。
145. 实现 Promise
答案：
Promise 的核心是三态模型：pending 只能单向转为 fulfilled 或 rejected；then 必须返回新 Promise，并把回调返回值或异常传递给它：
js
class MyPromise {
constructor(executor) {
this.state = 'pending'; this.value = undefined; this.handlers = [];
const settle = (state, value) => { if (this.state !== 'pending') return; this.state = state; this.value = value; queueMicrotask(() => this.handlers.splice(0).forEach(h => this.run(h))); };
const resolve = v => v && typeof v.then === 'function' ? v.then(resolve, reject) : settle('fulfilled', v);
const reject = e => settle('rejected', e);
try { executor(resolve, reject); } catch (e) { reject(e); }
}
run(h) { const fulfilled = this.state === 'fulfilled'; const fn = fulfilled ? h.ok : h.fail; try { if (fn) h.resolve(fn(this.value)); else (fulfilled ? h.resolve : h.reject)(this.value); } catch (e) { h.reject(e); } }
then(ok, fail) { return new MyPromise((resolve, reject) => { const h = { ok, fail, resolve, reject }; this.handlers.push(h); if (this.state !== 'pending') queueMicrotask(() => this.run(h)); }); }
}面试实现需特别说明 thenable 吸收、异常冒泡和异步回调；完整规范实现还需处理自解析循环。
146. 实现深拷贝
答案：
深拷贝要递归复制嵌套对象，并用 WeakMap 记录已复制对象以处理循环引用：
js
function cloneDeep(value, seen = new WeakMap()) {
if (value === null || typeof value !== 'object') return value;
if (seen.has(value)) return seen.get(value);
if (value instanceof Date) return new Date(value);
if (value instanceof RegExp) return new RegExp(value.source, value.flags);
const out = Array.isArray(value) ? [] : {}; seen.set(value, out);
for (const key of Reflect.ownKeys(value)) {
const d = Object.getOwnPropertyDescriptor(value, key);
if ('value' in d) d.value = cloneDeep(d.value, seen);
Object.defineProperty(out, key, d);
}
return out;
}时间复杂度 O(n)，空间复杂度 O(n)。Map、Set、TypedArray 和自定义原型可按业务继续扩展。
147. 实现Object.assign
答案：
Object.assign 把一个或多个源对象的自有可枚举字符串键和 Symbol 键，按从左到右顺序浅复制到目标对象，并返回目标对象：
js
function assign(target, ...sources) {
if (target == null) throw new TypeError('target is null');
const out = Object(target);
for (const source of sources) {
if (source == null) continue;
for (const key of Reflect.ownKeys(Object(source))) {
if (Object.prototype.propertyIsEnumerable.call(source, key)) out[key] = source[key];
}
}
return out;
}它不递归，后面的同名属性覆盖前面的；getter 会被读取，setter 可能抛错。
148. 实现 instanceof
答案：
instanceof 判断构造函数的 prototype 是否出现在对象的原型链上：
js
function myInstanceof(value, Ctor) {
if (value == null || (typeof value !== 'object' && typeof value !== 'function')) return false;
if (typeof Ctor !== 'function' || !Ctor.prototype) throw new TypeError('invalid constructor');
let proto = Object.getPrototypeOf(value);
while (proto) {
if (proto === Ctor.prototype) return true;
proto = Object.getPrototypeOf(proto);
}
return false;
}时间复杂度 O(h)，h 为原型链高度。它不判断跨 realm 的内建类型，且右侧可通过 Symbol.hasInstance 自定义语义。
149. 函数珂里化
实现方法add：
js
add(1)(2)(3)(4)=10;
add(1)(1,2,3)(2)=9;答案：
可返回一个函数持续收集参数，并重写 valueOf/toString，使其参与运算时得到总和：
js
function add(...first) {
const args = [...first];
const fn = (...next) => { args.push(...next); return fn; };
const sum = () => args.reduce((total, n) => total + n, 0);
fn.valueOf = sum; fn.toString = () => String(sum());
return fn;
}
add(1)(2)(3)(4) == 10; // true
add(1)(1, 2, 3)(2) == 9; // true这里用宽松相等触发 valueOf；若要求显式结果，可约定调用 add(...)(...)()，避免依赖隐式类型转换。
150. 实现 throttle（节流）函数
答案：
节流保证连续高频触发时，固定时间窗口内最多执行一次；下面是 leading + trailing 版本：
js
function throttle(fn, wait) {
let last = 0, timer = null, lastArgs, lastThis;
return function (...args) {
const now = Date.now(), remain = wait - (now - last);
lastArgs = args; lastThis = this;
if (remain <= 0) { if (timer) clearTimeout(timer); timer = null; last = now; fn.apply(lastThis, lastArgs); }
else if (!timer) timer = setTimeout(() => { timer = null; last = Date.now(); fn.apply(lastThis, lastArgs); }, remain);
};
}常用于 scroll、resize、拖拽；需明确是否保留首尾触发，计时器也应在组件销毁时清理。
151. 实现 debounce（防抖）函数
答案：
防抖把多次连续触发合并为一次：每次触发都取消旧计时器，只有停止触发超过等待时间才执行：
js
function debounce(fn, wait, immediate = false) {
let timer;
return function (...args) {
const callNow = immediate && !timer;
clearTimeout(timer);
timer = setTimeout(() => { timer = null; if (!immediate) fn.apply(this, args); }, wait);
if (callNow) fn.apply(this, args);
};
}适合搜索输入、窗口 resize 等场景。时间开销为每次 O(1)，应在组件卸载时取消计时器以避免悬挂回调。
152. 实现 Function.prototype.bind
答案：
bind 返回新函数，调用时把目标函数的 this 与预置参数拼接；被绑定函数用 new 调用时，原绑定的 this 应失效：
js
function bind(fn, context, ...preset) {
if (typeof fn !== 'function') throw new TypeError('not callable');
function bound(...rest) {
const isNew = this instanceof bound;
return fn.apply(isNew ? this : context, [...preset, ...rest]);
}
bound.prototype = Object.create(fn.prototype);
return bound;
}严格兼容原生还需处理构造函数返回对象、length/name 和 null/undefined 的 this 规则。
153. 实现 Function.prototype.call
答案：
call 在指定 this 上临时挂载原函数，用参数列表调用后删除临时属性；用 Symbol 可避免键冲突：
js
function call(fn, context, ...args) {
if (typeof fn !== 'function') throw new TypeError('not callable');
const receiver = context == null ? globalThis : Object(context);
const key = Symbol('fn'); receiver[key] = fn;
try { return receiver[key](...args); } finally { delete receiver[key]; }
}原生 fn.call(ctx, ...) 在严格模式下保留 null/undefined 的 this；上例用 globalThis 是非严格模拟的常见简化。
154. 实现 Function.prototype.apply()
第一个参数是绑定的this，默认为window，第二个参数是数组或类数组
答案：
apply 与 call 的绑定规则相同，区别是第二个参数为数组或类数组：
js
function apply(fn, context, args) {
if (typeof fn !== 'function') throw new TypeError('not callable');
const receiver = context == null ? globalThis : Object(context);
const key = Symbol('fn'); receiver[key] = fn;
try { return receiver[key](...(args == null ? [] : Array.from(args))); }
finally { delete receiver[key]; }
}需支持 null/undefined 参数数组表示无参数，并在调用结束后清理临时属性；真实内建方法还受严格模式和长度限制影响。
155. 实现 Array.prototype.reduce()
答案：
reduce 从初始值开始依次累积；未提供初始值时取第一个存在的元素，空数组则抛错，并跳过稀疏空位：
js
function reduce(arr, callback, initial) {
if (arr == null || typeof callback !== 'function') throw new TypeError();
const obj = Object(arr); let i = 0, acc;
if (arguments.length >= 3) acc = initial;
else { while (i < obj.length && !(i in obj)) i++; if (i >= obj.length) throw new TypeError('empty'); acc = obj[i++]; }
for (; i < obj.length; i++) if (i in obj) acc = callback(acc, obj[i], i, obj);
return acc;
}时间 O(n)，空间 O(1)；原生还会固定开始时的 length。
156. 实现 Array.prototype.forEach()
答案：
forEach 按开始时确定的 length 遍历存在的索引，调用回调但不收集返回值，也不会遍历回调中新添加到末尾的元素：
js
function forEach(arr, callback, thisArg) {
if (arr == null || typeof callback !== 'function') throw new TypeError();
const obj = Object(arr), len = obj.length >>> 0;
for (let i = 0; i < len; i++) if (i in obj) callback.call(thisArg, obj[i], i, obj);
}稀疏数组空位会被跳过，回调抛出的异常直接向外传播，时间复杂度 O(n)。
157. 实现 Array.prototype.map()
答案：
map 为每个存在的索引调用回调并生成新数组，保留稀疏结构，不修改原数组：
js
function map(arr, callback, thisArg) {
if (arr == null || typeof callback !== 'function') throw new TypeError();
const obj = Object(arr), len = obj.length >>> 0, out = new Array(len);
for (let i = 0; i < len; i++) if (i in obj) out[i] = callback.call(thisArg, obj[i], i, obj);
return out;
}结果长度与原数组初始 length 相同，复杂度 O(n)，额外空间 O(n)。
158. 类数组转化为数组
类数组是具有length属性，但不具有数组原型上的方法。常见的类数组有arguments、DOM操作方法返回的结果。
答案：
类数组具有非负整数索引和 length，但不一定继承 Array 原型。常见转换方式是 Array.from(value)，它能处理可迭代对象和普通类数组；也可用 [...value]（要求可迭代）或 Array.prototype.slice.call(value)。例如：
js
function toArray(arrayLike) { return Array.from(arrayLike); }转换会创建新数组，时间和空间复杂度均为 O(n)；类数组缺失的索引会按迭代/映射规则处理。
159. 数组去重
js
const arr = [1, 1, '1', 17, true, true, false, false, 'true', 'a', {}, {}];
// => [1, '1', 17, true, false, 'true', 'a', {}, {}]答案：
推荐 Set 去重，它按 SameValueZero 判断，保留首次出现顺序，并能区分数字 1 与字符串 '1'：
js
function unique(arr) { return [...new Set(arr)]; }示例中的两个对象引用不同，因此都会保留；两个 NaN 会视为同一个。时间复杂度平均 O(n)，空间 O(n)。若要按对象某个字段去重，应改用 Map 按字段建立键。
160. 实现一个函数，判断输入是不是回文字符串。
“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
答案：
回文判断可用双指针从两端向中间比较，发现一对字符不同立即返回 false：
js
function isPalindrome(value) {
if (typeof value !== 'string') return false;
for (let left = 0, right = value.length - 1; left < right; left++, right--) {
if (value[left] !== value[right]) return false;
}
return true;
}该实现区分大小写和空白；若题目要求忽略大小写、空格或标点，应先按规则规范化。时间复杂度 O(n)，额外空间 O(1)。
161. 最大的钻石
1 楼到 n 楼的每层电梯门口都放着一颗钻石，钻石大小不一。你乘坐电梯从 1 楼到 n 楼，每层楼电梯门都会打开一次，只能拿一次钻石，问怎样才能拿到「最大」的一颗？
答案：
在钻石大小独立、随机排列，且只能当场选择、不能回看的前提下，这是秘书问题。不能保证必拿到最大值；当楼层数较大时，先放弃约 n/e（约 37%）层并记录其中最大值，之后选择第一颗大于该记录的钻石，可使拿到全局最大值的概率达到最优的渐近策略。若后面始终没有更大的钻石，则最后一层必须选择。若大小分布受人为安排、可比较历史信息或 n 很小时，应按具体条件计算精确阈值。