前端算法图解

// 方法1：递归版 function flatten(arr) { const result = []; for (const item of arr) { if (Array.isArray(item)) { result.push(...flatten(item)); } else { result.push(item); } } return result; } // 方法2：reduce 版 const flattenReduce = (arr) => arr.reduce((acc, cur) => acc.concat(Array.isArray(cur) ? flattenReduce(cur) : cur) , []); // 方法3：ES6 flat() const flattenES6 = (arr) => arr.flat(Infinity);

// 方法4：迭代版（用栈模拟递归） function flattenIterative(arr) { const stack = [...arr]; const result = []; while (stack.length) { const item = stack.pop(); if (Array.isArray(item)) { // 展开后压回栈（注意顺序要反转） stack.push(...item.reverse()); } else { result.push(item); } } return result.reverse(); // 结果也需反转 } // 面试对比：递归简洁但可能栈溢出 // 迭代用显式栈，无栈溢出风险 // ES6 flat(Infinity) 底层也是迭代实现

function deepClone(obj, map = new WeakMap()) { // null 或非对象，直接返回 if (obj === null || typeof obj !== 'object') return obj; // 处理循环引用 if (map.has(obj)) return map.get(obj); // Date if (obj instanceof Date) return new Date(obj); // RegExp if (obj instanceof RegExp) return new RegExp(obj); // 数组 const clone = Array.isArray(obj) ? [] : {}; map.set(obj, clone); // Symbol 作为 key const keys = [...Object.keys(obj), ...Object.getOwnPropertySymbols(obj)]; for (const key of keys) { clone[key] = deepClone(obj[key], map); } return clone; }

// 浅拷贝方式一览 const obj = { a: 1, b: { c: 2 } }; // 1. Object.assign const copy1 = Object.assign({}, obj); // 2. 展开运算符 const copy2 = { ...obj }; // 3. Array.slice / concat (数组) const arr = [1, { x: 2 }]; const copy3 = arr.slice(); // 以上都是浅拷贝：b 仍指向同一个对象！ copy1.b === obj.b // true ⚠️

// 方法1：Set（推荐） const unique1 = (arr) => [...new Set(arr)]; // 方法2：filter + indexOf const unique2 = (arr) => arr.filter((item, i) => arr.indexOf(item) === i); // 方法3：reduce const unique3 = (arr) => arr.reduce((acc, cur) => acc.includes(cur) ? acc : [...acc, cur], []); // 方法4：Map const unique4 = (arr) => { const map = new Map(); arr.forEach(item => map.set(item, true)); return [...map.keys()]; }

// DFS 递归三序 function preorder(root, res = []) { if (!root) return res; res.push(root.val); preorder(root.left, res); preorder(root.right, res); return res; } function inorder(root, res = []) { if (!root) return res; inorder(root.left, res); res.push(root.val); inorder(root.right, res); return res; } function postorder(root, res = []) { if (!root) return res; postorder(root.left, res); postorder(root.right, res); res.push(root.val); return res; } // DFS 迭代版（栈）— 以前序为例 function preorderIter(root) { const res = [], stack = [root]; while (stack.length) { const node = stack.pop(); if (!node) continue; res.push(node.val); stack.push(node.right); // 右先入栈 stack.push(node.left); } return res; } // BFS 层序（队列） function levelOrder(root) { if (!root) return []; const res = [], queue = [root]; while (queue.length) { const node = queue.shift(); res.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } return res; }

// 中序遍历迭代版（最经典的栈写法） function inorderIterative(root) { const res = [], stack = []; let cur = root; while (cur || stack.length) { // 1. 沿左子树一路走到底，压栈 while (cur) { stack.push(cur); cur = cur.left; } // 2. 弹出栈顶 = 最左节点 cur = stack.pop(); res.push(cur.val); // 3. 转向右子树 cur = cur.right; } return res; // 输出: 4→2→5→1→6→3→7 } // 后序迭代技巧：前序(根右左) → 反转 // 即把前序的 left/right 交换，最后 reverse

// 防抖：最后一次触发后 delay ms 执行 function debounce(fn, delay) { let timer = null; return function(...args) { clearTimeout(timer); timer = setTimeout(() => fn.apply(this, args), delay); }; } // 节流：每隔 delay ms 最多执行一次 function throttle(fn, delay) { let last = 0; return function(...args) { const now = Date.now(); if (now - last >= delay) { last = now; fn.apply(this, args); } }; } // 使用示例 input.addEventListener('input', debounce(search, 300)); window.addEventListener('scroll', throttle(handleScroll, 200));

// 节流定时器版：能保证最后一次触发也执行 function throttleTimer(fn, delay) { let timer = null; return function(...args) { if (timer) return; // 还在冷却中，跳过 timer = setTimeout(() => { fn.apply(this, args); timer = null; // 冷却结束 }, delay); }; } // 两种版本区别： // 时间戳版：首次立即执行，最后一次不执行 // 定时器版：首次延迟执行，最后一次会执行 // 面试加分：合并版（首尾都执行）

// 串行：reduce 依次执行 function runSerial(fns) { return fns.reduce((p, fn) => p.then(fn), Promise.resolve()); } // 并行：Promise.all 同时执行 function runParallel(fns) { return Promise.all(fns.map(fn => fn())); } // 限流：最多同时 concurrency 个 async function runLimit(fns, concurrency = 2) { const results = []; const executing = new Set(); for (const [i, fn] of fns.entries()) { const p = fn().then(r => { executing.delete(p); results[i] = r; }); executing.add(p); if (executing.size >= concurrency) { await Promise.race(executing); } } await Promise.all(executing); return results; }

// Map 版 LRU（利用 Map 的插入顺序） class LRUCache { constructor(capacity) { this.capacity = capacity; this.cache = new Map(); } get(key) { if (!this.cache.has(key)) return -1; const val = this.cache.get(key); this.cache.delete(key); // 删除后重新插入→移到末尾(最新) this.cache.set(key, val); return val; } put(key, value) { if (this.cache.has(key)) this.cache.delete(key); this.cache.set(key, value); if (this.cache.size > this.capacity) { // Map.keys() 第一个 = 最久未用 const oldest = this.cache.keys().next().value; this.cache.delete(oldest); } } } // 双向链表版：面试白板更常见 // 思路：head↔...↔tail // get: delete node → insertAfterHead // put: if full → removeTail → insertAfterHead

// 双向链表节点 class Node { constructor(key, val) { this.key = key; this.val = val; this.prev = null; this.next = null; } } // 双向链表版 LRU（白板面试标配） class LRUCache2 { constructor(cap) { this.cap = cap; this.map = new Map(); // 哨兵节点简化边界处理 this.head = new Node(0, 0); this.tail = new Node(0, 0); this.head.next = this.tail; this.tail.prev = this.head; } // 删除节点 remove(node) { node.prev.next = node.next; node.next.prev = node.prev; } // 插入到 head 后面（最近使用） insertHead(node) { node.next = this.head.next; node.prev = this.head; this.head.next.prev = node; this.head.next = node; } get(key) { if (!this.map.has(key)) return -1; const node = this.map.get(key); this.remove(node); this.insertHead(node); return node.val; } put(key, val) { if (this.map.has(key)) this.remove(this.map.get(key)); const node = new Node(key, val); this.map.set(key, node); this.insertHead(node); if (this.map.size > this.cap) { // 淘汰 tail 前面的节点 const lru = this.tail.prev; this.remove(lru); this.map.delete(lru.key); } } }

class EventEmitter { constructor() { this.events = {}; } on(event, fn) { (this.events[event] ||= []).push(fn); return this; } off(event, fn) { if (!this.events[event]) return this; this.events[event] = this.events[event] .filter(f => f !== fn); return this; } emit(event, ...args) { (this.events[event] || []).forEach(fn => fn(...args)); return this; } once(event, fn) { const wrapper = (...args) => { fn(...args); this.off(event, wrapper); }; this.on(event, wrapper); return this; } } // 使用示例 const ee = new EventEmitter(); const handler = (data) => console.log('收到:', data); ee.on('msg', handler); ee.emit('msg', 'hello'); // 收到: hello ee.off('msg', handler);