Skip to main content

常规算法

前端算法面试题通常围绕数据结构、算法逻辑、性能优化等方向展开，以下是不同难度和类型的经典题目及解析，帮助你系统备考：

一、基础数据结构类​

1. 数组相关​

题目：移除数组中的重复元素（LeetCode 26）
示例：输入 nums = [1,1,2]，输出 2，数组变为 [1,2]（顺序不影响，返回长度即可）。
思路：

  • 双指针法：i 指向当前不重复子数组的末尾，j 遍历数组。若 nums[i] !== nums[j]，则 i++ 并将 nums[j] 赋值给 nums[i]。
    代码：
function removeDuplicates(nums) {
  if (!nums.length) return 0;
  let i = 0;
  for (let j = 1; j < nums.length; j++) {
    if (nums[i] !== nums[j]) {
      i++;
      nums[i] = nums[j];
    }
  }
  return i + 1;
}

2. 链表操作​

题目：反转链表（LeetCode 206）
示例：输入 1->2->3->4->5，输出 5->4->3->2->1。
思路：

  • 迭代法：维护三个指针 prev（前一个节点）、curr（当前节点）、next（下一个节点），每次将 curr.next 指向 prev，并更新指针位置。
    代码：
function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

二、算法逻辑类​

1. 排序与搜索​

题目：二分查找（LeetCode 704）
示例：在有序数组 [-1,0,3,5,9,12] 中查找 9，返回索引 4。
思路：

  • 确定左边界 left 和右边界 right，每次取中点 mid 比较目标值，若 nums[mid] < target，则 left = mid + 1，否则 right = mid - 1。
    代码：
function search(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

2. 动态规划​

题目：爬楼梯（LeetCode 70）
示例：爬 n=3 阶楼梯，有 3 种方法（1+1+1，1+2，2+1）。
思路：

  • 状态定义：dp[i] 表示爬 i 阶楼梯的方法数。
  • 转移方程：dp[i] = dp[i-1] + dp[i-2]（最后一步爬1阶或2阶）。
  • 初始条件：dp[1]=1，dp[2]=2。
    代码：
function climbStairs(n) {
  if (n <= 2) return n;
  let dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[n];
}

三、高频场景类​

1. 字符串处理​

题目：最长回文子串（LeetCode 5）
示例：输入 s = "babad"，输出 "bab" 或 "aba"。
思路：

  • 中心扩展法：遍历每个字符作为回文中心，向左右扩展，记录最长回文子串。
    代码：
function longestPalindrome(s) {
  if (!s || s.length < 1) return "";
  let start = 0, end = 0;
  
  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (right - left > end - start) {
        start = left;
        end = right;
      }
      left--;
      right++;
    }
  }
  
  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i);       // 奇数长度回文
    expandAroundCenter(i, i + 1);   // 偶数长度回文
  }
  return s.substring(start, end + 1);
}

2. 哈希表应用​

题目：两数之和（LeetCode 1）
示例：输入 nums = [2,7,11,15]，target=9，输出 [0,1]。
思路：

  • 用哈希表存储值到索引的映射，遍历数组时检查 target - nums[i] 是否已存在于表中。
    代码：
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}

四、性能优化类​

1. 数组去重（进阶）​

题目：去除数组重复元素，要求：

  • 保持原顺序；
  • 支持复杂数据类型（如对象）。
    思路：
  • 简单类型：用 Set 去重后转数组；
  • 复杂类型：用 Map 记录唯一标识（如JSON字符串）。
    代码：
function unique(arr) {
  if (!Array.isArray(arr)) return [];
  return arr.reduce((res, item) => {
    // 转为字符串避免引用类型问题
    const key = JSON.stringify(item);
    if (!res.map(it => JSON.stringify(it)).includes(key)) {
      res.push(item);
    }
    return res;
  }, []);
}

2. 节流与防抖（实际应用）​

题目：实现 debounce（防抖）和 throttle（节流）函数。
思路：

  • 防抖：多次触发事件时，只执行最后一次，延迟期间若再次触发则重新计时。
  • 节流：控制事件在一定时间内只执行一次，如滚动事件高频触发时限制频率。
    代码：
// 防抖函数
function debounce(func, wait = 300) {
  let timeout;
  return function(...args) {
    const context = this;
    clearTimeout(timeout);
    timeout = setTimeout(() => {
      func.apply(context, args);
    }, wait);
  };
}

// 节流函数（时间戳版）
function throttle(func, wait = 300) {
  let previous = 0;
  return function(...args) {
    const now = Date.now();
    const context = this;
    if (now - previous > wait) {
      func.apply(context, args);
      previous = now;
    }
  };
}

五、面试高频技巧​

  1. 解题步骤：

    • 明确输入输出和边界条件（如空数组、单元素等）；
    • 先给出暴力解法，再优化（如O(n²)→O(n)）；
    • 用例子验证逻辑（如爬楼梯n=1,2,3的情况）。

  2. 空间与时间复杂度：

    • 数组遍历通常O(n)，嵌套循环O(n²)；
    • 哈希表查询O(1)，排序O(n log n)。

  3. 常见陷阱：

    • 数组索引越界（如二分查找的left <= right）；
    • 引用类型比较（如对象去重需转字符串）；
    • 异步场景下的算法应用（如防抖处理API请求）。

六、扩展练习​

  • 中等难度：合并两个有序链表（LeetCode 21）、寻找缺失的数字（LeetCode 268）；
  • 困难难度：括号生成（LeetCode 22）、单词搜索（LeetCode 79）；
  • 前端特色：虚拟DOM Diff算法（双指针比较新旧节点）、数组扁平化（递归+reduce）。