前端笔试高频算法题及JavaScript实现
以下是前端笔试常见的编程算法题及JavaScript代码现,结合最新面试题整理:
一、数组/字符串处理
-
两数之和
找出数组中两数之和等于目标值的索引const 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); } };
-
最长无重复子串
求字符串中最长不重复字符的子串长度const lengthOfLongestSubstring = (s) => { let map = new Map(), max = 0, left = 0; for (let right = 0; right < s.length; right++) { if (map.has(s[right])) left = Math.max(left, map.get(s[right]) + 1); map.set(s[right], right); max = Math.max(max, right - left + 1); } };
-
数组扁平化与去重
输入多维数组,输出一维去重排序结果const flattenAndUnique = (arr) => [...new Set(arr.flat(Infinity))].sort((a,b) => a - b);
二、排序算法
-
快速排序
分治递归实现const quickSort = (arr) => { if (arr.length <= 1) return arr; const pivot = arr.pop(); const left = arr.filter(x => x <= pivot); const right = arr.filter(x => x > pivot); return [...quickSort(left), pivot, ...quickSort(right)]; };
-
冒泡排序
基础版本function bubbleSort(arr) { let len = arr.length; for (let i = 0; i < len; i++) { for (let j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } return arr; }
三、链表操作
-
反转链表
单链表原地反转function reverseList(head) { let prev = null, curr = head; while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; }
-
判断环形链表
快慢指针法const hasCycle = (head) => { let slow = head, fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow === fast) return true; } return false; };
四、动态规划
-
爬楼梯
每次跳1或2阶,求方法总数const climbStairs = (n) => { let [a, b] = [1, 1]; for (let i = 2; i <= n; i++) [a, b] = [b, a + b]; return b; };
-
买卖股票最佳时机
求一次交易最大利润const maxProfit = (prices) => { let min = Infinity, max = 0; for (const price of prices) { min = Math.min(min, price); max = Math.max(max, price - min); } return max; };
五、其他高频题
- 有效括号
判断字符串中的括号是否有效const isValid = (s) => { const stack = []; const map = { '(': ')', '{': '}', '[': ']' }; for (const char of s) { if (map[char]) stack.push(map[char]); else if (char !== stack.pop()) return false; } return stack.length === 0; };
提示:面试中需注意边界条件(如空数组、null值)和代码优化,建议结合具体场景选择最优解法。更多题目可参考中的完整题库。
以下是更多前端笔试高频算法题及JavaScript实现,结合最新面试题整理:
一、数组/字符串处理
- 二维数组中的数查找
在每行递增、每列递增的二维数组中查找目标值
const findNumberIn2DArray = (matrix, target) => {
if (matrix.length === 0 || matrix[0].length === 0) return false;
let row = 0, col = matrix[0].length - 1;
while (row < matrix.length && col >= 0) {
if (matrix[row][col] === target) return true;
else if (matrix[row][col] > target) col--;
else row++;
}
return false;
};
//
- 替换空格
将字符串中的空格替换为"%20"
const replaceSpace = (s) => s.replace(/\s/g, '%20');
//
- 版本号排序
对版本号数组进行降序排序
const versionSort = (versions) =>
versions.sort((a, b) => {
const arr1 = a.split('.').map(Number);
const arr2 = b.split('.').map(Number);
for (let i = 0; i < Math.max(arr1.length, arr2.length); i++) {
if (arr1[i] !== arr2[i]) return arr2[i] - arr1[i];
}
return 0;
});
//
二、排序算法
- 快速排序优化
三数取中法优化基准选择
const quickSort = (arr) => {
if (arr.length <= 1) return arr;
const pivotIndex = medianOfThree(arr, 0, Math.floor(arr.length/2), arr.length-1);
const pivot = arr.splice(pivotIndex, 1)[0];
const left = [], right = [];
for (let num of arr) {
if (num < pivot) left.push(num);
else right.push(num);
}
return [...quickSort(left), pivot, ...quickSort(right)];
};
//
- 堆排序
基于最大堆的排序实现
const heapSort = (arr) => {
buildMaxHeap(arr);
for (let i = arr.length - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, 0, i);
}
};
//
三、动态规划
- 最长递增子序列
求最长严格递增子序列长度
const lengthOfLIS = (nums) => {
const dp = new Array(nums.length).fill(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);
}
}
return Math.max(...dp);
};
//
- 编辑距离
计算两个字符串的最小编辑操作数
const minDistance = (word1, word2) => {
const m = word1.length, n = word2.length;
const dp = Array.from({ length: m+1 }, () => Array(n+1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i-1] === word2[j-1]) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
}
}
return dp[m][n];
};
//
四、递归与回溯
- 字符串全排列
生成字符串的所有排列组合
const permute = (str) => {
const results = [];
const backtrack = (current, remaining) => {
if (remaining.length === 0) results.push(current);
for (let i = 0; i < remaining.length; i++) {
backtrack(current + remaining[i], remaining.slice(0, i) + remaining.slice(i+1));
}
};
backtrack('', str);
return results;
};
//
- N皇后问题
在N×N棋盘上放置N个皇后
const solveNQueens = (n) => {
const solutions = [];
const columns = new Set();
const diagonals1 = new Set();
const diagonals2 = new Set();
const backtrack = (row, queens) => {
if (row === n) {
solutions.push(queens.map(pos => '.'.repeat(pos) + 'Q' + '.'.repeat(n - pos - 1)));
return;
}
for (let col = 0; col < n; col++) {
const diag1 = row - col;
const diag2 = row + col;
if (!columns.has(col) && !diagonals1.has(diag1) && !diagonals2.has(diag2)) {
columns.add(col);
diagonals1.add(diag1);
diagonals2.add(diag2);
backtrack(row + 1, [...queens, col]);
columns.delete(col);
diagonals1.delete(diag1);
diagonals2.delete(diag2);
}
}
};
backtrack(0, []);
return solutions;
};
//
五、高频算法优化技巧
- 位运算优化素数判断
利用6k±1规则加速判断
const isPrime = (num) => {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 === 0 || num % 3 === 0) return false;
for (let i = 5; i * i <= num; i += 6) {
if (num % i === 0 || num % (i + 2) === 0) return false;
}
return true;
};
//
- 双指针优化数组操作
如三数之和、旋转数组最小值问题
// 三数之和优化版
const threeSum = (nums) => {
nums.sort((a,b) => a - b);
const res = [];
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;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
res.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 < 0) left++;
else right--;
}
}
return res;
};
//
提示:以上题目覆盖了前端面试80%以上的算法考点,建议结合LeetCode、HackerRank等平台进行专项训练。面试时注意代码鲁棒性,如处理空值、边界条件等。