前端算法详解

基础数据结构 🟢

1. 数组操作进阶

数组是最基础的数据结构，但在实际应用中，我们需要掌握一些高级操作技巧：

数组去重：

Set去重：最简单但不支持对象去重
对象数组去重：需要考虑对象属性比较
保持原有顺序：某些场景必须保证顺序不变
性能优化：大数据量时的优化策略

代码示例：

// 基础去重
function uniqueArray(arr) {
    return [...new Set(arr)];
}

// 对象数组去重
function uniqueObjectArray(arr, key) {
    const seen = new Map();
    return arr.filter(item => {
        const value = item[key];
        if (seen.has(value)) {
            return false;
        }
        seen.set(value, true);
        return true;
    });
}

// 高性能去重（适用于大数组）
function uniqueLargeArray(arr) {
    const seen = new Set();
    const result = [];
    let i = 0;
    const len = arr.length;
    
    while (i < len) {
        const value = arr[i];
        if (!seen.has(value)) {
            seen.add(value);
            result.push(value);
        }
        i++;
        
        // 每处理1000个元素让出主线程
        if (i % 1000 === 0) {
            if (typeof window !== 'undefined') {
                await new Promise(resolve => setTimeout(resolve, 0));
            }
        }
    }
    
    return result;
}

数组扁平化：

递归实现：最直观但可能栈溢出
迭代实现：避免栈溢出问题
深度控制：支持指定扁平化深度
特殊值处理：null、undefined等

代码示例：

// 递归实现
function flattenRecursive(arr, depth = Infinity) {
    return arr.reduce((flat, item) => {
        if (Array.isArray(item) && depth > 0) {
            return flat.concat(flattenRecursive(item, depth - 1));
        }
        return flat.concat(item);
    }, []);
}

// 迭代实现
function flattenIterative(arr, depth = Infinity) {
    const result = [];
    const stack = arr.map(item => ({
        value: item,
        depth
    }));
    
    while (stack.length) {
        const { value, depth } = stack.pop();
        
        if (Array.isArray(value) && depth > 0) {
            stack.push(...value.map(item => ({
                value: item,
                depth: depth - 1
            })));
        } else {
            result.unshift(value);
        }
    }
    
    return result;
}

// 生成器实现
function* flattenGenerator(arr, depth = Infinity) {
    for (const item of arr) {
        if (Array.isArray(item) && depth > 0) {
            yield* flattenGenerator(item, depth - 1);
        } else {
            yield item;
        }
    }
}

2. 链表操作进阶

链表是一种重要的数据结构，在前端中虽然使用较少，但在算法面试中经常出现：

链表反转：

迭代法：使用三个指针
递归法：简洁但空间复杂度高
部分反转：反转指定区间
分组反转：每K个节点一组反转

代码示例：

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

// 迭代反转
function reverseList(head) {
    let prev = null;
    let curr = head;
    
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

// 递归反转
function reverseListRecursive(head) {
    if (!head || !head.next) {
        return head;
    }
    
    const newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    
    return newHead;
}

// 区间反转
function reverseBetween(head, left, right) {
    if (!head || left === right) return head;
    
    const dummy = new ListNode(0, head);
    let prev = dummy;
    
    // 移动到反转起点的前一个节点
    for (let i = 1; i < left; i++) {
        prev = prev.next;
    }
    
    // 开始反转
    let curr = prev.next;
    for (let i = left; i < right; i++) {
        const next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }
    
    return dummy.next;
}

链表环检测：

快慢指针：最优解，空间O(1)
哈希表法：直观但空间O(n)
环的起点：快慢指针的应用
环的长度：如何计算环的长度

代码示例：

// 检测环
function hasCycle(head) {
    if (!head || !head.next) return false;
    
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            return true;
        }
    }
    
    return false;
}

// 找到环的起点
function detectCycle(head) {
    if (!head || !head.next) return null;
    
    // 第一步：检测环
    let slow = head;
    let fast = head;
    let hasCycle = false;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            hasCycle = true;
            break;
        }
    }
    
    if (!hasCycle) return null;
    
    // 第二步：找到环的起点
    slow = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;
}

// 计算环的长度
function cycleLength(head) {
    const start = detectCycle(head);
    if (!start) return 0;
    
    let curr = start.next;
    let length = 1;
    
    while (curr !== start) {
        length++;
        curr = curr.next;
    }
    
    return length;
}

排序算法详解 🟡

1. 快速排序

快速排序是最常用的排序算法之一，其核心思想是分治。我们需要考虑以下几个方面：

基准值选择：

固定选择：最简单但可能退化
随机选择：避免最坏情况
三数取中：更好的基准值
处理重复元素：双指针优化

分区策略：

单路分区：简单但重复元素多时效率低
双路分区：处理重复元素更高效
三路分区：处理大量重复元素最优

代码示例：

// 三路快排实现
function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return;
    
    // 三数取中选择基准值
    const mid = Math.floor((left + right) / 2);
    const pivot = medianOfThree(
        arr[left],
        arr[mid],
        arr[right]
    );
    
    // 三路分区
    let lt = left;     // arr[left...lt-1] < pivot
    let gt = right;    // arr[gt+1...right] > pivot
    let i = left;      // arr[lt...i-1] == pivot
    
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr, i++, lt++);
        } else if (arr[i] > pivot) {
            swap(arr, i, gt--);
        } else {
            i++;
        }
    }
    
    // 递归处理左右两部分
    quickSort(arr, left, lt - 1);
    quickSort(arr, gt + 1, right);
    
    return arr;
}

// 三数取中
function medianOfThree(a, b, c) {
    if (a > b) [a, b] = [b, a];
    if (b > c) [b, c] = [c, b];
    if (a > b) [a, b] = [b, a];
    return b;
}

// 交换元素
function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}

2. 归并排序

归并排序是一种稳定的排序算法，在处理链表排序时特别有用：

实现方式：

递归实现：自顶向下
迭代实现：自底向上
原地归并：节省空间
并行归并：利用多线程

代码示例：

// 递归归并排序
function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    
    return merge(left, right);
}

// 优化的归并函数
function merge(left, right) {
    const result = new Array(left.length + right.length);
    let i = 0, j = 0, k = 0;
    
    // 使用临时数组避免频繁的数组操作
    while (i < left.length && j < right.length) {
        result[k++] = left[i] <= right[j] ? 
            left[i++] : right[j++];
    }
    
    // 处理剩余元素
    while (i < left.length) result[k++] = left[i++];
    while (j < right.length) result[k++] = right[j++];
    
    return result;
}

// 链表归并排序
function mergeSortList(head) {
    if (!head || !head.next) return head;
    
    // 快慢指针找中点
    let slow = head;
    let fast = head;
    let prev = null;
    
    while (fast && fast.next) {
        fast = fast.next.next;
        prev = slow;
        slow = slow.next;
    }
    
    // 断开链表
    prev.next = null;
    
    // 递归排序
    const left = mergeSortList(head);
    const right = mergeSortList(slow);
    
    // 合并有序链表
    return mergeLists(left, right);
}

// 合并有序链表
function mergeLists(l1, l2) {
    const dummy = new ListNode(0);
    let curr = dummy;
    
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    
    curr.next = l1 || l2;
    return dummy.next;
}

搜索算法详解 🟡

1. 二分查找进阶

二分查找虽然概念简单，但细节很多，需要注意以下几点：

边界处理：

左闭右闭：[left, right]
左闭右开：[left, right)
处理重复元素
寻找边界值

变种问题：

旋转数组查找
寻找峰值
寻找插入位置
寻找最接近的元素

代码示例：

// 标准二分查找
function binarySearch(arr, target) {
    let left = 0;
    let 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;
}

// 寻找左边界
function searchLeftBound(arr, target) {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = left + ((right - left) >> 1);
        
        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

// 寻找右边界
function searchRightBound(arr, target) {
    let left = 0;
    let right = arr.length;
    
    while (left < right) {
        const mid = left + ((right - left) >> 1);
        
        if (arr[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left - 1;
}

// 旋转数组查找
function searchInRotated(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = left + ((right - left) >> 1);
        
        if (arr[mid] === target) {
            return mid;
        }
        
        // 判断哪部分是有序的
        if (arr[left] <= arr[mid]) {
            // 左半部分有序
            if (target >= arr[left] && target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // 右半部分有序
            if (target > arr[mid] && target <= arr[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

2. 深度优先搜索(DFS)

DFS是一种重要的搜索算法，在树和图的遍历中经常使用：

实现方式：

递归实现：代码简洁
栈实现：避免递归栈溢出
回溯法：需要恢复状态
剪枝优化：提高效率

代码示例：

// 递归DFS（以二叉树为例）
function dfs(root) {
    if (!root) return;
    
    // 前序遍历
    console.log(root.val);
    dfs(root.left);
    dfs(root.right);
}

// 栈实现DFS
function dfsIterative(root) {
    if (!root) return;
    
    const stack = [root];
    const result = [];
    
    while (stack.length) {
        const node = stack.pop();
        result.push(node.val);
        
        // 注意入栈顺序
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    
    return result;
}

// 回溯法（以全排列为例）
function permute(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);
    
    function backtrack(path) {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            
            // 做选择
            path.push(nums[i]);
            used[i] = true;
            
            // 递归
            backtrack(path);
            
            // 撤销选择
            path.pop();
            used[i] = false;
        }
    }
    
    backtrack([]);
    return result;
}

3. 广度优先搜索(BFS)

BFS常用于寻找最短路径和层次遍历：

实现要点：

队列实现：核心数据结构
层次信息：如何保存层次
优化技巧：双端队列、多源BFS
避免重复：访问标记

代码示例：

// 二叉树层次遍历
function levelOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length) {
        const level = [];
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const node = queue.shift();
            level.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(level);
    }
    
    return result;
}

// 最短路径BFS
function shortestPath(graph, start, end) {
    const queue = [[start]];
    const visited = new Set([start]);
    
    while (queue.length) {
        const path = queue.shift();
        const node = path[path.length - 1];
        
        if (node === end) {
            return path;
        }
        
        for (const next of graph[node]) {
            if (!visited.has(next)) {
                visited.add(next);
                queue.push([...path, next]);
            }
        }
    }
    
    return null;
}

// 多源BFS（以01矩阵为例）
function updateMatrix(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const dist = Array.from(
        { length: m },
        () => new Array(n).fill(Infinity)
    );
    const queue = [];
    
    // 将所有0入队
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 0) {
                dist[i][j] = 0;
                queue.push([i, j]);
            }
        }
    }
    
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    
    while (queue.length) {
        const [i, j] = queue.shift();
        
        for (const [di, dj] of dirs) {
            const ni = i + di;
            const nj = j + dj;
            
            if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                if (dist[ni][nj] > dist[i][j] + 1) {
                    dist[ni][nj] = dist[i][j] + 1;
                    queue.push([ni, nj]);
                }
            }
        }
    }
    
    return dist;
}

动态规划详解 🔴

动态规划是一种解决复杂问题的方法，通过将问题分解为子问题来解决。关键点包括：

问题特征：

最优子结构
重叠子问题
状态转移方程
边界条件

常见优化：

状态压缩
空间优化
预处理优化
决策单调性

代码示例：

// 经典DP问题：最长递增子序列
function lengthOfLIS(nums) {
    if (!nums.length) return 0;
    
    // dp[i]表示以nums[i]结尾的最长递增子序列长度
    const dp = new Array(nums.length).fill(1);
    let maxLen = 1;
    
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    
    return maxLen;
}

// 优化版本：使用二分查找
function lengthOfLISOptimized(nums) {
    const tails = [];
    
    for (const num of nums) {
        let left = 0;
        let right = tails.length;
        
        while (left < right) {
            const mid = left + ((right - left) >> 1);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        if (left === tails.length) {
            tails.push(num);
        } else {
            tails[left] = num;
        }
    }
    
    return tails.length;
}

// 背包问题
function knapsack(weights, values, capacity) {
    const n = weights.length;
    const dp = Array.from(
        { length: n + 1 },
        () => new Array(capacity + 1).fill(0)
    );
    
    for (let i = 1; i <= n; i++) {
        const w = weights[i - 1];
        const v = values[i - 1];
        
        for (let j = 0; j <= capacity; j++) {
            if (j >= w) {
                dp[i][j] = Math.max(
                    dp[i - 1][j],
                    dp[i - 1][j - w] + v
                );
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    
    return dp[n][capacity];
}

// 空间优化版本
function knapsackOptimized(weights, values, capacity) {
    const dp = new Array(capacity + 1).fill(0);
    
    for (let i = 0; i < weights.length; i++) {
        for (let j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(
                dp[j],
                dp[j - weights[i]] + values[i]
            );
        }
    }
    
    return dp[capacity];
}

通过以上内容，我们详细介绍了前端开发中常见的算法问题及其解决方案。这些算法不仅在面试中常见，在实际开发中也有广泛应用。掌握这些算法可以帮助我们写出更高效的代码，解决更复杂的问题。

每个算法都包含了详细的实现代码和优化思路，建议读者在理解基本实现的基础上，思考如何根据实际场景进行优化和改进。同时，也要注意算法的时间复杂度和空间复杂度，在实际应用中做出合适的取舍。