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) - 1let 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; }};