乐趣区

JS算法题之leetcode2130

jiezi

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;
    }
};
退出移动版