【复盘】20个常考的前端算法题，你全都会吗？ |
您所在的位置：网站首页 › gis工程师考算法吗 › 【复盘】20个常考的前端算法题，你全都会吗？ |
【复盘】20个常考的前端算法题，你全都会吗？
|
大厂技术 高级前端 Node进阶 点击上方 程序员成长指北，关注公众号 回复1，加入高级Node交流群 现在面试中，算法出现的频率越来越高了，大厂基本必考 今天给大家带来20个常见的前端算法题，重要的地方已添加注释，如有不正确的地方，欢迎多多指正💕 1、两数之和题目：给定一个数组 nums 和一个目标值 target，在该数组中找出和为目标值的两个数 输入：nums: [8, 2, 6, 5, 4, 1, 3] ；target:7 输出：[2, 5] // 时间复杂度O(n)、 空间复杂度O(n) function twoNumAdd(arr, target) { if (Array.isArray(arr)) { // 使用map将遍历过的数字存起来，空间换时间 let map = {}; for (let i = 0; i < arr.length; i++) { // 从map中查找是否有key 等于 target-nums[i]，如果有，则条件成立，返回结果 if (map[target - arr[i]] !== undefined) { return [target - arr[i], arr[i]]; } else { // 条件不成立，将该值存起来 map[arr[i]] = i; } } } return []; } 复制代码 2、三数之和题目：给定一个数组nums，判断 nums 中是否存在三个元素a，b，c，使得 a + b + c = target，找出所有满足条件且不重复的三元组合 输入：nums: [5, 2, 1, 1, 3, 4, 6] ；target:8 输出：[[1, 1, 6], [1, 2, 5], [1, 3, 4]] // 用`双端指针`的方式，将三数之和转化为两数之和 function findThree(arr, target) { // 先将数组从小到大排序 arr.sort(); let result = []; for (let i = 0; i < arr.length; i++) { // 跳过重复的arr[i]值, 比如[2, 1, 1],跳过第二个1 if (i && arr[i] === arr[i - 1]) continue; let left = i + 1; let right = arr.length - 1; // 双端指针left、right while (left < right) { let sum = arr[i] + arr[left] + arr[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { // 先取arr[left]，然后left++, 两步合成一步；arr[right--]同样的逻辑 result.push([arr[i], arr[left++], arr[right--]]); while (arr[left] === arr[left - 1]) { // 跳过重复的arr[left]值, left++; } while (arr[right] === arr[right + 1]) { // 跳过重复的arr[right]值 right--; } } } } return result; } 复制代码 3、版本号排序题目：输入一组版本号，输出从大到小的排序 输入：['2.1.0.1', '0.402.1', '10.2.1', '5.1.2', '1.0.4.5'] 输出：['10.2.1', '5.1.2', '2.1.0.1', '1.0.4.5', '0.402.1'] function versionSort(arr) { return arr.sort((a, b) => { let i = 0; const arr1 = a.split("."); const arr2 = b.split("."); while (true) { // 取出相同位置的数字 const s1 = arr1[i]; const s2 = arr2[i]; i++; // 若s1 或 s2 不存在，说明相同的位置已比较完成，接下来比较arr1 与 arr2的长度，长的版本号大 if (s1 === undefined || s2 === undefined) { return arr2.length - arr1.length; } if (s1 === s2) continue; // 比较相同位置的数字大小 return s2 - s1; } }); } 复制代码 4、第一个不重复的字符题目：输入一个字符串，找到第一个不重复字符的下标 输入：'abcabcde' 输出：6 // 时间复杂度O(n)、 空间复杂度O(n) function findOneStr(str) { if (!str) return -1; // 使用map存储每个字符出现的次数 let map = {}; let arr = str.split(""); arr.forEach(item => { let val = map[item]; // val为undefined时，表示未存储，map[item] = 1；否则map[item] = val + 1 map[item] = val ? val + 1 : 1; }); // 再遍历一遍找到出现1次的下标 for (let i = 0; i < arr.length; i++) { if (map[arr[i]] == 1) { return i; } } return -1; } 复制代码 5、字符串所有排列组合题目：输入一个字符串，打印出该字符串中，所有字符的排列组合 输入：'abc' 输出：['abc', 'acb', 'bca', 'bac', 'cab', 'cba'] /** * 利用回溯算法，计算所有字符串的组合 * @param {array} list - 字符串列表 * @param {array} result - 最终的结果 * @param {string} current - 当前的字符串 * @param {string} temp - 当前固定的字符 */ function stringGroup(list = [], result = [], current = "", temp = "") { current += temp; if (list.length === 0) { // 递归的出口，将对应结果添加到list中 return result.push(current); } for (let i = 0; i < list.length; i++) { // 每次递归 固定第一个字符 temp = list.shift(); stringGroup(list, result, current, temp); // 将删除的temp重新添加到queue尾部，实现将数组反转的效果，如[a,b,c]反转为[c,b,a] list.push(temp); } // 这里去重是解决str中有重复的字母，比如str为'aacd' return [...new Set(result)]; } 复制代码 6、冒泡排序时间复杂度为O(n²)，稳定排序算法 
bubble.gif
function bubbleSort(arr) {
let length = arr.length;
// 外层循环用控制 排序进行多少轮
for (let i = 0; i < length; i++) {
// 内层循环用于每一轮的数据比较
// 注意j的长度范围 length - i - 1
for (let j = 0; j < length - i - 1; j++) {
// 相邻元素，大的放到后面
if (arr[j] > arr[j + 1]) {
// 交换位置
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
复制代码
7、选择排序
时间复杂度为O(n²)，不稳定 
selectSort.gif
function selectSort(arr) {
// 定义index存储最小值的下标
let index;
// 外层循环用控制 排序进行多少轮
for (let i = 0; i < arr.length - 1; i++) {
index = i;
// 内层循环用于每一轮的数据比较
// 注意j的起始范围是 i + 1
for (let j = i + 1; j < arr.length; j++) {
// 寻找最小值
if (arr[j] < arr[index]) {
// 保存最小值的下标
index = j;
}
}
// 如果 index 不是目前的头部元素，则交换两者
if (index !== i) {
[arr[i], arr[index]] = [arr[index], arr[i]];
}
}
return arr;
}
复制代码
8、插入排序
时间复杂度为O(n²)，稳定 
insert.gif
function insertSort(arr) {
// 从第 2 个元素开始遍历序列
for (let i = 1; i < arr.length; i++) {
let j = i;
//记录要插入的目标元素
let target = arr[j];
//从 target 所在位置向前遍历，直至找到一个比目标元素小的元素，目标元素插入到该元素之后的位置
while (j > 0 && arr[j - 1] > target) {
//移动前一个元素的位置，将其向后移动一个位置
arr[j] = arr[j - 1];
j--;
}
arr[j] = target;
}
return arr;
}
复制代码
9、快速排序
时间复杂度为O(nlogn)，不稳定 
sort.gif
function quickSort(list) {
// 当list.length base) {
right.push(item);
} else {
left.push(item);
}
});
// 重新组合数组
return quickSort(left).concat(base, quickSort(right));
}
复制代码
10、归并排序
时间复杂度为O(nlogn)，稳定 
merge.gif
function MergeSort(array) {
let len = array.length;
// 当每个子序列中仅有1个元素时返回
if (len {
arr.push(data.id);
// 遍历子树
data.children && deepTree(data.children, arr);
});
return arr;
}
// 非递归版本
function deepTree(tree) {
if (!tree || !tree.length) return;
let arr = [];
let stack = [];
//先将第一层节点放入栈
for (let i = 0, len = tree.length; i < len; i++) {
stack.push(tree[i]);
}
let node;
while (stack.length) {
// 获取当前第一个节点
node = stack.shift();
arr.push(node.id);
//如果该节点有子节点，继续添加进入栈顶
if (node.children && node.children.length) {
stack = node.children.concat(stack);
}
}
return arr;
}
复制代码
13、广度优先遍历
题目：以横向的维度对树进行遍历，从第一个节点开始，依次遍历其所有的兄弟节点，再遍历第一个节点的子节点，一层层向下遍历 输入：上文第11题生成的tree 输出：[1, 2, 3, 4, 5] function rangeTree(tree) { if (!tree || !tree.length) return; let arr = []; let node, list = [...tree]; // 取出当前节点 while ((node = list.shift())) { arr.push(node.id); node.children && list.push(...node.children); } return arr; } 复制代码 14、树形结构查找节点题目：查找树形结构中符合要求的节点 输入：tree：上文第11题生成的tree func：data => data.title === "child2_1" 输出：{ id: 5, parentId: 2, title: "child2_1" } /** * 查找节点 * @param {array} tree - 树 * @param {function} func - 查找条件 * */ function findTreeNode(tree, func) { for (const data of tree) { // 条件成立 直接返回 if (func(data)) return data; if (data.children) { const res = findTreeNode(data.children, func); // 结果存在再返回 if (res) return res; } } return null; } // 测试 findTreeNode(tree, data => data.title === "child2_1") 复制代码 15、二叉查找树题目：判断一个数组，是否为某二叉查找树的前序遍历结果，二叉查找树特点是所有的左节点比父节点的值小，所有的右节点比父节点的值大 输入：[5, 3, 2, 1, 4, 6, 7, 8, 9] 输出：true function preOrderOfBST(list) { if (list && list.length > 0) { // 前序遍历，第一个值为根节点 var root = list[0]; // 找到数组中，第一个比根节点大的节点，即为右子树的节点 for (var i = 0; i < list.length; i++) { if (list[i] > root) { break; } } // 遍历右子树的节点，要求所有右子树的节点都比根节点大 for (let j = i; j < list.length; j++) { if (list[j] < root) { return false; } } var left = true; // 同理，递归判断左子树是否符合二叉查找树的规则 if (i > 1) { left = preOrderOfBST(list.slice(1, i + 1)); } var right = true; // 递归判断右子树是否符合二叉查找树的规则 if (i < list.length) { right = preOrderOfBST(list.slice(i, list.length)); } // 左、右子树都符合要求，则是一个二叉查找树 return left && right; } } 复制代码 16、查找二叉树的路径题目：查找二叉树和为某一值的路径 输入：二叉树结构如下，找到和为 11 的所有路径 
findTree.png
输出：[[5, 3, 2, 1], [5, 6]] /** * 利用回溯算法，找到和为某一值的路径 * @param {object} node - 二叉树 * @param {number} num - 目标值 * @param {array} stack - 栈 * @param {number} sum - 当前路径的和 * @param {array} result - 存储所有的结果 * */ function findPath(node, num, stack = [], sum = 0, result = []) { stack.push(node.data); sum += node.data; // 找到所有的节点路径(包含叶子节点和子节点的所有情况之和) if (sum === num) { // if (!node.left && !node.right && sum === num) { // 找到所有的叶子节点路径 result.push(stack.slice()); } if (node.left) { findPath(node.left, num, stack, sum, result); } if (node.right) { findPath(node.right, num, stack, sum, result); } // 回溯算法：不符合要求，退回来，换一条路再试 // 叶子节点直接pop；子节点中的所有的节点递归完成后再pop stack.pop(); return result; } 复制代码 17、买卖股票问题题目：给定一个整数数组，其中第 i 个元素代表了第 i天的股票价格；非负整数 fee 代表了交易股票的手续费用，求返回获得利润的最大值 输入：arr: [1, 12, 13, 9, 15, 8, 6, 16]；fee: 2 输出：22 /** * 贪心算法求解 * @param {array} list - 股票每天的价格列表 * @param {number} fee - 手续费 * */ function buyStock(list, fee) { // min为当前的最小值，即买入点 let min = list[0], sum = 0; for (let i = 1; i < list.length; i++) { // 从1开始，依次判断 if (list[i] < min) { // 寻找数组的最小值 min = list[i]; } else { // 计算如果当天卖出是否赚钱 let temp = list[i] - min - fee; if (temp > 0) { // 赚钱 存数据 sum += temp; // 关键代码：重新计算min，分两种情况，如果后面继续涨，则默认继续持有；若后面跌，则以后面的价格重新买入 min = list[i] - fee; } } } return sum; } 复制代码 18、斐波那契数列题目：从第3项开始，当前项等于前两项之和：1 1 2 3 5 8 13 21 ……，计算第n项的值 输入：10 输出：89 // 使用动态规划，将复杂的问题拆分，也就是：`F(N) = F(N - 1) + F(N - 2)`，用数组将已经计算过的值存起来 function fib(n) { // 使用dp数组，将之前计算的结果存起来，防止栈溢出 if (n < 2) return 1; let dp = [1, 1]; for (let i = 2; i = 0; j--) { // 当前窗口的值依次和要插入的值做比较，如果小于要插入的值，剔除掉该值，直到window为空为止（保证window中最左侧的值为最大值） if (nums[window[j]] = k - 1) { // 窗口是从0开始移动，当移动的距离大于等于目标范围后，以后再往后移动一次，就要写入当前窗口的最大值 result.push(nums[window[0]]); } } return result; } 复制代码 20、最长递增子序列题目：一个整数数组 nums，找到其中一组最长递增子序列的值 输入：[3,5,7,1,2,8] 输出：[3,5,7,8] function lengthOfLIS(nums) { if (!nums.length) return 0; // 创建一个和原数组等长的数组dp，用来存储每一项的最长递增子序列 // 比如[1,2,2] 表示第二项和第三项的最长递增子序列都为2 let dp = new Array(nums.length).fill(1); // 双层for循环，每一项都和之前的所有项一一进行比较，计算出该项的最长递增子序列个数，存储到dp中 for (let i = 0; i < nums.length; i++) { // 当前项依次和之前的每一项进行比较，累加出当前项的最长递增子序列 for (let j = 0; j < i; j++) { if (nums[j] < nums[i]) { // 比较当前项已有的最大值和之前项最大值，比如当比较到第三项[1,2,2]时，如第三项比第二项大，所以第三项的计算结果为[1,2,3] dp[i] = Math.max(dp[i], dp[j] + 1); } } } // 取出一组最长递增子序列的具体值（注意：最长递增子序列有可能有多组值，这里是只取出其中一组值） // 找到dp中的最大值，该值就是nums的最长递增子序列的个数 let max = Math.max(...dp); let result = []; for (let i = max; i >= 1; i--) { // 倒序遍历，根据长度获取对应的值 findArrNode(dp, i, result, nums); } return result; } function findArrNode(dp, value, result, arr) { // 找到符合条件最后一项的下标，这样才能保证数组的顺序是正确的 let index = dp.lastIndexOf(value); // 存储对应的值 result.unshift(arr[index]); // 对dp进行截取，保证只取最大项之前的数据 dp.length = index + 1; } 复制代码github代码仓库：https://github.com/xy-sea/blog/blob/dev/markdown/「历时8个月」10万字前端知识体系总结（算法篇）.md 以上就是工作或面试中最常见的算法题，小伙伴是不是全都掌握了呢，欢迎在评论区交流 如果文章对你有所帮助，不要忘了点上宝贵的👍！ 作者：海阔_天空 原文：https://juejin.cn/post/7158730050718662687 Node 社群 我组建了一个氛围特别好的 Node.js 社群，里面有很多 Node.js小伙伴，如果你对Node.js学习感兴趣的话（后续有计划也可以），我们可以一起进行Node.js相关的交流、学习、共建。下方加 考拉 好友回复「Node」即可。
|
【本文地址】
今日新闻 |
推荐新闻 |