5道经典算法题

好的，我们来深入探讨一下前端开发面试中那些最经典、最核心的算法题目。

不同于后端或纯算法岗位，前端的算法面试更侧重于考察那些与日常工作场景紧密相关的问题。比如：处理树状结构（DOM、组件树）、应对高频事件、管理异步流程、高效处理数据等。因此，一个优秀的前端工程师不仅要懂“增删改查”，更要理解这些操作背后的效率和逻辑。

下面我将问题分为五大经典类别，每个类别下选择最具代表性的题目，并提供从问题分析、代码实现到场景应用的“一条龙”式彻底讲解。

---

类别一：数组与字符串 (Array & String) - 数据处理基石

这是最基础也是最高频的类别。前端每天都在和接口返回的数组、用户输入的字符串打交道。

经典题目：两数之和 (Two Sum)

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

示例:

输入: nums = [2, 7, 11, 15], target = 9

输出: [0, 1]

解释: 因为 nums[0] + nums[1] == 9，所以返回 [0, 1]。

为什么这道题对前端如此重要？

这道题考察的是最基本的数据查找和匹配能力。在实际业务中，我们经常需要：

• 在商品列表中找到价格能凑成某个优惠券满减金额的两个商品。

• 从两个不同的数据源（比如用户信息和订单信息）中，通过某个共同的 ID 找到关联项。

• 这道题的解法演进（从暴力到高效）能很好地体现一个工程师对时间复杂度的理解。

思路演进与代码详解

解法1：暴力枚举（不推荐，但应了解）

最直观的思路是，用两层循环，遍历所有可能的数字组合。

• 思路: 第一个指针 i 从头开始，第二个指针 j 从 i+1 开始，检查 nums[i] + nums[j] 是否等于 target。

• 时间复杂度: O(n2)，因为是嵌套循环。

• 空间复杂度: O(1)，没有使用额外的存储空间。

JavaScript

/**
 * 暴力解法 - O(n^2)
 * @param {number[]} nums 整数数组
 * @param {number} target 目标值
 * @returns {number[]} 两个数的下标
 */
function twoSum_bruteForce(nums, target) {
  // 外层循环，从第一个元素开始
  for (let i = 0; i < nums.length; i++) {
    // 内层循环，从外层循环的下一个元素开始，避免重复和对自己求和
    for (let j = i + 1; j < nums.length; j++) {
      // 检查两个数的和是否等于目标值
      if (nums[i] + nums[j] === target) {
        return [i, j]; // 找到后立即返回
      }
    }
  }
}

解法2：哈希表 / Map（最优解）

面试官期待的答案。我们可以通过空间换时间，将查找效率从 O(n) 降低到 O(1)。

• 思路: 遍历数组，对于每个元素 num，我们不再是向后查找，而是去一个“登记处”（哈希表）查询我们“需要”的那个数字 (target - num) 是否已经出现过。

  1. 创建一个 Map（或普通对象）来存储已经遍历过的数字及其下标。

  2. 遍历 nums 数组。

  3. 在遍历到 nums[i] 时，计算出我们需要的“另一半”：complement = target - nums[i]。

  4. 在 Map 中查找是否存在 complement。

  5. 如果存在，说明我们找到了配对，直接返回 map.get(complement) 和当前的下标 i。

  6. 如果不存在，就把当前的 nums[i] 和它的下标 i 存入 Map 中，供后续的数字进行查询。

• 时间复杂度: O(n)。我们只需要遍历数组一次。Map 的插入和查找操作平均时间复杂度都是 O(1)。

• 空间复杂度: O(n)。在最坏的情况下，我们需要把所有元素都存入 Map 中。

JavaScript

/**
 * 哈希表解法 - O(n)
 * @param {number[]} nums 整数数组
 * @param {number} target 目标值
 * @returns {number[]} 两个数的下标
 */
function twoSum(nums, target) {
  // 创建一个 Map，用于存储 { 数字: 下标 } 的键值对
  const map = new Map();

  // 仅需一次遍历
  for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
    // 计算我们需要寻找的“另一半”
    const complement = target - currentNum;

    // 检查 Map 中是否已经存在“另一半”
    if (map.has(complement)) {
      // 如果存在，说明找到了配对
      // complement 的下标已经存在 map 中，currentNum 的下标就是当前的 i
      return [map.get(complement), i];
    }

    // 如果没找到，就把当前数字和它的下标存入 Map
    // 供后续的元素进行配对查询
    map.set(currentNum, i);
  }

  // 如果遍历完都没有找到，可以根据题目要求返回空数组或抛出错误
  // (题目假设总会有一个解，所以这里理论上不会执行到)
}

// --- 测试 ---
const nums = [2, 7, 11, 15];
const target = 9;
console.log(`最优解找到的下标: [${twoSum(nums, target)}]`); // 输出: 最优解找到的下标: [0,1]

彻底讲明白: 核心思想是用哈希表将“查找”这个耗时的操作变成近乎瞬时的操作。当我们遍历到第 i 个元素时，我们不再需要向后遍历 n-i 次去寻找配对，而是直接问哈希表：“嘿，我需要的那个数你见过吗？” 这个“问”的动作，时间成本是 O(1)。这就是典型的“空间换时间”策略，在前端性能优化中非常常见（例如，缓存计算结果）。

---

类别二：树与 DOM (Tree & DOM) - 前端核心战场

DOM 本身就是一棵树，React/Vue 的组件结构也是一棵树。因此，树的遍历和操作是前端工程师的必备技能。

经典题目：树的深度优先遍历 (DFS) 与广度优先遍历 (BFS)

题目描述

给定一个树状结构（比如一个嵌套的对象，或者真实的 DOM 树），实现两种遍历方式：

1. 深度优先遍历 (DFS, Depth-First Search): 尽可能深地搜索树的分支。

2. 广度优先遍历 (BFS, Breadth-First Search): 又叫层次遍历，从上到下，从左到右逐层访问节点。

为什么这道题对前端如此重要？

• DOM 操作: querySelectorAll 的底层实现就类似于树的遍历。当你需要寻找页面上所有 class 为 highlight 的 div 元素时，就是在进行树的遍历和筛选。

• 组件通信: 在 React 或 Vue 中，有时需要从父组件向深层子组件传递信息（Context API），或者反向通信，这都涉及到组件树的遍历逻辑。

• 数据处理: 从 API 获取的 JSON 数据经常是嵌套的树状结构，你需要遍历这棵树来提取或转换数据。

代码详解

我们用一个简单的对象来模拟树结构：

JavaScript

const tree = {
  value: 'A',
  children: [
    {
      value: 'B',
      children: [
        { value: 'D', children: [] },
        { value: 'E', children: [] }
      ]
    },
    {
      value: 'C',
      children: [
        { value: 'F', children: [] }
      ]
    }
  ]
};

解法1：深度优先遍历 (DFS) - 递归实现

递归是实现 DFS 最自然、最简洁的方式。

• 思路:

  1. 定义一个函数 dfs(node)，接收一个节点作为参数。

  2. 首先处理当前节点（比如，打印它的值）。

  3. 然后遍历当前节点的 children 数组。

  4. 对每个 child，递归调用 dfs(child)。

• 特点: 实现简单，代码易读。但如果树的层级非常深，可能导致调用栈溢出（Stack Overflow）。

JavaScript

/**
 * 深度优先遍历 (DFS) - 递归实现
 * @param {object} node 树节点
 * @param {Array} result 存储遍历结果的数组
 */
function dfs(node, result = []) {
  if (!node) return; // 递归的基线条件

  // 1. 处理当前节点
  result.push(node.value);
  console.log(`DFS访问: ${node.value}`);

  // 2. 递归遍历子节点
  if (node.children && node.children.length > 0) {
    for (const child of node.children) {
      dfs(child, result); // 对每个子节点递归调用
    }
  }

  return result;
}

// --- 测试 DFS ---
console.log('--- 开始深度优先遍历 ---');
const dfsResult = dfs(tree);
console.log(`DFS 最终结果: [${dfsResult.join(', ')}]`); // A, B, D, E, C, F

解法2：广度优先遍历 (BFS) - 队列实现

BFS 不能简单地用递归实现，它需要一个辅助的数据结构——队列（Queue）。

• 思路:

  1. 创建一个队列，并把根节点放进去。

  2. 当队列不为空时，执行循环：

     a. 从队列头部取出一个节点 currentNode。

     b. 处理 currentNode（比如，打印它的值）。

     c. 将 currentNode 的所有子节点依次加入队列的尾部。

  3. 重复步骤 2，直到队列为空。

• 特点: 能保证按层级顺序访问。实现上比递归 DFS 稍复杂，但不会有栈溢出的风险。可以用来找最短路径。

JavaScript

/**
 * 广度优先遍历 (BFS) - 队列实现
 * @param {object} node 树节点
 * @returns {Array} 遍历结果数组
 */
function bfs(node) {
  if (!node) return [];

  const queue = [node]; // 1. 创建队列，放入根节点
  const result = [];

  // 2. 当队列不为空时循环
  while (queue.length > 0) {
    // a. 从队首取出一个节点
    const currentNode = queue.shift(); // shift() 方法模拟出队

    // b. 处理当前节点
    result.push(currentNode.value);
    console.log(`BFS访问: ${currentNode.value}`);

    // c. 将其所有子节点入队
    if (currentNode.children && currentNode.children.length > 0) {
      for (const child of currentNode.children) {
        queue.push(child); // push() 方法模拟入队
      }
    }
  }

  return result;
}

// --- 测试 BFS ---
console.log('--- 开始广度优先遍历 ---');
const bfsResult = bfs(tree);
console.log(`BFS 最终结果: [${bfsResult.join(', ')}]`); // A, B, C, D, E, F

彻底讲明白:

• DFS 的精髓是“一条路走到黑，走不通再回头”。它的数据结构是栈 (Stack)。对于递归实现，这个栈就是函数的调用栈。你也可以用一个真实的栈来迭代实现 DFS。

• BFS 的精髓是“一层一层地毯式搜索”。它的数据结构是队列 (Queue)。它能保证最先被访问的节点的邻居也一定比后被访问的节点的邻居要早被访问。这使得 BFS 成为在无权图中寻找最短路径的不二之选（例如，找到从A节点到B节点最少需要经过几层）。

---

类别三：异步编程 (Asynchronous Programming) - 前端命脉

JavaScript 是单线程的，但浏览器环境是事件驱动的。处理网络请求、定时器、用户交互等异步任务是前端的日常。

经典题目：实现 Promise.all

题目描述

Promise.all(promises) 方法接收一个 promise 的可迭代对象（比如数组），并返回一个单独的 Promise。这个返回的 Promise 会在所有输入的 promise 都兑现（fulfilled）后兑现，其值为一个包含所有兑现值的数组。如果输入的任何一个 promise 被拒绝（rejected），则返回的 Promise 会立即被拒绝，并带有第一个被拒绝的 promise 的原因。

请你实现一个功能类似的 myPromiseAll 函数。

为什么这道题对前端如此重要？

• 并发请求: 页面初始化时，我们经常需要同时请求多个接口（比如用户信息、商品列表、配置信息），并在所有数据都返回后再渲染页面。Promise.all 是实现这一需求的核心工具。

• 理解 Promise: 能否写出 Promise.all 是检验面试者是否真正理解 Promise 状态、执行流程和错误处理的“试金石”。

代码详解

• 核心思路:

  1. myPromiseAll 函数返回一个新的 Promise。

  2. 它需要一个计数器 count 来记录已完成的 promise 数量，以及一个 results 数组来按顺序存储结果。

  3. 遍历输入的 promises 数组。对于每个 promise：

     • 使用 .then() 来处理它。

     • 当 promise 成功时，将结果存入 results 数组的对应位置（而不是 push，因为 promise 完成顺序不确定），并将计数器 count 加一。

     • 检查 count 是否等于 promises 的总数。如果是，说明所有 promise 都已完成，此时 resolve 新 Promise，并传入 results 数组。

  4. 如果遍历过程中的任何一个 promise 失败了（进入 .catch 或 .then 的第二个参数），则立即 reject 新 Promise，并把这个错误原因传出去。

JavaScript

/**
 * 实现 Promise.all
 * @param {Array<Promise>} promises Promise 数组
 * @returns {Promise}
 */
function myPromiseAll(promises) {
  // 1. 返回一个新的 Promise
  return new Promise((resolve, reject) => {
    // 如果传入的不是可迭代对象，或者为空，需要做边界处理
    if (!promises || typeof promises[Symbol.iterator] !== 'function') {
      return reject(new TypeError('Argument must be iterable'));
    }

    const promisesArray = Array.from(promises); // 确保是数组
    const n = promisesArray.length;

    // 如果传入空数组，应立即兑现
    if (n === 0) {
      return resolve([]);
    }

    const results = new Array(n); // 存放结果的数组，预分配长度
    let resolvedCount = 0;        // 已完成的 promise 计数器

    // 3. 遍历 promises 数组
    promisesArray.forEach((promise, index) => {
      // Promise.resolve() 可以处理传入的值不是 promise 的情况
      Promise.resolve(promise)
        .then(
          // promise 成功的回调
          (value) => {
            results[index] = value; // 按原始顺序存放结果
            resolvedCount++;        // 计数器加一

            // 检查是否所有 promise 都已完成
            if (resolvedCount === n) {
              resolve(results); // 如果是，兑现我们自己的 promise
            }
          },
          // promise 失败的回调
          (reason) => {
            // 4. 一旦有任何一个 promise 失败，立即拒绝
            reject(reason);
          }
        );
    });
  });
}

// --- 测试 ---
function createDelayedPromise(value, delay, shouldReject = false) {
  return new Promise((resolve, reject) => {
    setTimeout(() => {
      console.log(`Promise with value ${value} finished.`);
      if (shouldReject) {
        reject(`Error from promise ${value}`);
      } else {
        resolve(value);
      }
    }, delay);
  });
}

const p1 = createDelayedPromise(1, 1000);
const p2 = createDelayedPromise(2, 500);
const p3 = createDelayedPromise(3, 1500);

console.log("--- 测试成功场景 ---");
myPromiseAll([p1, p2, p3])
  .then(results => {
    console.log("All promises resolved:", results); // 预期: [1, 2, 3] (顺序保持不变)
  })
  .catch(error => {
    console.error("Caught an error:", error);
  });

const p4 = createDelayedPromise(4, 800, true); // 这个会失败
setTimeout(() => {
  console.log("\n--- 测试失败场景 ---");
  myPromiseAll([p1, p4, p3])
    .then(results => {
      console.log("All promises resolved:", results);
    })
    .catch(error => {
      console.error("Caught an error:", error); // 预期: Caught an error: Error from promise 4
    });
}, 2000);

彻底讲明白: 这道题的关键点在于处理并发、顺序和失败。

• 并发: forEach 循环是同步的，它会立即启动所有 promise 的执行，这就实现了并发。

• 顺序: 结果必须与输入 promises 的顺序一致。所以我们不能用 push，而是要根据 index 存放到预先创建好的 results 数组的指定位置 results[index] = value。

• 失败: Promise.all 的特性是“一败俱败”。只要有一个 promise 被 reject，整个 myPromiseAll 返回的 Promise 就立刻被 reject。我们的代码通过在 .then 的第二个参数或 .catch 中直接调用 reject 来实现这一点。

---

类别四：性能与优化 (Performance & Optimization) - 体现工程能力

一个功能跑得起来和跑得好是两回事。性能优化相关的算法题能直接体现面试者的工程素养。

经典题目：实现防抖 (Debounce) 和节流 (Throttle)

题目描述

编写两个高阶函数：debounce 和 throttle。

• 防抖 (Debounce): 在事件被触发 n 秒后再执行回调，如果在这 n 秒内又被触发，则重新计时。

• 节流 (Throttle): 规定在一个单位时间内，只能触发一次函数。如果这个单位时间内触发多次函数，只有一次生效。

为什么这道题对前端如此重要？

这是前端性能优化的“标配”技能。

• 防抖应用:

  • 搜索框输入建议：用户停止输入一小段时间后再发请求，而不是每输入一个字母都发请求。

  • 窗口 resize 事件：只在用户调整完窗口大小后才重新计算布局。

• 节流应用:

  • scroll 事件：监听页面滚动，但每隔 200ms 才触发一次回调（比如计算元素是否进入视口）。

  • 鼠标 mousemove 事件：实现拖拽功能时，不需要对每 1px 的移动都做响应。

代码详解

实现防抖 (Debounce)

• 思路: 利用定时器 setTimeout。每次触发事件时，都先清除上一个定时器，然后设置一个新的定时器。只有当最后一次触发后，定时器能够完整地执行完，回调函数才会被调用。

JavaScript

/**
 * 防抖函数 (高阶函数)
 * @param {Function} func 需要防抖的函数
 * @param {number} delay 延迟时间 (ms)
 * @returns {Function} 封装后的新函数
 */
function debounce(func, delay) {
  let timer = null; // 闭包变量，用于存储定时器ID

  // 返回一个新函数
  return function(...args) {
    const context = this; // 保存 this 上下文

    // 如果存在定时器，就清除它
    if (timer) {
      clearTimeout(timer);
    }

    // 设置一个新的定时器
    timer = setTimeout(() => {
      // 当定时器触发时，执行真正的函数
      // 并将参数和 this 传递过去
      func.apply(context, args);
      timer = null; // 执行完后可以清空timer
    }, delay);
  };
}

// --- 测试防抖 ---
const handleInput = (e) => {
  console.log('向服务器发送请求:', e.target.value);
};

const debouncedInputHandler = debounce(handleInput, 500);

// 模拟在输入框中快速输入
// document.getElementById('my-input').addEventListener('input', debouncedInputHandler);
// 在node环境中模拟:
console.log("--- 测试防抖 ---");
console.log("快速输入 'a', 'ab', 'abc'");
debouncedInputHandler({ target: { value: 'a' } });
debouncedInputHandler({ target: { value: 'ab' } });
debouncedInputHandler({ target: { value: 'abc' } });
// 预期的输出是：500ms后，只打印一次 "向服务器发送请求: abc"

实现节流 (Throttle)

• 思路: 利用一个标志位 inThrottle (或 canRun)。当函数被触发时，检查标志位。如果可以运行，则执行函数，并立刻将标志位置为“不可运行”，然后开启一个定时器，在 delay 时间后，再将标志位恢复为“可运行”。

JavaScript

/**
 * 节流函数 (高阶函数)
 * @param {Function} func 需要节流的函数
 * @param {number} delay 间隔时间 (ms)
 * @returns {Function} 封装后的新函数
 */
function throttle(func, delay) {
  let inThrottle = false; // 节流阀状态
  let lastArgs = null;    // 可选：用于保存最后一次的参数，以便在节流结束后执行一次最新的调用

  // 返回一个新函数
  return function(...args) {
    const context = this;

    // 如果节流阀是关闭的 (即正在冷却中)
    if (inThrottle) {
      // lastArgs = args; // 可选：保存参数
      return;
    }

    // 立即执行
    func.apply(context, args);
    inThrottle = true; // 关闭节流阀

    // 设置定时器，在 delay 时间后打开节流阀
    setTimeout(() => {
      inThrottle = false;
      // if (lastArgs) { // 可选：如果希望停止触发后还能执行一次最新调用
      //   func.apply(context, lastArgs);
      //   lastArgs = null;
      // }
    }, delay);
  };
}

// --- 测试节流 ---
let scrollCount = 0;
const handleScroll = () => {
  scrollCount++;
  console.log(`触发滚动事件，总次数: ${scrollCount}`);
};

const throttledScrollHandler = throttle(handleScroll, 1000);

// 模拟高频滚动
console.log("\n--- 测试节流 ---");
console.log("模拟2秒内高频触发滚动...");
const intervalId = setInterval(throttledScrollHandler, 100); // 每100ms触发一次

setTimeout(() => {
  clearInterval(intervalId);
  console.log("停止触发。");
  // 预期输出：大约在 0ms, 1000ms 时各打印一次日志，总共2次左右
}, 2000);

彻底讲明白:

• 防抖的核心是等待和重置。它关心的是“最后一次”操作。就像电梯关门，只要有人按开门按钮，关门计时就重置。

• 节流的核心是锁定和解锁。它关心的是“固定频率”。就像技能冷却，放了一次技能后，必须等 CD 转好才能放第二次。

• 选择哪个取决于业务需求：如果你只关心最终结果（比如用户输完的最终文本），用防抖；如果你需要以固定频率对过程进行响应（比如滚动时的动画），用节流。

---

类别五：综合应用 - Virtual DOM Diff

这是前几类知识的集大成者，也是现代前端框架的灵魂。能讲明白 Diff 算法，说明你对前端的渲染机制有非常深刻的理解。

经典题目：简化版的 Virtual DOM Diff 算法

题目描述

请描述 Virtual DOM 的 Diff 算法的核心思想，并用代码模拟一个简化版的 patch(oldVNode, newVNode) 函数，该函数能够找出两个虚拟节点树的差异，并生成一个描述这些差异的“补丁”对象。

简化假设:

1. 只考虑节点类型（tag）不同和文本内容（text）不同的情况。

2. 不考虑 props 的 diff。

3. 不考虑复杂的子节点移动，只考虑子节点列表的同级替换、删除和新增。

为什么这道题对前端如此重要？

• 框架基石: 这是 React、Vue 等框架实现高性能渲染的核心。理解它，就等于理解了为什么我们不再需要手动操作繁琐且昂贵的 DOM。

• 抽象思维: VDOM 和 Diff 算法是前端领域一个非常成功的抽象设计，它将 UI 描述（VNode）和 UI 实现（DOM）解耦，考察的是工程师的抽象和设计能力。

思路与代码详解

核心思想

1. 同级比较: Diff 算法是逐层比较的，不会跨层级移动节点。如果 div 下的 p 变成了 section 下的 p，它会被当做“删除旧 p”和“新增新 p”来处理。

2. 类型判断:

   • 如果新旧节点类型不同（比如 div 变成了 p），直接替换整个旧节点及其子树，不做后续比较。

   • 如果都是文本节点，比较文本内容是否变化。

3. 子节点比较 (Key 的重要性):

   • 这是最复杂的部分。当父节点相同时，需要比较它们的子节点列表。

   • 为了高效地识别出哪些子节点是新增、删除或移动的，现代框架引入了 key。通过 key，我们可以快速匹配新旧列表中的同一个节点，从而避免不必要的重建，只需移动即可。

   • 在我们的简化版中，我们先不实现复杂的 key 匹配，只做一个简单的对比。

代码实现

JavaScript

// 定义 VNode 的基本结构
function h(tag, props, children) {
  return { tag, props, children };
}

// 定义补丁类型
const PatchType = {
  REPLACE: 'REPLACE', // 替换节点
  TEXT: 'TEXT',       // 修改文本
  PROPS: 'PROPS',     // 修改属性 (本次简化版不实现)
  REORDER: 'REORDER'  // 子节点重排序 (本次简化版不实现)
};

/**
 * 比较两个 VNode 并生成补丁对象
 * @param {object | undefined} oldVNode
 * @param {object | undefined} newVNode
 * @returns {object | undefined} patch object
 */
function diff(oldVNode, newVNode) {
  // Case 1: 新节点不存在，说明是删除
  if (!newVNode) {
    return { type: PatchType.REPLACE, node: null };
  }

  // Case 2 & 3: 旧节点不存在，或者节点类型/标签不同，都是替换
  if (!oldVNode || oldVNode.tag !== newVNode.tag) {
    // 在真实场景中，如果 oldVNode 和 newVNode 都是文本节点，
    // 即使 tag 都是 undefined，也需要比较内容
    if (typeof oldVNode !== 'string' && typeof newVNode !== 'string' && oldVNode.tag !== newVNode.tag) {
       return { type: PatchType.REPLACE, node: newVNode };
    }
  }

  // Case 4: 都是文本节点，但内容不同
  if (typeof oldVNode === 'string' && typeof newVNode === 'string') {
    if (oldVNode !== newVNode) {
      return { type: PatchType.TEXT, text: newVNode };
    } else {
      return undefined; // 文本相同，无变化
    }
  }

  // 如果执行到这里，说明 oldVNode 和 newVNode 的 tag 相同
  // 此时需要比较它们的子节点
  const patches = {};
  const childrenPatches = diffChildren(oldVNode.children, newVNode.children);
  if (Object.keys(childrenPatches).length > 0) {
    // 我们用一个简化的方式来表示子节点的 patch
    patches.children = childrenPatches;
  }
  
  // 如果 patches 对象不为空，则返回
  if(Object.keys(patches).length > 0) {
    return patches;
  }
  
  return undefined; // 无任何变化
}


/**
 * 比较子节点列表
 * @param {Array} oldChildren
 * @param {Array} newChildren
 * @returns {object} patches for children
 */
function diffChildren(oldChildren, newChildren) {
    const patches = {};
    const maxLen = Math.max(oldChildren.length, newChildren.length);
    for (let i = 0; i < maxLen; i++) {
        const childPatch = diff(oldChildren[i], newChildren[i]);
        if (childPatch) {
            patches[i] = childPatch;
        }
    }
    return patches;
}


// --- 测试 ---
const oldTree = h('div', { id: 'container' }, [
  h('p', {}, ['Hello']),
  h('ul', {}, [
    h('li', {}, ['Item 1']),
    h('li', {}, ['Item 2'])
  ])
]);

const newTree = h('div', { id: 'container' }, [
  h('h1', {}, ['Hi']), // p -> h1 (REPLACE)
  h('ul', {}, [
    h('li', {}, ['Item 1']),
    h('li', {}, ['Item B']) // Item 2 -> Item B (TEXT)
  ]),
  h('span', {}, ['A new span']) // 新增 (REPLACE null)
]);


const patches = diff(oldTree, newTree);
console.log('--- Virtual DOM Diff Patches ---');
console.log(JSON.stringify(patches, null, 2));

/*
预期输出:
{
  "children": {
    "0": { // 第一个子节点 (p -> h1)
      "type": "REPLACE",
      "node": { "tag": "h1", "props": {}, "children": ["Hi"] }
    },
    "1": { // 第二个子节点 (ul)
      "children": {
        "1": { // ul 的第二个子节点 (li)
          "children": {
            "0": { // li 的文本节点
              "type": "TEXT",
              "text": "Item B"
            }
          }
        }
      }
    },
    "2": { // 新增的第三个子节点 (span)
      "type": "REPLACE",
      "node": { "tag": "span", "props": {}, "children": ["A new span"] }
    }
  }
}
*/

彻底讲明白:

这个简化版的 diff 函数递归地遍历了新旧两棵 VDOM 树。

1. 它返回一个 patches 对象，这个对象的结构模仿了原 VDOM 树的结构。patches 对象只在有差异的地方记录差异信息。

2. 在真实的 patch 过程中，会有一个独立的函数（比如 applyPatches(domRoot, patches)），它会拿着这个 patches 对象去对真实的 DOM 进行最小化的操作。例如，看到 type: 'REPLACE'，它就知道调用 parentElement.replaceChild()；看到 type: 'TEXT'，它就知道修改 node.textContent。

3. 关键点: diff 过程本身不操作 DOM，它只是一个纯粹的 JavaScript 对象比较过程，因此速度非常快。昂贵的操作被推迟到最后一步，并且只执行必要的部分。这就是 VDOM 提升性能的秘密。在面试中，能把这一点（计算与执行分离）讲清楚，会非常加分。

---

总结与建议

以上五个类别的题目覆盖了前端开发中从数据处理、页面渲染、异步控制到性能优化的核心环节。它们之所以经典，是因为它们不仅仅是算法题，更是对前端工程师日常工作的高度抽象和提炼。

最好的准备方式是：

1. 理解而非背诵: 理解每个问题背后的“为什么”，它解决了什么实际场景的问题。

2. 动手编码: 亲手把每个题目敲一遍，并且尝试不同的解法，比较它们的优劣。

3. 举一反三:

   • Promise.all 会了，那 Promise.race、Promise.any, Promise.allSettled 呢？

   • 会了防抖和节流，能实现一个带立即执行选项的 debounce(func, delay, immediate) 吗？

   • Diff 算法懂了，能说说 key 的作用是什么吗？为什么不建议用 index 作为 key？

当你能将这些算法题与实际的前端工作场景联系起来，并清晰地阐述其原理、复杂度以及多种解法时，你就已经具备了优秀前端工程师的思维深度。