【面试】盘点10个高频的前端算法题,你全都会了吗?

2024-02-16 14:36

本文主要是介绍【面试】盘点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] <= nums2[j]) {nums1[k--] = nums2[j--];} else {nums1[k--] = nums1[i--];}}return nums1;
};

2.两数之和

题目:给定一个数组nums和一个目标值target,在数组中找出和为目标值的两个数,并返回下标。

示例:

来源:LeetCode第1题

代码实现:

// 哈希法,利用map
var twoSum = function (nums, target) {let map = new Map();// 遍历当前元素,并在map中寻找是否有匹配的keyfor (let i = 0; i < nums.length; i++) {if (map.has(target - nums[i])) {return [i, map.get(target - nums[i])];} else {// 没找到与当前匹配的元素,就把当前元素及对应下标加入mapmap.set(nums[i], i);}}
};

3.三数之和

题目:给你一个包含 n 个整数的数组 nums,判断nums中是否存在三个元素a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

示例:

来源:LeetCode第15题

代码实现:

// 双指针法
var threeSum = function (nums) {let res = [];//排序nums.sort((a, b) => a - b);for (let i = 0; i < nums.length; i++) {//如果当前第一个数大于0直接返回resif (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;// 查看剩余部分长度是否大于等于 kfor (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;
}

结语

🔥如果此文对你有帮助的话,欢迎💗关注、👍点赞、⭐收藏、✍️评论,支持一下博主~ 

这篇关于【面试】盘点10个高频的前端算法题,你全都会了吗?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/714822

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

这15个Vue指令,让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件,按住 Control 和回车键再显示它吗?小菜一碟: <template

【 html+css 绚丽Loading 】000046 三才归元阵

前言:哈喽,大家好,今天给大家分享html+css 绚丽Loading!并提供具体代码帮助大家深入理解,彻底掌握!创作不易,如果能帮助到大家或者给大家一些灵感和启发,欢迎收藏+关注哦 💕 目录 📚一、效果📚二、信息💡1.简介:💡2.外观描述:💡3.使用方式:💡4.战斗方式:💡5.提升:💡6.传说: 📚三、源代码,上代码,可以直接复制使用🎥效果🗂️目录✍️

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig