前端中的常用算法：从数据结构到性能优化

 1// 方法1：使用 Set（最简单，但会丢失对象引用）
 2function unique1(arr) {
 3  return [...new Set(arr)];
 4}
 5
 6// 方法2：使用 filter + indexOf
 7function unique2(arr) {
 8  return arr.filter((item, index) => arr.indexOf(item) === index);
 9}
10
11// 方法3：使用 reduce
12function unique3(arr) {
13  return arr.reduce((acc, item) => {
14    if (!acc.includes(item)) {
15      acc.push(item);
16    }
17    return acc;
18  }, []);
19}
20
21// 方法4：对象去重（根据某个属性）
22function uniqueBy(arr, key) {
23  const seen = new Set();
24  return arr.filter(item => {
25    const value = item[key];
26    if (seen.has(value)) {
27      return false;
28    }
29    seen.add(value);
30    return true;
31  });
32}

 1// 方法1：使用 flat（ES2019）
 2function flatten1(arr) {
 3  return arr.flat(Infinity);
 4}
 5
 6// 方法2：递归
 7function flatten2(arr) {
 8  const result = [];
 9  for (const item of arr) {
10    if (Array.isArray(item)) {
11      result.push(...flatten2(item));
12    } else {
13      result.push(item);
14    }
15  }
16  return result;
17}
18
19// 方法3：使用 reduce
20function flatten3(arr) {
21  return arr.reduce((acc, item) => {
22    return acc.concat(Array.isArray(item) ? flatten3(item) : item);
23  }, []);
24}
25
26// 方法4：迭代（避免栈溢出）
27function flatten4(arr) {
28  const stack = [...arr];
29  const result = [];
30  while (stack.length > 0) {
31    const item = stack.pop();
32    if (Array.isArray(item)) {
33      stack.push(...item);
34    } else {
35      result.unshift(item);
36    }
37  }
38  return result;
39}

 1// 按条件分组
 2function groupBy(arr, fn) {
 3  return arr.reduce((acc, item) => {
 4    const key = typeof fn === 'function' ? fn(item) : item[fn];
 5    if (!acc[key]) {
 6      acc[key] = [];
 7    }
 8    acc[key].push(item);
 9    return acc;
10  }, {});
11}
12
13// 使用
14const users = [
15  { name: 'John', age: 20 },
16  { name: 'Jane', age: 25 },
17  { name: 'Bob', age: 20 }
18];
19
20groupBy(users, user => user.age);
21// { 20: [{ name: 'John', age: 20 }, { name: 'Bob', age: 20 }], 25: [{ name: 'Jane', age: 25 }] }

 1// 将数组分成指定大小的块
 2function chunk(arr, size) {
 3  const result = [];
 4  for (let i = 0; i < arr.length; i += size) {
 5    result.push(arr.slice(i, i + size));
 6  }
 7  return result;
 8}
 9
10// 使用
11chunk([1, 2, 3, 4, 5], 2); // [[1, 2], [3, 4], [5]]

 1// 交集
 2function intersection(arr1, arr2) {
 3  const set2 = new Set(arr2);
 4  return arr1.filter(item => set2.has(item));
 5}
 6
 7// 并集
 8function union(arr1, arr2) {
 9  return [...new Set([...arr1, ...arr2])];
10}
11
12// 差集（arr1 有但 arr2 没有的）
13function difference(arr1, arr2) {
14  const set2 = new Set(arr2);
15  return arr1.filter(item => !set2.has(item));
16}

 1function quickSort(arr) {
 2  if (arr.length <= 1) return arr;
 3  
 4  const pivot = arr[Math.floor(arr.length / 2)];
 5  const left = [];
 6  const middle = [];
 7  const right = [];
 8  
 9  for (const item of arr) {
10    if (item < pivot) {
11      left.push(item);
12    } else if (item > pivot) {
13      right.push(item);
14    } else {
15      middle.push(item);
16    }
17  }
18  
19  return [...quickSort(left), ...middle, ...quickSort(right)];
20}

 1function mergeSort(arr) {
 2  if (arr.length <= 1) return arr;
 3  
 4  const mid = Math.floor(arr.length / 2);
 5  const left = mergeSort(arr.slice(0, mid));
 6  const right = mergeSort(arr.slice(mid));
 7  
 8  return merge(left, right);
 9}
10
11function merge(left, right) {
12  const result = [];
13  let i = 0, j = 0;
14  
15  while (i < left.length && j < right.length) {
16    if (left[i] <= right[j]) {
17      result.push(left[i++]);
18    } else {
19      result.push(right[j++]);
20    }
21  }
22  
23  return result.concat(left.slice(i)).concat(right.slice(j));
24}

 1function heapSort(arr) {
 2  // 构建最大堆
 3  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
 4    heapify(arr, arr.length, i);
 5  }
 6  
 7  // 逐个取出堆顶元素
 8  for (let i = arr.length - 1; i > 0; i--) {
 9    [arr[0], arr[i]] = [arr[i], arr[0]];
10    heapify(arr, i, 0);
11  }
12  
13  return arr;
14}
15
16function heapify(arr, n, i) {
17  let largest = i;
18  const left = 2 * i + 1;
19  const right = 2 * i + 2;
20  
21  if (left < n && arr[left] > arr[largest]) {
22    largest = left;
23  }
24  
25  if (right < n && arr[right] > arr[largest]) {
26    largest = right;
27  }
28  
29  if (largest !== i) {
30    [arr[i], arr[largest]] = [arr[largest], arr[i]];
31    heapify(arr, n, largest);
32  }
33}

 1function binarySearch(arr, target) {
 2  let left = 0;
 3  let right = arr.length - 1;
 4  
 5  while (left <= right) {
 6    const mid = Math.floor((left + right) / 2);
 7    
 8    if (arr[mid] === target) {
 9      return mid;
10    } else if (arr[mid] < target) {
11      left = mid + 1;
12    } else {
13      right = mid - 1;
14    }
15  }
16  
17  return -1;
18}
19
20// 查找第一个大于等于 target 的位置
21function lowerBound(arr, target) {
22  let left = 0;
23  let right = arr.length;
24  
25  while (left < right) {
26    const mid = Math.floor((left + right) / 2);
27    if (arr[mid] < target) {
28      left = mid + 1;
29    } else {
30      right = mid;
31    }
32  }
33  
34  return left;
35}

 1// 图的 DFS
 2function dfs(graph, start, visited = new Set()) {
 3  visited.add(start);
 4  console.log(start);
 5  
 6  for (const neighbor of graph[start] || []) {
 7    if (!visited.has(neighbor)) {
 8      dfs(graph, neighbor, visited);
 9    }
10  }
11}
12
13// 迭代版本
14function dfsIterative(graph, start) {
15  const stack = [start];
16  const visited = new Set();
17  
18  while (stack.length > 0) {
19    const node = stack.pop();
20    if (!visited.has(node)) {
21      visited.add(node);
22      console.log(node);
23      
24      for (const neighbor of graph[node] || []) {
25        if (!visited.has(neighbor)) {
26          stack.push(neighbor);
27        }
28      }
29    }
30  }
31}

 1function bfs(graph, start) {
 2  const queue = [start];
 3  const visited = new Set([start]);
 4  
 5  while (queue.length > 0) {
 6    const node = queue.shift();
 7    console.log(node);
 8    
 9    for (const neighbor of graph[node] || []) {
10      if (!visited.has(neighbor)) {
11        visited.add(neighbor);
12        queue.push(neighbor);
13      }
14    }
15  }
16}

 1function kmpSearch(text, pattern) {
 2  const lps = computeLPS(pattern);
 3  let i = 0; // text 的索引
 4  let j = 0; // pattern 的索引
 5  
 6  while (i < text.length) {
 7    if (text[i] === pattern[j]) {
 8      i++;
 9      j++;
10    }
11    
12    if (j === pattern.length) {
13      return i - j; // 找到匹配
14    } else if (i < text.length && text[i] !== pattern[j]) {
15      if (j !== 0) {
16        j = lps[j - 1];
17      } else {
18        i++;
19      }
20    }
21  }
22  
23  return -1;
24}
25
26function computeLPS(pattern) {
27  const lps = new Array(pattern.length).fill(0);
28  let len = 0;
29  let i = 1;
30  
31  while (i < pattern.length) {
32    if (pattern[i] === pattern[len]) {
33      len++;
34      lps[i] = len;
35      i++;
36    } else {
37      if (len !== 0) {
38        len = lps[len - 1];
39      } else {
40        lps[i] = 0;
41        i++;
42      }
43    }
44  }
45  
46  return lps;
47}

 1function lcs(str1, str2) {
 2  const m = str1.length;
 3  const n = str2.length;
 4  const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
 5  
 6  for (let i = 1; i <= m; i++) {
 7    for (let j = 1; j <= n; j++) {
 8      if (str1[i - 1] === str2[j - 1]) {
 9        dp[i][j] = dp[i - 1][j - 1] + 1;
10      } else {
11        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
12      }
13    }
14  }
15  
16  // 回溯构建 LCS
17  let i = m, j = n;
18  const result = [];
19  while (i > 0 && j > 0) {
20    if (str1[i - 1] === str2[j - 1]) {
21      result.unshift(str1[i - 1]);
22      i--;
23      j--;
24    } else if (dp[i - 1][j] > dp[i][j - 1]) {
25      i--;
26    } else {
27      j--;
28    }
29  }
30  
31  return result.join('');
32}

 1function editDistance(str1, str2) {
 2  const m = str1.length;
 3  const n = str2.length;
 4  const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
 5  
 6  // 初始化
 7  for (let i = 0; i <= m; i++) {
 8    dp[i][0] = i;
 9  }
10  for (let j = 0; j <= n; j++) {
11    dp[0][j] = j;
12  }
13  
14  // 填充 dp 表
15  for (let i = 1; i <= m; i++) {
16    for (let j = 1; j <= n; j++) {
17      if (str1[i - 1] === str2[j - 1]) {
18        dp[i][j] = dp[i - 1][j - 1];
19      } else {
20        dp[i][j] = Math.min(
21          dp[i - 1][j] + 1,     // 删除
22          dp[i][j - 1] + 1,     // 插入
23          dp[i - 1][j - 1] + 1  // 替换
24        );
25      }
26    }
27  }
28  
29  return dp[m][n];
30}

 1class TreeNode {
 2  constructor(val) {
 3    this.val = val;
 4    this.left = null;
 5    this.right = null;
 6  }
 7}
 8
 9// 前序遍历（根-左-右）
10function preorderTraversal(root) {
11  if (!root) return [];
12  return [
13    root.val,
14    ...preorderTraversal(root.left),
15    ...preorderTraversal(root.right)
16  ];
17}
18
19// 中序遍历（左-根-右）
20function inorderTraversal(root) {
21  if (!root) return [];
22  return [
23    ...inorderTraversal(root.left),
24    root.val,
25    ...inorderTraversal(root.right)
26  ];
27}
28
29// 后序遍历（左-右-根）
30function postorderTraversal(root) {
31  if (!root) return [];
32  return [
33    ...postorderTraversal(root.left),
34    ...postorderTraversal(root.right),
35    root.val
36  ];
37}
38
39// 层序遍历（BFS）
40function levelOrderTraversal(root) {
41  if (!root) return [];
42  
43  const result = [];
44  const queue = [root];
45  
46  while (queue.length > 0) {
47    const level = [];
48    const size = queue.length;
49    
50    for (let i = 0; i < size; i++) {
51      const node = queue.shift();
52      level.push(node.val);
53      
54      if (node.left) queue.push(node.left);
55      if (node.right) queue.push(node.right);
56    }
57    
58    result.push(level);
59  }
60  
61  return result;
62}

 1// 深度优先遍历 DOM 树
 2function traverseDOM(node, callback) {
 3  callback(node);
 4  
 5  for (const child of node.children) {
 6    traverseDOM(child, callback);
 7  }
 8}
 9
10// 查找所有匹配选择器的元素
11function querySelectorAll(root, selector) {
12  const result = [];
13  
14  function matches(node, selector) {
15    // 简化的匹配逻辑（实际应该用浏览器 API）
16    return node.matches && node.matches(selector);
17  }
18  
19  function traverse(node) {
20    if (matches(node, selector)) {
21      result.push(node);
22    }
23    
24    for (const child of node.children) {
25      traverse(child);
26    }
27  }
28  
29  traverse(root);
30  return result;
31}

 1function diff(oldTree, newTree) {
 2  const patches = {};
 3  let index = 0;
 4  
 5  walk(oldTree, newTree, index, patches);
 6  return patches;
 7}
 8
 9function walk(oldNode, newNode, index, patches) {
10  const currentPatches = [];
11  
12  if (!newNode) {
13    // 节点被删除
14    currentPatches.push({ type: 'REMOVE', index });
15  } else if (typeof oldNode === 'string' && typeof newNode === 'string') {
16    // 文本节点
17    if (oldNode !== newNode) {
18      currentPatches.push({ type: 'TEXT', content: newNode });
19    }
20  } else if (oldNode.type === newNode.type) {
21    // 相同类型的节点，比较属性和子节点
22    const attrs = diffAttrs(oldNode.props, newNode.props);
23    if (Object.keys(attrs).length > 0) {
24      currentPatches.push({ type: 'ATTR', attrs });
25    }
26    
27    diffChildren(oldNode.children, newNode.children, index, patches);
28  } else {
29    // 节点类型不同，直接替换
30    currentPatches.push({ type: 'REPLACE', newNode });
31  }
32  
33  if (currentPatches.length > 0) {
34    patches[index] = currentPatches;
35  }
36}
37
38function diffAttrs(oldAttrs, newAttrs) {
39  const patches = {};
40  
41  // 找出变化的属性
42  for (const key in newAttrs) {
43    if (oldAttrs[key] !== newAttrs[key]) {
44      patches[key] = newAttrs[key];
45    }
46  }
47  
48  // 找出被删除的属性
49  for (const key in oldAttrs) {
50    if (!(key in newAttrs)) {
51      patches[key] = undefined;
52    }
53  }
54  
55  return patches;
56}
57
58function diffChildren(oldChildren, newChildren, index, patches) {
59  let currentIndex = index;
60  
61  oldChildren.forEach((oldChild, i) => {
62    const newChild = newChildren[i];
63    currentIndex++;
64    walk(oldChild, newChild, currentIndex, patches);
65  });
66}

 1class LRUCache {
 2  constructor(capacity) {
 3    this.capacity = capacity;
 4    this.cache = new Map();
 5  }
 6  
 7  get(key) {
 8    if (this.cache.has(key)) {
 9      // 将访问的项移到末尾（最近使用）
10      const value = this.cache.get(key);
11      this.cache.delete(key);
12      this.cache.set(key, value);
13      return value;
14    }
15    return -1;
16  }
17  
18  put(key, value) {
19    if (this.cache.has(key)) {
20      // 更新已存在的项
21      this.cache.delete(key);
22    } else if (this.cache.size >= this.capacity) {
23      // 删除最久未使用的项（第一个）
24      const firstKey = this.cache.keys().next().value;
25      this.cache.delete(firstKey);
26    }
27    
28    this.cache.set(key, value);
29  }
30}

 1class LFUCache {
 2  constructor(capacity) {
 3    this.capacity = capacity;
 4    this.cache = new Map(); // key -> { value, frequency }
 5    this.freqMap = new Map(); // frequency -> Set of keys
 6    this.minFreq = 0;
 7  }
 8  
 9  get(key) {
10    if (!this.cache.has(key)) return -1;
11    
12    const item = this.cache.get(key);
13    this.updateFrequency(key);
14    return item.value;
15  }
16  
17  put(key, value) {
18    if (this.capacity === 0) return;
19    
20    if (this.cache.has(key)) {
21      this.cache.get(key).value = value;
22      this.updateFrequency(key);
23    } else {
24      if (this.cache.size >= this.capacity) {
25        this.evict();
26      }
27      
28      this.cache.set(key, { value, frequency: 1 });
29      this.addToFreqMap(key, 1);
30      this.minFreq = 1;
31    }
32  }
33  
34  updateFrequency(key) {
35    const item = this.cache.get(key);
36    const oldFreq = item.frequency;
37    item.frequency++;
38    
39    this.removeFromFreqMap(key, oldFreq);
40    this.addToFreqMap(key, oldFreq + 1);
41    
42    if (oldFreq === this.minFreq && (!this.freqMap.get(oldFreq) || this.freqMap.get(oldFreq).size === 0)) {
43      this.minFreq++;
44    }
45  }
46  
47  addToFreqMap(key, freq) {
48    if (!this.freqMap.has(freq)) {
49      this.freqMap.set(freq, new Set());
50    }
51    this.freqMap.get(freq).add(key);
52  }
53  
54  removeFromFreqMap(key, freq) {
55    const set = this.freqMap.get(freq);
56    if (set) {
57      set.delete(key);
58      if (set.size === 0) {
59        this.freqMap.delete(freq);
60      }
61    }
62  }
63  
64  evict() {
65    const keys = this.freqMap.get(this.minFreq);
66    const keyToRemove = keys.values().next().value;
67    keys.delete(keyToRemove);
68    this.cache.delete(keyToRemove);
69    
70    if (keys.size === 0) {
71      this.freqMap.delete(this.minFreq);
72    }
73  }
74}

 1function debounce(func, delay) {
 2  let timeoutId;
 3  return function (...args) {
 4    clearTimeout(timeoutId);
 5    timeoutId = setTimeout(() => func.apply(this, args), delay);
 6  };
 7}
 8
 9// 立即执行版本
10function debounceImmediate(func, delay) {
11  let timeoutId;
12  let immediate = true;
13  
14  return function (...args) {
15    if (immediate) {
16      func.apply(this, args);
17      immediate = false;
18    }
19    
20    clearTimeout(timeoutId);
21    timeoutId = setTimeout(() => {
22      immediate = true;
23    }, delay);
24  };
25}

 1// 时间戳版本
 2function throttle(func, delay) {
 3  let lastCall = 0;
 4  return function (...args) {
 5    const now = Date.now();
 6    if (now - lastCall >= delay) {
 7      lastCall = now;
 8      func.apply(this, args);
 9    }
10  };
11}
12
13// 定时器版本
14function throttleTimer(func, delay) {
15  let timeoutId;
16  return function (...args) {
17    if (!timeoutId) {
18      timeoutId = setTimeout(() => {
19        func.apply(this, args);
20        timeoutId = null;
21      }, delay);
22    }
23  };
24}
25
26// 结合版本（第一次和最后一次都会执行）
27function throttleBoth(func, delay) {
28  let timeoutId;
29  let lastCall = 0;
30  
31  return function (...args) {
32    const now = Date.now();
33    const remaining = delay - (now - lastCall);
34    
35    if (remaining <= 0) {
36      lastCall = now;
37      func.apply(this, args);
38    } else if (!timeoutId) {
39      timeoutId = setTimeout(() => {
40        lastCall = Date.now();
41        timeoutId = null;
42        func.apply(this, args);
43      }, remaining);
44    }
45  };
46}

 1function memoize(fn) {
 2  const cache = new Map();
 3  
 4  return function (...args) {
 5    const key = JSON.stringify(args);
 6    
 7    if (cache.has(key)) {
 8      return cache.get(key);
 9    }
10    
11    const result = fn.apply(this, args);
12    cache.set(key, result);
13    return result;
14  };
15}
16
17// 带过期时间的记忆化
18function memoizeWithTTL(fn, ttl = 60000) {
19  const cache = new Map();
20  
21  return function (...args) {
22    const key = JSON.stringify(args);
23    const cached = cache.get(key);
24    
25    if (cached && Date.now() - cached.timestamp < ttl) {
26      return cached.value;
27    }
28    
29    const result = fn.apply(this, args);
30    cache.set(key, {
31      value: result,
32      timestamp: Date.now()
33    });
34    
35    return result;
36  };
37}

1function shuffle(arr) {
2  const result = [...arr];
3  for (let i = result.length - 1; i > 0; i--) {
4    const j = Math.floor(Math.random() * (i + 1));
5    [result[i], result[j]] = [result[j], result[i]];
6  }
7  return result;
8}

 1function weightedRandom(items, weights) {
 2  const totalWeight = weights.reduce((sum, w) => sum + w, 0);
 3  let random = Math.random() * totalWeight;
 4  
 5  for (let i = 0; i < items.length; i++) {
 6    random -= weights[i];
 7    if (random <= 0) {
 8      return items[i];
 9    }
10  }
11  
12  return items[items.length - 1];
13}

 1// 最大子数组和
 2function maxSubarraySum(arr, k) {
 3  let maxSum = 0;
 4  let windowSum = 0;
 5  
 6  // 计算第一个窗口
 7  for (let i = 0; i < k; i++) {
 8    windowSum += arr[i];
 9  }
10  maxSum = windowSum;
11  
12  // 滑动窗口
13  for (let i = k; i < arr.length; i++) {
14    windowSum = windowSum - arr[i - k] + arr[i];
15    maxSum = Math.max(maxSum, windowSum);
16  }
17  
18  return maxSum;
19}