关于javascript:Leetcode-做题学算法周刊第八期

首发于微信公众号《前端成长记》，写于 2020.05.07

背景

本文记录刷题过程中的整个思考过程，以供参考。次要内容涵盖：

• 题目剖析构想
• 编写代码验证
• 查阅别人解法
• 思考总结

目录

• 155.最小栈
• 160.相交链表
• 167.两数之和II输出有序数组
• 168.Excel表列名称
• 169.求众数

Easy

155.最小栈

题目地址

题目形容

设计一个反对 push，pop，top 操作，并能在常数工夫内检索到最小元素的栈。

• push(x) -- 将元素 x 推入栈中。
• pop() -- 删除栈顶的元素。
• top() -- 获取栈顶元素。
• getMin() -- 检索栈中的最小元素。

示例：

MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();   --> 返回 -3.minStack.pop();minStack.top();      --> 返回 0.minStack.getMin();   --> 返回 -2.

题目剖析构想

这道题感觉就是构造函数，仅此而已，给函数的原型加一些办法。差别就在办法实现自身上，这个就写一个集体的思路吧，外部保护每次操作后的最小值数组。当然用差值数组和最小值也是能够的。

编写代码验证

Ⅰ.外部保护最小值数组

代码：

/** * initialize your data structure here. */var MinStack = function() {    // 栈内数据用数组存储    this.stacks = []    this.mins = []};/** * @param {number} x * @return {void} */MinStack.prototype.push = function(x) {    this.stacks.push(x)    // 比以后最小值小的数都须要存住    if (!this.mins.length || this.mins[this.mins.length - 1] >= x) {        this.mins.push(x)    }};/** * @return {void} */MinStack.prototype.pop = function() {    // 如果推出的是最小值，那最小值数组也同步更新即可    if (this.stacks.pop() === this.mins[this.mins.length - 1]) {        this.mins.pop()    }};/** * @return {number} */MinStack.prototype.top = function() {    return this.stacks.length ? this.stacks[this.stacks.length - 1] : undefined};/** * @return {number} */MinStack.prototype.getMin = function() {    return this.mins[this.mins.length - 1]};

后果：

• 18/18 cases passed (116 ms)
• Your runtime beats 89.63 % of javascript submissions
• Your memory usage beats 7.49 % of javascript submissions (44.9 MB)
• 工夫复杂度： O(1)

Ⅱ.差值数组和最小值

代码：

/** * initialize your data structure here. */var MinStack = function() {    // 栈内数据用数组存储    this.stacks = []    this.min = Infinity};/** * @param {number} x * @return {void} */MinStack.prototype.push = function(x) {    if (!this.stacks.length) {        this.min = x        // x - this.min = 0        this.stacks.push(0)    } else {        // 先存差值再更新最小值        this.stacks.push(x - this.min)        if (x < this.min) this.min = x    }};/** * @return {void} */MinStack.prototype.pop = function() {    // 以后值比最小值小，则须要    let val = this.stacks.pop()    if (val < 0) {        this.min -= val    }};/** * @return {number} */MinStack.prototype.top = function() {    if (this.stacks[this.stacks.length - 1] < 0) {        // 以后最小值就是推出项的值        return this.min    } else {        return this.stacks[this.stacks.length - 1] + this.min    }};/** * @return {number} */MinStack.prototype.getMin = function() {    return this.min};

后果：

• 18/18 cases passed (124 ms)
• Your runtime beats 71.47 % of javascript submissions
• Your memory usage beats 16.67 % of javascript submissions (44.5 MB)
• 工夫复杂度： O(1)

查阅别人解法

这里看到有用栈的，JS 外面我就不构建了。另外还看见一种把值和最小值混合存储的思路，挺有意思的。

Ⅰ.混合存储

代码：

/** * initialize your data structure here. */var MinStack = function() {    // 栈内数据用数组存储    this.stacks = []    this.min = Infinity};/** * @param {number} x * @return {void} */MinStack.prototype.push = function(x) {    // 先推上一步的最小值，再推原数据    if (x <= this.min) {        this.stacks.push(this.min)        this.min = x    }    this.stacks.push(x)};/** * @return {void} */MinStack.prototype.pop = function() {    // 如果推出值等于以后最小值，则将最小值更新为上一个最小值    if (this.stacks.pop() === this.min) {        this.min = this.stacks.pop()    }};/** * @return {number} */MinStack.prototype.top = function() {    return this.stacks[this.stacks.length - 1]};/** * @return {number} */MinStack.prototype.getMin = function() {    return this.min};

后果：

• 18/18 cases passed (124 ms)
• Your runtime beats 71.47 % of javascript submissions
• Your memory usage beats 7.15 % of javascript submissions (45 MB)
• 工夫复杂度： O(1)

思考总结

我集体是不举荐混合存储的，因为如果须要拓展查最大值，那整体逻辑实际上都须要调整。而后面两种办法，都只须要减少最大值数组或者最大值即可。

160.相交链表

题目地址

题目形容

编写一个程序，找到两个单链表相交的起始节点。

如上面的两个链表：

在节点 c1 开始相交。

留神：

• 如果两个链表没有交点，返回 null.
• 在返回后果后，两个链表仍须放弃原有的构造。
• 可假定整个链表构造中没有循环。
• 程序尽量满足 O(n) 工夫复杂度，且仅用 O(1) 内存。

题目剖析构想

这道题如果不加限度的话，办法还是很多的，比如说打标识，或者哈表表都能够解决问题。如果要满足内存要求的话，必然就不能应用哈希表。要满足放弃原有构造，那就不能用打标识的办法了。这里有个取巧的计划，因为不存在循环，两者相加的总长度相等，所以如果存在交点，那结尾必然相等。

编写代码验证

Ⅰ.打标识

代码：

/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */var getIntersectionNode = function(headA, headB) {    // 因为是内存援用指向，取巧了    while(headA) {        headA.FLAG = true        headA = headA.next    }    while(headB) {        if (headB.FLAG) return headB        headB = headB.next    }    return null};

后果：

• 45/45 cases passed (104 ms)
• Your runtime beats 50.31 % of javascript submissions
• Your memory usage beats 5.01 % of javascript submissions (45.3 MB)
• 工夫复杂度： O(m + n)

Ⅱ.哈希表法

代码：

/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */var getIntersectionNode = function(headA, headB) {    let hash = new Set()    while(headA) {        hash.add(headA)        headA = headA.next    }    while(headB) {        if (hash.has(headB)) return headB        headB = headB.next    }    return null};

后果：

• 45/45 cases passed (100 ms)
• Your runtime beats 67.12 % of javascript submissions
• Your memory usage beats 68.1 % of javascript submissions (43.8 MB)
• 工夫复杂度： O(m + n)

Ⅲ.双指针法

代码：

/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */var getIntersectionNode = function(headA, headB) {    // 用两个指针同时右移，A完了之后指向B持续右移    let pA = headA    let pB = headB    while(pA !== pB) {        pA = pA ? pA.next : headB        pB = pB ? pB.next : headA    }    return pA};

后果：

• 45/45 cases passed (100 ms)
• Your runtime beats 67.12 % of javascript submissions
• Your memory usage beats 72.7 % of javascript submissions (43.3 MB)
• 工夫复杂度： O(m + n)

查阅别人解法

这里个别的二重循环就不说了，跟两个数组中找同样的数一样，没有什么区别，效率也比拟底下。另外看见一个有意思的思路是，把两个链表拼成环，转化成找环节点的问题。

Ⅰ.转换环

代码：

/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */var getIntersectionNode = function(headA, headB) {    if (headA == null || headB == null)  return null;    let curA = headA,curB = headB;    while(curA.next != null){        curA = curA.next;    }    curA.next = headA;    let fast = headB,slow = headB;    while(fast != null&&fast.next != null){          slow = slow.next;          fast = fast.next.next;          if(slow == fast){             slow = headB;             while(slow != fast){                 slow = slow.next;                 fast = fast.next;            }            curA.next = null;            return fast;          }    }    curA.next = null;    return null;};

后果：

• 45/45 cases passed (104 ms)
• Your runtime beats 50.31 % of javascript submissions
• Your memory usage beats 12.39 % of javascript submissions (44.6 MB)
• 工夫复杂度： O(m + n)

思考总结

这里要满足空间复杂度要求，那就不能用哈希表法；要满足不扭转原始数据构造，那就不能用标识法。所以这种状况下我更倡议应用双指针法来间接作答，而转换为环尽管是一个思路，然而其实由一个问题转换为另一个问题，心智累赘没有升高。

167.两数之和II输出有序数组

题目地址

题目形容

给定一个已依照 升序排列 的有序数组，找到两个数使得它们相加之和等于指标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

阐明:

• 返回的下标值（index1 和 index2）不是从零开始的。
• 你能够假如每个输出只对应惟一的答案，而且你不能够重复使用雷同的元素。

示例:

输出: numbers = [2, 7, 11, 15], target = 9输入: [1,2]解释: 2 与 7 之和等于指标数 9 。因而 index1 = 1, index2 = 2 。

题目剖析构想

这道题有几个中央做了阐明了，须要留神一下：有序的升序数组、下标不从零开始、不能重复使用雷同元素。之前第一期的两数之和的办法就不做剖析了（两次遍历和哈希表），这里能够利用有序数组来提高效率，利用首尾指针，来做判断，能够了解为夹逼准则。

编写代码验证

Ⅰ.双指针夹逼

代码：

/** * @param {number[]} numbers * @param {number} target * @return {number[]} */var twoSum = function(numbers, target) {    let start = 0    let end = numbers.length - 1    while(start < end) {        const sum = numbers[start] + numbers[end]        if (sum === target) {            // 不从零开始，所以须要加一            return [start + 1, end + 1]        } else if (sum > target) {            end--        } else {            start++        }    }    // 因为有惟一输入，所以必然有后果，也不须要做非凡解决    return [-1, -1]};

后果：

• 17/17 cases passed (64 ms)
• Your runtime beats 87.01 % of javascript submissions
• Your memory usage beats 40.91 % of javascript submissions (35.2 MB)
• 工夫复杂度： O(n)

查阅别人解法

看了一下解法，没有效率更高的形式了。一些根本的解法在第一期的第一题能够查阅。另外有一个是以一个数为基准，二分查找，然而这样的话其实只是在两次循环根底上做了优化，甚至还不如哈希表效率高。所以，这里就没有看见其余有不同思路的解法了。

思考总结

既然数组有序，咱们就能够用夹逼准则来求解，在这道题我感觉是最合适，也是最高效的解法了。

168.Excel表列名称

题目地址

题目形容

给定一个正整数，返回它在 Excel 表中绝对应的列名称。

例如，

    1 -> A    2 -> B    3 -> C    ...    26 -> Z    27 -> AA    28 -> AB    ...

示例:

输出: 1输入: "A"输出: 28输入: "AB"输出: 701输入: "ZY"

题目剖析构想

这道题其实很清晰，就是将10进制转成26进制的问题。间接用取余运算就行，惟一的难点在于如何转成26进制。

编写代码验证

Ⅰ.取余

代码：

/** * @param {number} n * @return {string} */var convertToTitle = function(n) {    let str = ''    while( n > 0) {        // 因为A代表1，减一就能从0开始匹配进制转换        n--        str += String.fromCharCode(n % 26 + 'A'.charCodeAt())        n = Math.floor(n / 26)    }    return str.split('').reverse().join('')};

后果：

• 18/18 cases passed (64 ms)
• Your runtime beats 57.06 % of javascript submissions
• Your memory usage beats 100 % of javascript submissions (33.7 MB)
• 工夫复杂度： O(n)

查阅别人解法

看了一下解法，思路没有什么区别，有一个有意思的就是强行转换成一行，这里也列一下。

Ⅰ.单行代码

代码：

/** * @param {number} n * @return {string} */var convertToTitle = function(n, s = '') {    return !n-- ? s : convertToTitle(~~(n / 26), String.fromCharCode('A'.charCodeAt() + n % 26) + s);};

后果：

• 18/18 cases passed (60 ms)
• Your runtime beats 76.47 % of javascript submissions
• Your memory usage beats 100 % of javascript submissions (33.7 MB)
• 工夫复杂度： O(n)

思考总结

这道题实质上就是一道进制转换的题目，没有什么太大的难度。

169.求众数

题目地址

题目形容

给定一个大小为 n 的数组，找到其中的少数元素。少数元素是指在数组中呈现次数大于 ⌊ n/2 ⌋ 的元素。

你能够假如数组是非空的，并且给定的数组总是存在少数元素。

示例:

输出: [3,2,3]输入: 3输出: [2,2,1,1,1,2,2]输入: 2

题目剖析构想

这道题就是找出呈现次数最多的元素，依照惯例的思路的话有这么两种形式。

• 哈希法，通过哈希表记录每个数呈现的次数，找到呈现次数最多的数
• 分治法，将数组二分，别离求两边的少数元素，而后找出呈现次数多的元素

因为这里是找少数元素，有个前提是保障呈现次数大于一半，这里也能够取巧，先排序，排序后两头那个数肯定是少数元素。

编写代码验证

Ⅰ.哈希法

代码：

/** * @param {number[]} nums * @return {number} */var majorityElement = function(nums) {    let hash = {}    for(let i = 0; i < nums.length; i++) {        if (hash[nums[i]] === undefined) {            hash[nums[i]] = 1        } else {            hash[nums[i]] += 1            // 大于等于一半就能够间接认定为众数了            if (hash[nums[i]] >= nums.length / 2) {                return nums[i]            }        }    }    let count = 0    let val = null    for(let key in hash) {        if (hash[key] > count) {            count = hash[key]            val = key        }    }    return val};

后果：

• 46/46 cases passed (88 ms)
• Your runtime beats 41.1 % of javascript submissions
• Your memory usage beats 92.86 % of javascript submissions (37.6 MB)
• 工夫复杂度： O(n)

Ⅱ.分治法

代码：

/** * @param {number[]} nums * @return {number} */var majorityElement = function(nums) {    function countEle(arr, num, l, h) {        let count = 0        for(let i = l; i <= h; i++) {            if (arr[i] === num) {                count += 1            }        }        return count    }    function getEle(arr, l, h) {        debugger        if (l === h) { // 就一个元素，间接返回            return arr[l]        }        // 取中位数，减法次要为了避免溢出        let mid = parseInt((h - l) / 2 + l)        // 右边的众数        let left = getEle(arr, l, mid)        // 左边的众数        let right = getEle(arr, mid + 1, h)        // 如果左右两边数组为同一个众数，则间接返回        if (left === right) {            return left        }        // 比拟众数呈现次数，留神：要用父数组取呈现次数做比拟        // 要不像这种将返回谬误后果：[4,5,4,4,4,5]        let leftCount = countEle(arr, left, l, h)        let rightCount = countEle(arr, right, l, h)        return leftCount > rightCount ? left : right    }    return getEle(nums, 0, nums.length - 1)};

后果：

• 46/46 cases passed (148 ms)
• Your runtime beats 5.98 % of javascript submissions
• Your memory usage beats 28.57 % of javascript submissions (38.2 MB)
• 工夫复杂度： O(nlog(n))

Ⅲ.排序法

代码：

/** * @param {number[]} nums * @return {number} */var majorityElement = function(nums) {    return nums.sort()[nums.length >>> 1]};

后果：

• 46/46 cases passed (100 ms)
• Your runtime beats 24.58 % of javascript submissions
• Your memory usage beats 92.86 % of javascript submissions (37.3 MB)
• 工夫复杂度： O(nlog(n))，齐全是数组排序的复杂度

查阅别人解法

发现了一种叫做 Boyer Moore 投票算法。这个算法艰深点解释起来还是很容易了解的，其实能够了解为相互对消。每一个众数和一个其余数对消，剩下的必然就是众数了。

Ⅰ.投票算法

代码：

/** * @param {number[]} nums * @return {number} *//** * @param {number[]} nums * @return {number} */var majorityElement = function(nums) {    let count = 0    let candidate = null    for(let i = 0; i < nums.length; i++) {        if (count === 0) {            candidate = nums[i]        }        // 同样的数累加，不同的数相减，能够了解为同数量对消，对消完产生新的备选数        count += (nums[i] === candidate) ? 1 : -1    }    return candidate};

后果：

• 46/46 cases passed (80 ms)
• Your runtime beats 56.39 % of javascript submissions
• Your memory usage beats 92.86 % of javascript submissions (37.3 MB)
• 工夫复杂度： O(n)

思考总结

比拟不言而喻的是，这道题应用投票算法只需遍历一次，也不须要额定的空间，为最优解。

（完）

本文为原创文章，可能会更新知识点及修改谬误，因而转载请保留原出处，不便溯源，防止古老谬误常识的误导，同时有更好的浏览体验
如果能给您带去些许帮忙，欢送 ⭐️star 或 ✏️ fork
(转载请注明出处：https://chenjiahao.xyz)