南宁建设厅网站,南京站建设,九江室内设计学校,学校网站建设自查报告前言 #x1f4eb; 大家好#xff0c;我是南木元元#xff0c;热爱技术和分享#xff0c;欢迎大家交流#xff0c;一起学习进步#xff01; #x1f345; 个人主页#xff1a;南木元元 现在前端的面试中#xff0c;算法出现的频率越来越高了#xff0c;大厂更是必考算…前言 大家好我是南木元元热爱技术和分享欢迎大家交流一起学习进步 个人主页南木元元 现在前端的面试中算法出现的频率越来越高了大厂更是必考算法 。本文就来分享一下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中是否存在三个元素abc 使得 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;
}
结语
如果此文对你有帮助的话欢迎关注、点赞、⭐收藏、✍️评论支持一下博主~
