前端常见算法

#基础算法

基础算法是前端面试中最常考察的内容，主要包括排序算法和交换算法，这些算法能够有效考察应聘者的逻辑思维能力和代码实现能力。

#冒泡排序

冒泡排序是最基础的排序算法，时间复杂度为O(n²)，在最坏情况下需要进行n(n-1)/2次比较。其核心思想是相邻元素两两比较，如果顺序不对则交换位置，每一轮扫描后将当前最大的元素"冒泡"到末尾。冒泡排序是稳定的，因为它不会改变相等元素的相对顺序。JavaScript实现如下：

js
function bubbleSort(arr) {
  for (let i = 0, l = arr.length; i < l - 1; i++) {
    for (let j = 0; j < l - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

#快速排序

快速排序是基于分治策略的高效排序算法，平均时间复杂度为O(n log n)，最坏情况下为O(n²)。其核心思想是选取基准元素，将数组分为小于基准和大于基准的两部分，然后递归排序子数组。快速排序是不稳定的，但在实际应用中效率极高。JavaScript实现如下：

js
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = arr.filter(item => item < pivot);
  const middle = arr.filter(item => item === pivot);
  const right = arr.filter(item => item > pivot);
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

#插入排序

插入排序也是一种基础排序算法，时间复杂度为O(n²)，但在数据基本有序时效率较高。其核心思想是将未排序的元素插入到已排序的正确位置。JavaScript实现如下：

js
function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

#希尔排序

希尔排序是插入排序的一种优化，通过分组插入排序减少元素的移动次数。其时间复杂度取决于增量序列的选择，通常为O(n log n)到O(n²)之间。希尔排序的核心是选择合适的增量序列，将数组分为多个子组进行插入排序，然后逐渐减小增量直到为1。JavaScript实现如下：

js
function shellSort(arr) {
  let len = arr.length;
  let gap = Math.floor(len / 2); // 初始增量

  while (gap > 0) {
    for (let i = gap; i < len; i++) {
      let temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 2); // 减少增量
  }
  return arr;
}

#归并排序

归并排序是一种分治算法，将数组递归地分成小数组，然后合并这些已排序的小数组。其时间复杂度为O(n log n)，空间复杂度为O(n)，是稳定的排序算法。JavaScript实现如下：

js
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}

#数组操作算法

#数组去重

数组去重是前端面试中最基础且高频的算法题，有多种实现方法：

js
// 使用Set去重
function uniqueWithSet(arr) {
  return [...new Set(arr)];
}

// 使用Map去重
function uniqueWithMap(arr) {
  const map = new Map();
  return arr.filter(item => {
    if (!map.has(item)) {
      map.set(item, true);
      return true;
    }
    return false;
  });
}

// 双指针法去重
function uniqueWithTwoPointers(arr) {
  if (arr.length === 0) return arr;
  let i = 0;
  for (let j = 1; j < arr.length; j++) {
    if (arr[j] !== arr[i]) {
      i++;
      arr[i] = arr[j];
    }
  }
  return arr.slice(0, i + 1);
}

#两数之和

两数之和是LeetCode中的经典问题，考察哈希表的使用和空间换时间的优化思路：

js
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 [];
}

#三数之和

三数之和是两数之和的扩展，考察双指针法和去重逻辑：

js
function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // 去重
    let left = i + 1, right = nums.length - 1, target = -nums[i];
    while (left < right) {
      const sum = nums[left] + nums[right];
      if (sum === target) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++; // 去重
        while (left < right && nums[right] === nums[right - 1]) right++; // 去重
        left++;
        right--;
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}

#最大子数组和

最大子数组和考察动态规划思想，时间复杂度为O(n)：

js
function maxSubArray(nums) {
  let currentSum = nums[0];
  let maxSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

#和为k的子数组

和为k的子数组考察前缀和与哈希表的结合使用：

js
function subarraySum(nums, k) {
  const map = new Map([[0, 1]]); // 前缀和为0的情况
  let sum = 0, count = 0;
  for (const num of nums) {
    sum += num;
    count += map.get(sum - k) || 0; // 前缀和差为k的情况
    map.set(sum, (map.get(sum) || 0) + 1); // 记录当前前缀和
  }
  return count;
}

#数组旋转

数组旋转考察原地操作和空间优化能力，可通过三次翻转实现：

js
function rotateArray(arr, k) {
  k = k % arr.length; // 处理k大于数组长度的情况
  reverse(arr, 0, arr.length - 1);
  reverse(arr, 0, k - 1);
  reverse(arr, k, arr.length - 1);
  return arr;
}

function reverse(arr, start, end) {
  while (start < end) {
    const temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    start++;
    end--;
  }
}

#字符串处理方法

#统计字母出现次数

统计字母出现次数考察对象或Map的使用：

js
function countLetters(str) {
  const count = {};
  for (const char of str) {
    count[char] = (count[char] || 0) + 1;
  }
  return count;
}

#回文判断

回文判断考察字符串操作和循环逻辑：

js
// 方法一：利用split和reverse方法
function isPalindrome(str) {
  return str === str.split('').reverse().join('');
}

// 方法二：纯循环实现
function isPalindrome(str) {
  let left = 0, right = str.length - 1;
  while (left < right) {
    if (str[left] !== str[right]) return false;
    left++;
    right--;
  }
  return true;
}

#最长无重复子串

最长无重复子串考察滑动窗口和哈希表的结合使用，时间复杂度为O(n)：

js
function longest substringWithoutRepetition(s) {
  const map = new Map();
  let max = 0, left = 0;
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i]) && map.get(s[i]) >= left) {
      left = map.get(s[i]) + 1;
    }
    map.set(s[i], i);
    max = Math.max(max, i - left + 1);
  }
  return max;
}
```

#最长回文子串（Manacher算法）

最长回文子串是字符串处理中的难点，Manacher算法可在O(n)时间内解决：

js
function longestPalindrome(s) {
  if (s.length === 0) return '';
  const processedStr = '#' + s.split('').join('#') + '#';
  const n = processedStr.length;
  const pArr = new Array(n).fill(1);
  let center = 0, right = 0, maxLen = 0, maxCenter = 0;

  for (let i = 1; i < n - 1; i++) {
    if (i < right) {
      pArr[i] = Math.min(pArr[2 * center - i], right - i);
    }
    while (processedStr[i + pArr[i]] === processedStr[i - pArr[i]]) {
      pArr[i]++;
    }
    if (i + pArr[i] > right) {
      center = i;
      right = i + pArr[i];
    }
    if (pArr[i] > maxLen) {
      maxLen = pArr[i];
      maxCenter = i;
    }
  }

  const start = (maxCenter - maxLen) / 2;
  return s.substring(start, start + maxLen - 1);
}
```

#进阶算法

随着前端技术栈的复杂化，一些进阶算法题也开始在面试中出现。

#区间合并

区间合并考察数组排序和合并逻辑：

js
function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]); // 按起始点排序
  const result = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1];
    if (intervals[i][0] <= last[1]) {
      // 有重叠，合并区间
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      // 无重叠，添加新区间
      result.push(intervals[i]);
    }
  }
  return result;
}

#版本号排序

版本号排序考察字符串分段和逐位比较：

js
function versionSort(arr) {
  return arr.sort((a, b) => {
    const arr1 = a.split('.').map(Number);
    const arr2 = b.split('.').map(Number);
    const len = Math.max(arr1.length, arr2.length);

    for (let i = 0; i < len; i++) {
      const num1 = arr1[i] || 0;
      const num2 = arr2[i] || 0;
      if (num1 !== num2) return num1 - num2;
    }
    return 0;
  });
}

#大数阶乘

大数阶乘考察数组模拟大数存储和进位处理：

js
function factorial(n) {
  const result = [1];
  for (let i = 2; i <= n; i++) {
    let carry = 0;
    for (let j = 0; j < result.length; j++) {
      const product = result[j] * i + carry;
      result[j] = product % 10;
      carry = Math.floor(product / 10);
    }
    while (carry > 0) {
      result.push(carry % 10);
      carry = Math.floor(carry / 10);
    }
  }
  return result.reverse().join('');
}

#链表操作

链表反转是数据结构中的经典问题，考察指针操作：

js
// 迭代法反转链表
function reverseLinkedList(head) {
  let prev = null, cur = head;
  while (cur !== null) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

// 递归法反转链表
function reverseLinkedListRecursively(head) {
  if (head === null || head.next === null) return head;
  const newHead = reverseLinkedListRecursively(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

#二叉树层次遍历

二叉树层次遍历考察队列数据结构的使用：

js
function levelOrder(root) {
  if (root === null) return [];
  const queue = [root];
  const result = [];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left !== null) queue.push(node.left);
      if (node.right !== null) queue.push(node.right);
    }
    result.push(level);
  }

  return result;
}