前言
大家好，我是南木元元，热爱技术和分享，欢迎大家交流，一起学习进步！
个人主页：南木元元
现在前端的面试中，算法出现的频率越来越高了，大厂更是必考算法 。本文就来分享一下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中寻找是否有匹配的key
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i])) {
return [i, map.get(target - nums[i])];
} else {
// 没找到与当前匹配的元素，就把当前元素及对应下标加入map
map.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直接返回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;
}
结语
如果此文对你有帮助的话，欢迎关注、点赞、⭐收藏、✍️评论，支持一下博主~
推荐链接
您阅读本篇文章共花了：
发表评论