前端算法详解基础数据结构 🟢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];
}通过以上内容，我们详细介绍了前端开发中常见的算法问题及其解决方案。这些算法不仅在面试中常见，在实际开发中也有广泛应用。掌握这些算法可以帮助我们写出更高效的代码，解决更复杂的问题。
每个算法都包含了详细的实现代码和优化思路，建议读者在理解基本实现的基础上，思考如何根据实际场景进行优化和改进。同时，也要注意算法的时间复杂度和空间复杂度，在实际应用中做出合适的取舍。