共计 5987 个字符，预计需要花费 15 分钟才能阅读完成。
JS 算法题之 leetcode(21~30)
题目均来自乐扣（leetcode）
合并两个有序链表
题目描述
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4解答
这题不难，利用递归就能实现，两个链表双双比较即可
var mergeTwoLists = function(l1, l2) {if(l1 == null){return l2;}
if(l2 == null){return l1;}
if(l1.val < l2.val){l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else{l2.next = mergeTwoLists(l1, l2.next)
return l2
}
};括号生成
题目描述
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
["((()))",
"(()())",
"(())()",
"()(())",
"()()()"]
解答
这题我们用递归来实现，判断左括号数是否小于 n 切大于右括号数，否则就退出递归
var recursiveFun = (str, l, r, n, res) => {
// str 是字符串，l 是左括号数量，r 是右括号数量，n 是双括号数量，res 是返回结果
if(l == n && r == n){res.push(str);
return;
}
// 左括号数 > 右括号数，下一个可以为左括号，也可以为右括号
if(l < n){recursiveFun(str + '(', l+1, r, n, res);
}
if(l > r){recursiveFun(str + ')', l, r+1, n ,res)
}
}
var generateParenthesis = function(n) {if(n == 0){return []
}
else if(n == 1){return ["()"]
}
else{let res = []
recursiveFun("", 0, 0, n, res)
return res;
}
};合并 K 个排序链表
题目描述
合并 k 个排序链表，返回合并后的排序链表。
示例
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6解答
这题其实不太难，跟上面合并两个一样，只是多一层判断而已，直接看代码
var mergeKLists = function(lists) {if(lists.length == 0){return null}
else if(lists.length == 1){return lists[0]
}
else if(lists.length == 2){let l1 = lists[0], l2 = lists[1];
if(l1 == null){return l2;}
if(l2 == null){return l1}
if(l1.val <= l2.val){l1.next = mergeKLists([l1.next, l2])
return l1;
}
else{l2.next = mergeKLists([l1, l2.next])
return l2;
}
}
else if(lists.length == 3){return mergeKLists([lists[0], mergeKLists(lists.slice(1))])
}
else{return mergeKLists([mergeKLists(lists.slice(0, 2)), mergeKLists(lists.slice(2))])
}
};两两交换链表中的节点
题目描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例
给定 1->2->3->4, 你应该返回 2->1->4->3.解答
这题也是用递归来做，两两互换（不足两个直接返回剩余的），第一个指向第二个的 next（其实是另外一个递归函数），而第二个指向第一个，最终返回第二个节点即可
var swapPairs = function(head) {if(head == null || head.next == null){return head;}
else{
let nextList = head.next;
if(nextList.next){head.next = swapPairs(nextList.next)
}
else{head.next = null}
nextList.next = head;
return nextList;
}
};K 个一组翻转链表
题目描述
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5解答
这题稍微有点复杂，先获取 k 个节点，然后打断这 k 个节点跟其他节点的连接，然后利用三指针的方法翻转这 k 个节点，然后重新放进整体中，仔细看代码注释就能懂。
// 获取第 k 个节点
let getEndNode = (start, k) => {
let cur = start, end = null;
while(cur){if(k == 1){
end = cur;
break;
}
else{
cur = cur.next;
k--;
}
}
return end;
}
// 三指针方法 翻转链表
let reverserFun = (start) => {
let curNode = start, prevNode = null, res = null;
while(curNode){
let nextNode = curNode.next;
if(curNode.next){res = curNode.next;}
curNode.next = prevNode;
prevNode = curNode;
curNode = nextNode;
}
return res;
}
var reverseKGroup = function(head, k) {if(k < 2 || head == null || head.next == null){return head;}
let cur = head, res = null, prev = null;
while(cur && cur.next){
let start = cur;
let end = getEndNode(start, k);
if(end == null){
// 剩余节点不足 k 个
break;
}
else{cur = end.next;}
// 打断要翻转的 k 个节点
end.next = null;
// 翻转链表，start 变成最后一个节点，end 变成第一个节点
reverserFun(start);
// 再将链表连接起来
start.next = cur;
// 将 prev 指向翻转后的最后一个节点，用于下次指向翻转后的第一个节点
if(prev == null){
// 第一次处理
prev = start;
}
else{
prev.next = end;
prev = start;
}
// 最终返回的结果处理
if(res == null){res = end;}
}
if(res == null){return head;}
else{return res;}
};删除排序数组中的重复项
题目描述
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。你不需要考虑数组中超出新长度后面的元素。解答
这题简单，基于一个已经排好序的数组进行去重，但是注意的是不能使用额外空间，那就只能原地去重，既然已经排好序了，直接两两比较，遍历一次便可。
var removeDuplicates = function(nums) {
let i = 1;
while(i < nums.length){if(nums[i] == nums[i-1]){nums.splice(i, 1);
}
else{i++;}
}
return nums.length;
};移除元素
题目描述
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
示例
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。解答
这题跟上面的那道差不多，直接看代码
var removeElement = function(nums, val) {
let i = 0;
while(i < nums.length){if(nums[i] == val){nums.splice(i, 1);
}
else{i++;}
}
return nums.length;
};实现 strStr()
题目描述
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。
示例
输入: haystack = "hello", needle = "ll"
输出: 2
输入: haystack = "aaaaa", needle = "bba"
输出: -1解答
坦白讲，这题。。。不知道是不是我理解的问题，这题直接 indexOf 就完事了。。。
var strStr = function(haystack, needle) {if(needle == ""){return 0;}
return haystack.indexOf(needle)
};两数相除
题目描述
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
示例
输入: dividend = 10, divisor = 3
输出: 3
输入: dividend = 7, divisor = -3
输出: -2解答
这题也挺简单的，就是实现一个除法，不能使用加法乘法以及 mod，那就用减法便可，不过要注意符号。
let MAX = Math.pow(2, 31) - 1
let MIN = -1 * Math.pow(2, 31)
var divide = function(dividend, divisor) {if(dividend == 0){return 0;}
else{let num1 = Math.abs(dividend), num2 = Math.abs(divisor), res = 0;
if(num2 == 1){res = num1;}
else{while(num1 >= num2){
res++;
num1 -= num2;
}
}
if((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)){res = Number(`-${res}`);
}
if(res < MIN){return MIN;}
else if(res > MAX){return MAX;}
else{return res}
}
};串联所有单词的子串
题目描述
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例
输入：s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar"。输出的顺序不重要, [9,0] 也是有效答案。输入：s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：[]
解答
这题稍微有点复杂，我们采用窗口移动的方法，先计算出数组元素字符的总长度 windowLen, 从 s 的 0 下标开始，逐 windowLen 个的字符串提取出来，然后拿去跟 words 对比，将该字符串拆分为若干个单词，若这若干个单词刚好跟 words 一一对应，那便返回 true，记录下标。认真看代码注释即可
let isMatch = (str, words, itemLen) => {let arr = [...words];
while(str.length && words.length){let word = str.slice(0, itemLen);
let idx = arr.indexOf(word);
if(idx == -1){
// 不匹配
return false;
}
else{arr.splice(idx, 1);
str = str.slice(itemLen);
}
}
return true;
}
var findSubstring = function(s, words) {if(s == "" || words.length == 0){return []
}
else{let res = [];
if(words[0] == ""){for(let i = 0; i < s.length; i++){res.push(i);
}
}
else{
// 窗口移动法
// 单个单词长度、窗口长度、窗口下标、let itemLen = words[0].length, windowLen = itemLen * words.length, windowIdx = 0;
while(windowIdx + windowLen <= s.length){if(isMatch(s.slice(windowIdx, windowIdx + windowLen), words, itemLen)){res.push(windowIdx)
}
windowIdx++;
}
}
return res;
}
};
