【面试】盘点10个高频的前端算法题，你全都会了吗？ |
您所在的位置：网站首页 › 程序员算法面试题 › 【面试】盘点10个高频的前端算法题，你全都会了吗？ |
【面试】盘点10个高频的前端算法题，你全都会了吗？
|
前言 📫 大家好，我是南木元元，热爱技术和分享，欢迎大家交流，一起学习进步！ 🍅 个人主页：南木元元 现在前端的面试中，算法出现的频率越来越高了，大厂更是必考算法 。本文就来分享一下10个常见的前端算法题，重要的地方已添加注释，如有不正确的地方，欢迎多多指正。 目录 1.合并两个有序数组 2.两数之和 3.三数之和 4.反转链表 5.全排列 6.有效的括号 7.二叉树的中序遍历 8.翻转二叉树 9.K个一组翻转链表 10.最长递增子序列 结语 1.合并两个有序数组题目：给定两个非递减的有序数组nums1和nums2，合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。 示例：
来源：LeetCode第88题 代码实现： //方法1：将nums2放到nums1的尾部，然后直接对整个数组进行排序 var merge = function (nums1, m, nums2, n) { nums1.splice(m, n, ...nums2); nums1.sort((a, b) => a - b); }; //方法2：逆向双指针，从后往前遍历 var merge = function (nums1, m, nums2, n) { let i = m - 1, j = n - 1, k = m + n - 1; while (i >= 0 || j >= 0) { if (i < 0) { nums1[k--] = nums2[j--]; } else if (j < 0) { nums1[k--] = nums1[i--]; } else if (nums1[i] a - b); for (let i = 0; i < nums.length; i++) { //如果当前第一个数大于0直接返回res if (nums[i] > 0) { return res; } //对第一个元素去重 if (i > 0 && nums[i] === nums[i - 1]) { continue; } let l = i + 1; let r = nums.length - 1; while (l < r) { if (nums[i] + nums[l] + nums[r] > 0) { r--; } else if (nums[i] + nums[l] + nums[r] < 0) { l++; } else { res.push([nums[i], nums[l], nums[r]]); // 对第2、3个元素去重 while (l < r && nums[l] === nums[l + 1]) { l++; } while (l < r && nums[r] === nums[r - 1]) { r--; } l++; r--; } } } return res; }; 4.反转链表题目：给你一个单链表的头节点head，反转单链表。 示例：
来源：LeetCode第206题 代码实现： // 1.双指针法，只需要改变链表的next指针的指向 var reverseList = function(head) { let p = null; let q = head; let tmp = null; //保存下一个节点 while(q) { tmp = q.next; q.next = p; p = q; q = tmp; } return p; }; // 2.递归法 var reverseList = function(head) { var reverse = function(p, q) { if(q === null) { return p; } let tmp = q.next; q.next = p; p = q; return reverse(p, tmp); //注意这里必须return } return reverse(null, head); }; 5.全排列题目：给定一个没有重复数字的序列，返回其所有可能的全排列。 示例：
来源：LeetCode第46题 实现代码： // 回溯 var permute = function (nums) { let res = []; let path = []; var bt = function (used) { if (path.length === nums.length) { res.push([...path]); return; } for (let i = 0; i < nums.length; i++) { //used数组，记录此时path里已经选择的元素,一个排列里一个元素只能使用一次 if (used[i] === 1) { continue; } path.push(nums[i]); used[i] = 1; bt(used); used[i] = 0; path.pop(); } }; bt([]); return res; }; 6.有效的括号题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 示例：
来源：LeetCode第20题 实现代码： var isValid = function (s) { let stack = []; for (let i = 0; i < s.length; i++) { if (s[i] === "(") { stack.push(")"); } else if (s[i] === "{") { stack.push("}"); } else if (s[i] === "[") { stack.push("]"); } else { //栈为空，说明多了右括号 if (stack.length === 0 || stack.pop() !== s[i]) { return false; } } } //遍历结束栈还有元素，说明多了左括号 return stack.length !== 0 ? false : true; }; 7.二叉树的中序遍历题目：给定一个二叉树的根节点root，返回它的中序遍历。 示例：
来源：LeetCode第94题 代码实现： // 1.递归 法var preorderTraversal = function (root) { let res = []; var dfs = function (root) { if (!root) { return; } dfs(root.left); //左 res.push(root.val); //中 dfs(root.right); //右 }; dfs(root); return res; }; // 2.迭代法（重点） var inorderTraversal = function (root) { if (!root) { return []; } let res = []; let stack = []; //定义一个指针，指向当前遍历节点 let cur = root; while (cur || stack.length) { if (cur) { //一直遍历到左下 stack.push(cur); cur = cur.left; } else { cur = stack.pop(); res.push(cur.val); cur = cur.right; } } return res; }; 8.翻转二叉树题目：给你一棵二叉树的根节点root，翻转这棵树，并返回其根节点。 示例：
来源：LeetCode第102题 代码实现： // 1.递归，先交换根节点左右子树，再分别对左右子树进行处理 var invertTree = function (root) { if (!root) { return root; } let tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right); return root; }; // 2.迭代 var invertTree = function(root) { let stack = []; if(root == null) { return root; } stack.push(root); while(stack.length != 0) { let node = stack.pop(); if(node != null) { if(node.right) { stack.push(node.right); } if(node.left) { stack.push(node.left); } stack.push(node); stack.push(null); } else { let cur = stack.pop(); //每遍历一个节点，就交换它的左右子树 [cur.left, cur.right] = [cur.right, cur.left]; } } return root; }; 9.K个一组翻转链表题目：给你一个链表的头节点head，每k个节点一组进行翻转，返回修改后的链表。 示例：
来源：LeetCode第25题 代码实现： var reverse = function (head, tail) { let prev = tail.next; let p = head; while (prev !== tail) { let tmp = p.next; p.next = prev; prev = p; p = tmp; } return [tail, head]; }; var reverseKGroup = function (head, k) { let vnode = new ListNode(0, head); let pre = vnode; while (head) { let tail = pre; // 查看剩余部分长度是否大于等于 k for (let i = 0; i < k; i++) { tail = tail.next; if (!tail) { return vnode.next; } } let tmp = tail.next; //反转每个子链表 [head, tail] = reverse(head, tail); // 把子链表重新接回原链表 pre.next = head; tail.next = tmp; pre = tail; head = tmp; } return vnode.next; }; 10.最长递增子序列题目：给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 示例：
来源：LeetCode第300题 代码实现： var lengthOfLIS = function(nums) { let 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); };题目扩展：给你一个整数数组 nums ，找出其最长严格递增子序列。 示例：
实现代码： function lengthOfLIS(nums) { if (!nums.length) return []; let dp = new Array(nums.length).fill(1); for (let i = 0; i < nums.length; i++) { for (let j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } //最长递增子序列的长度 let max = Math.max(...dp); let result = []; //倒序遍历,每次根据当前长度去获取数组中对应下标的值放入结果数组 for (let i = max; i >= 1; i--) { // 找到符合条件最后一项的下标，这样才能保证数组的顺序是正确的 let index = dp.lastIndexOf(i); // 存储对应的值，插入结果数组的最前面 result.unshift(nums[index]); // 对dp进行截取，保证只取最大项之前的数据 dp.length = index + 1; } return result; } 结语🔥如果此文对你有帮助的话，欢迎💗关注、👍点赞、⭐收藏、✍️评论，支持一下博主~ |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |