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

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

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

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

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

题目地址

设计一个反对 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)

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

题目地址

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

如上面的两个链表：

在节点 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)

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

题目地址

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

函数应该返回这两个下标值 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)

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

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

题目地址

给定一个正整数，返回它在 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)

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

题目地址

给定一个大小为 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)

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

背景

目录

Easy

155. 最小栈

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结

160. 相交链表

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结

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

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结

168.Excel 表列名称

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结

169. 求众数

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结