算法与数据结构

冒泡排序（O(n²)）：
function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

快速排序（O(n log n)）：
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = arr.slice(1).filter(x => x <= pivot);
  const right = arr.slice(1).filter(x => x > pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

1. Set（最简洁）：
[...new Set(arr)]

2. filter + indexOf：
arr.filter((item, i) => arr.indexOf(item) === i)

3. reduce + includes：
arr.reduce((acc, cur) => acc.includes(cur) ? acc : [...acc, cur], [])

4. Map（引用类型去重）：
const map = new Map(); arr.filter(item => !map.has(item.key) && map.set(item.key, true))

5. 对象 key：
arr.filter(item => !obj[item] && (obj[item] = true))

注意：Set 去重对 NaN 有效（Set 认为 NaN === NaN），但对引用类型按引用比较。

前提：数组必须有序。

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1); // 防溢出
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // 未找到
}

注意事项：
1. mid = left + (right - left) / 2 防止整数溢出
2. 循环条件 left <= right（等号取决于边界定义）
3. 更新边界 left = mid + 1 / right = mid - 1，避免死循环

变体：查找第一个等于、最后一个等于、第一个大于等于等。

1. flat()（最简单）：
arr.flat(Infinity)

2. 递归：
function flatten(arr) {
  return arr.reduce((acc, cur) =>
    Array.isArray(cur) ? acc.concat(flatten(cur)) : acc.concat(cur)
  , []);
}

3. 迭代（栈）：
function flatten(arr) {
  const stack = [...arr];
  const result = [];
  while (stack.length) {
    const item = stack.pop();
    Array.isArray(item) ? stack.push(...item) : result.push(item);
  }
  return result.reverse();
}

指定深度：arr.flat(depth)，depth 默认 1。

动态规划（DP）：将复杂问题拆分为重叠子问题，通过存储中间结果避免重复计算。

关键要素：
1. 最优子结构：问题的最优解包含子问题的最优解
2. 重叠子问题：子问题会被重复计算
3. 状态转移方程：描述子问题之间的关系

经典例题 — 爬楼梯：
每次爬 1 或 2 阶，到第 n 阶有多少种方法？
dp[i] = dp[i-1] + dp[i-2]（从 i-1 爬 1 阶或从 i-2 爬 2 阶）
function climbStairs(n) {
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) [a, b] = [b, a + b];
  return n === 1 ? 1 : b;
}

其他经典题：背包问题、最长公共子序列、零钱兑换。

迭代法：
function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

递归法：
function reverseList(head) {
  if (!head || !head.next) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

时间复杂度：O(n)，空间复杂度：迭代 O(1)，递归 O(n)。
变体：反转前 N 个、反转指定区间、K 个一组反转。

栈（Stack）：后进先出（LIFO），只在一端操作。
队列（Queue）：先进先出（FIFO），一端进另一端出。

用两个栈实现队列：
class MyQueue {
  stackIn = [];
  stackOut = [];
  push(x) { this.stackIn.push(x); }
  pop() {
    if (!this.stackOut.length) {
      while (this.stackIn.length) this.stackOut.push(this.stackIn.pop());
    }
    return this.stackOut.pop();
  }
  peek() { /* 类似 pop，但不移除 */ }
  empty() { return !this.stackIn.length && !this.stackOut.length; }
}

应用：栈 — 括号匹配、函数调用栈、撤销操作；队列 — BFS、任务调度、消息队列。