【Leetcode 做题学算法周刊】第四期

时间:2019-11-21 McChen 人气:1

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

背景

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

题目分析设想
编写代码验证
查阅他人解法
思考总结

Easy

67.二进制求和

题目地址

题目描述

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例：

输入: a = "11", b = "1"
输出: "100"

输入: a = "1010", b = "1011"
输出: "10101"

题目分析设想

这道题又是一道加法题，所以记住下，直接转数字进行加法可能会溢出，所以不可取。所以我们需要遍历每一位来做解答。我这有两个大方向：补0后遍历，和不补0遍历。但是基本的依据都是本位相加，逢2进1即可，类似手写10进制加法。

补0后遍历，可以采用先算出的位数推入数组最后反转，也可以采用先算出的位数填到对应位置后直接输出
不补0遍历，根据短数组的长度进行遍历，长数组剩下的数字与短数组生成的进位进行计算

查阅他人解法

Ⅰ.补0后遍历，先算先推

代码：

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let times = Math.max(a.length, b.length) // 需要遍历次数
    // 补 0
    while(a.length < times) {
        a = '0' + a
    }
    while(b.length < times) {
        b = '0' + b
    }
    let res = []
    let carry = 0 // 是否进位
    for(let i = times - 1; i >= 0; i--) {
        const num = carry + (a.charAt(i) | 0) + (b.charAt(i) | 0)
        carry = num >= 2 ? 1 : 0
        res.push(num % 2)
    }
    if (carry === 1) {
        res.push(1)
    }
    return res.reverse().join('')
};

结果：

294/294 cases passed (68 ms)
Your runtime beats 95.13 % of javascript submissions
Your memory usage beats 72.58 % of javascript submissions (35.4 MB)
时间复杂度 O(n)

Ⅱ.补0后遍历，按位运算

代码：

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let times = Math.max(a.length, b.length) // 需要遍历次数
    // 补 0
    while(a.length < times) {
        a = '0' + a
    }
    while(b.length < times) {
        b = '0' + b
    }
    let res = []
    let carry = 0 // 是否进位
    for(let i = times - 1; i >= 0; i--) {
        res[i] = carry + (a.charAt(i) | 0) + (b.charAt(i) | 0)
        carry = res[i] >= 2 ? 1 : 0
        res[i] %= 2
    }
    if (carry === 1) {
        res.unshift(1)
    }
    return res.join('')
};

结果：

294/294 cases passed (60 ms)
Your runtime beats 99.65 % of javascript submissions
Your memory usage beats 65.82 % of javascript submissions (35.5 MB)
时间复杂度 O(n)

Ⅲ.不补0遍历

当然处理方式还是可以选择上面两种，我这就采用先算先推来处理了。

代码：

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let max = Math.max(a.length, b.length) // 最大长度
    let min = Math.min(a.length, b.length) // 最大公共长度

    // 将长字符串拆成两部分
    let left = a.length > b.length ? a.substr(0, a.length - b.length) : b.substr(0, b.length - a.length)
    let right = a.length > b.length ? a.substr(a.length - b.length) : b.substr(b.length - a.length)

    // 公共长度部分遍历
    let rightRes = []
    let carry = 0
    for(let i = min - 1; i >= 0; i--) {
        const num = carry + (right.charAt(i) | 0) + (((a.length > b.length ? b : a)).charAt(i) | 0)
        carry = num >= 2 ? 1 : 0
        rightRes.push(num % 2)
    }

    let leftRes = []
    for(let j = max - min - 1; j >= 0; j--) {
        const num = carry + (left.charAt(j) | 0)
        carry = num >= 2 ? 1 : 0
        leftRes.push(num % 2)
    }

    if (carry === 1) {
        leftRes.push(1)
    }
    return leftRes.reverse().join('') + rightRes.reverse().join('')
};

结果:

294/294 cases passed (76 ms)
Your runtime beats 80.74 % of javascript submissions
Your memory usage beats 24.48 % of javascript submissions (36.2 MB)
时间复杂度 O(n)

查阅他人解法

看到一些细节上的区别，我这使用 '1' | 0 来转数字，有的使用 ''1' - '0''。另外还有就是初始化结果数组长度为最大长度加1后，最后判断首位是否为0需要剔除的，我这使用的是判断最后是否还要进位补1。

这里还看到用一个提案中的 BigInt 类型来解决的

Ⅰ.BigInt

代码：

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    return (BigInt("0b"+a) + BigInt("0b"+b)).toString(2);
};

结果：

294/294 cases passed (52 ms)
Your runtime beats 100 % of javascript submissions
Your memory usage beats 97.05 % of javascript submissions (34.1 MB)
时间复杂度 O(1)

思考总结

通过 BigInt 的方案我们能看到，使用原生方法确实性能更优。简单说一下这个类型，目前还在提案阶段，看下面的等式基本就能知道实现原理自己写对应 Hack 来实现了：

BigInt(10) = '10n'
BigInt(20) = '20n'
BigInt(10) + BigInt(20) = '30n'

虽然这种方式很友好，但是还是希望看到加法题的时候，能考虑到遍历按位处理。

69.x的平方根

题目地址

题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例：

输入: 4
输出: 2

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
     由于返回类型是整数，小数部分将被舍去。

题目分析设想

同样，这里类库提供的方法 Math.sqrt(x) 就不说了，这也不是本题想考察的意义。所以这里有几种方式：

暴力法，这里不用考虑溢出是因为x没溢出，所以即使加到平方根加1，也会终止循环
二分法，直接取中位数运算，可以快速排除当前区域一半的区间

编写代码验证

Ⅰ.暴力法

代码：

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x === 0) return 0
    let i = 1
    while(i * i < x) {
        i++
    }
    return i * i === x ? i : i - 1
};

结果：

1017/1017 cases passed (120 ms)
Your runtime beats 23 % of javascript submissions
Your memory usage beats 34.23 % of javascript submissions (35.7 MB)
时间复杂度 O(n)

Ⅱ.二分法

代码：

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x === 0) return 0
    let l = 1
    let r = x >>> 1
    while(l < r) {
        // 这里要用大于判断，所以取右中位数
        const mid = (l + r + 1) >>> 1

        if (mid * mid > x) {
            r = mid - 1
        } else {
            l = mid
        }
    }
    return l
};

结果：

1017/1017 cases passed (76 ms)
Your runtime beats 96.08 % of javascript submissions
Your memory usage beats 59.17 % of javascript submissions (35.5 MB)
时间复杂度 O(log2(n))

查阅他人解法

这里看见了两个有意思的解法：

2的幂次底层优化
牛顿法

Ⅰ.幂次优化

稍微解释一下，二分法需要做乘法运算，他这里改用加减法

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let l = 0
    let r = 1 << 16 // 2的16次方，这里我猜是因为上限2^32所以取一半
    while (l < r - 1) {
        const mid = (l + r) >>> 1
        if (mid * mid <= x) {
            l = mid
        } else {
            r = mid
        }
    }
    return l
};

结果：

1017/1017 cases passed (72 ms)
Your runtime beats 98.46 % of javascript submissions
Your memory usage beats 70.66 % of javascript submissions (35.4 MB)

时间复杂度 O(log2(n))

Ⅱ.牛顿法

算法说明：

在迭代过程中，以直线代替曲线，用一阶泰勒展式（即在当前点的切线）代替原曲线，求直线与 xx 轴的交点，重复这个过程直到收敛。

首先随便猜一个近似值 x，然后不断令 x 等于 x 和 a/x 的平均数，迭代个六七次后 x 的值就已经相当精确了。

公式可以写为 X[n+1]=(X[n]+a/X[n])/2

代码：

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x === 0 || x === 1) return x

    let a = x >>> 1
    while(true) {
        let cur = a
        a = (a + x / a) / 2
        // 这里是为了消除浮点运算的误差，1e-5是我试出来的
        if (Math.abs(a - cur) < 1e-5) {
            return parseInt(cur)
        }
    }
};

结果：

1017/1017 cases passed (68 ms)
Your runtime beats 99.23 % of javascript submissions
Your memory usage beats 9.05 % of javascript submissions (36.1 MB)
时间复杂度 O(log2(n))

思考总结

这里就提一下新接触的牛顿法吧，实际上是牛顿迭代法，主要是迭代操作。由于在单根附近具有平方收敛，所以可以转换成线性问题去求平方根的近似值。主要应用场景有这两个方向：

求方程的根
求解最优化问题

70.爬楼梯

题目地址

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

题目分析设想

这道题很明显可以用动态规划和斐波那契数列来求解。然后我们来看看其他正常思路，如果使用暴力法的话，那么复杂度将会是 2^n，很容易溢出，但是如果能够优化成 n 的话，其实还可以求解的。所以这道题我就从以下三个方向来作答：

哈希递归，也就是暴力运算的改进版，通过存下算过的值降低复杂度
动态规划
斐波那契数列

编写代码验证

Ⅰ.哈希递归

代码：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let hash = {}
    return count(0)
    function count (i) {
        if (i > n) return 0
        if (i === n) return 1

        // 这步节省运算
        if(hash[i] > 0) {
            return hash[i]
        }

        hash[i] = count(i + 1) + count(i + 2)
        return hash[i]
    }
};

结果：

45/45 cases passed (52 ms)
Your runtime beats 98.67 % of javascript submissions
Your memory usage beats 48.29 % of javascript submissions (33.7 MB)
时间复杂度 O(n)

Ⅱ.动态规划

代码：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1) return 1
    if (n === 2) return 2
    // dp[0] 多一位空间，省的后面做减法
    let dp = new Array(n + 1).fill(0)
    dp[1] = 1
    dp[2] = 2
    for(let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
};

结果：

45/45 cases passed (48 ms)
Your runtime beats 99.48 % of javascript submissions
Your memory usage beats 21.49 % of javascript submissions (33.8 MB)
时间复杂度 O(n)

Ⅲ.斐波那契数列

其实斐波那契数列就可以用动态规划来实现，所以下面的代码思路很相似。

代码：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1) return 1
    if (n === 2) return 2
    let num1 = 1
    let num2 = 2
    for(let i = 3; i <= n; i++) {
        let count = num1 + num2
        num1 = num2
        num2 = count
    }
    // 相当于fib(n)
    return num2
};

结果：

45/45 cases passed (56 ms)
Your runtime beats 95.49 % of javascript submissions
Your memory usage beats 46.1 % of javascript submissions (33.7 MB)
时间复杂度 O(n)

查阅他人解法

查看题解发现这么几种解法：

斐波那契公式（原来有计算公式可以直接用，尴尬）
Binets 方法
排列组合

Ⅰ.斐波那契公式

代码：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const sqrt_5 = Math.sqrt(5)
    // 由于 F0 = 1，所以相当于需要求 n+1 的值
    const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2, n + 1)
    return Math.round(fib_n / sqrt_5)
};

结果：

45/45 cases passed (52 ms)
Your runtime beats 98.67 % of javascript submissions
Your memory usage beats 54.98 % of javascript submissions (33.6 MB)
时间复杂度 O(log(n))

Ⅱ.Binets 方法

算法说明：

使用矩阵乘法来得到第 n 个斐波那契数。注意需要将初始项从 fib(2)=2,fib(1)=1 改成 fib(2)=1,fib(1)=0 ，来达到矩阵等式的左右相等。

解法参考官方题解

代码：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {

    function pow(a, n) {
        let ret = [[1,0],[0,1]] // 矩阵
        while(n > 0) {
            if ((n & 1) === 1) {
                ret = multiply(ret, a)
            }
            n >> 1
            a = multiply(a, a)
        }
        return ret;
    }
    function multiply(a, b) {
        let c = [[0,0], [0,0]]
        for (let i = 0; i < 2; i++) {
            for(let j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
            }
        }
        return c
    }

    let q = [[1,1], [1, 0]]
    let res = pow(q, n)
    return res[0][0]
};

结果：

测试用例可以输出，提交发现超时。

这个笔者还没完全理解，所以很抱歉，暂时没有 js 相应代码分析，后续会补上。也欢迎您补充给我，感谢！

Ⅲ.排列组合

代码：

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    // n 个台阶走 i 次1阶和 j 次2阶走到，推导出 i + 2*j = n
    function combine(m, n) {
        if (m < n) [m, n] = [n, m];
        let count = 1;
        for (let i = m + n, j = 1; i > m; i--) {
            count *= i;
            if (j <= n) count /= j++;
        }
        return count;
    }
    let total = 0;
    // 取出所有满足条件的解
    for (let i = 0,j = n; j >= 0; j -= 2, i++) {
      total += combine(i, j);
    }
    return total;
};

结果：

45/45 cases passed (60 ms)
Your runtime beats 87.94 % of javascript submissions
Your memory usage beats 20.72 % of javascript submissions (33.8 MB)
时间复杂度 O(n^2)

思考总结

这种叠加的问题，首先就会想到动态规划的解法，刚好这里又满足斐波那契数列，所以我是推荐首选这两种解法。另外通过查看他人解法学到了斐波那契公式，以及站在排列组合的角度去解，开拓了思路。

83.删除排序链表中的重复元素

题目地址

题目描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例：

输入: 1->1->2
输出: 1->2

输入: 1->1->2->3->3
输出: 1->2->3

题目分析设想

注意一下，给定的是一个排序链表，所以只需要依次更改指针就可以直接得出结果。当然，也可以使用双指针来跳过重复项即可。所以这里有两个方向：

直接运算，通过改变指针指向
双指针，通过跳过重复项

如果是无序链表，我会建议先得到所有值然后去重后（比如通过Set）生成新链表作答。

编写代码验证

Ⅰ.直接运算

代码：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // 复制一个用做操作，由于对象是传址，所以改指针指向即可
    let cur = head
    while(cur !== null && cur.next !== null) {
        if (cur.val === cur.next.val) { // 值相等
            cur.next = cur.next.next
        } else {
            cur = cur.next
        }
    }
    return head
};

结果：

165/165 cases passed (76 ms)
Your runtime beats 87.47 % of javascript submissions
Your memory usage beats 81.21 % of javascript submissions (35.5 MB)
时间复杂度 O(n)

Ⅱ.双指针法

代码：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    // 新建哨兵指针和当前遍历指针
    if (head === null || head.next === null) return head
    let pre = head
    let cur = head
    while(cur !== null) {
        debugger
        if (cur.val === pre.val) {
            // 当前指针移动
            cur = cur.next
        } else {
            pre.next = cur
            pre = cur
        }
    }
    // 最后一项如果重复需要把head.next指向null
    pre.next = null
    return head
};

结果：

165/165 cases passed (80 ms)
Your runtime beats 77.31 % of javascript submissions
Your memory usage beats 65.1 % of javascript submissions (35.7 MB)
时间复杂度 O(n)

查阅他人解法

忘记了，这里确实还可以使用递归来作答。

Ⅰ.递归法

代码：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    if(head === null || head.next === null) return head
    if (head.val === head.next.val) { // 值相等
        return deleteDuplicates(head.next)
    } else {
        head.next = deleteDuplicates(head.next)
    }
    return head
};

结果：

165/165 cases passed (80 ms)
Your runtime beats 77.31 % of javascript submissions
Your memory usage beats 81.21 % of javascript submissions (35.5 MB)
时间复杂度 O(n)

思考总结

关于链表的题目一般都是通过修改指针指向来作答，区分单指针和双指针法。另外，遍历也是可以实现的。

88.合并两个有序数组

题目地址

题目描述

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

题目分析设想

之前我们做过删除排序数组中的重复项，其实这里也类似。可以从这几个方向作答：

数组合并后排序
遍历数组并进行插入
双指针法，轮流比较

但是由于题目有限定空间都在 nums1 ，并且不要写 return ，直接在 nums1 上修改，所以我这里主要的思路就是遍历，通过 splice 来修改数组。区别就在于遍历的方式方法。

从前往后
从后往前
合并后排序再赋值

编写代码验证

Ⅰ.从前往后

代码：

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // 两个数组对应指针
    let p1 = 0
    let p2 = 0
    // 这里需要提前把nums1的元素拷贝出来，要不然比较赋值后就丢失了
    let cpArr = nums1.splice(0, m)

    // 数组指针
    let p = 0
    while(p1 < m && p2 < n) {
        // 先赋值，再进行+1操作
        nums1[p++] = cpArr[p1] < nums2[p2] ? cpArr[p1++] : nums2[p2++]
    }
    // 已经有p个元素了，多余的元素要删除，剩余的要加上
    if (p1 < m) {
        // 剩余元素，p1 + m + n - p = m + n - (p - p1) = m + n - p2
        nums1.splice(p, m + n - p, ...cpArr.slice(p1, m + n - p2))
    }
    if (p2 < n) {
        // 剩余元素，p2 + m + n - p = m + n - (p - p2) = m + n - p1
        nums1.splice(p, m + n - p, ...nums2.slice(p2, m + n - p1))
    }
};

结果：

59/59 cases passed (48 ms)
Your runtime beats 100 % of javascript submissions
Your memory usage beats 64.97 % of javascript submissions (33.8 MB)
时间复杂度 O(m + n)

Ⅱ.从后往前

代码：

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // 避免 nums1 = [0,0,0,0], nums2 = [1,2] 这种 nums1.length > nums2.length 并且 m = 0
    nums1.splice(m, nums1.length - m)
    // 两个数组对应指针
    let p1 = m - 1
    let p2 = n - 1
    // 数组指针
    let p = m + n - 1
    while(p1 >= 0 && p2 >= 0) {
        // 先赋值，再进行-1操作
        nums1[p--] = nums1[p1] < nums2[p2] ? nums2[p2--] : nums1[p1--]
    }
    // 可能nums2有剩余，由于指针是下标，所以截取数量需要加1
    nums1.splice(0, p2 + 1, ...nums2.slice(0, p2 + 1))
};

结果：

59/59 cases passed (52 ms)
Your runtime beats 99.76 % of javascript submissions
Your memory usage beats 78.3 % of javascript submissions (33.6 MB)
时间复杂度 O(m + n)

Ⅲ.合并后排序再赋值

代码：

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    arr = [].concat(nums1.splice(0, m), nums2.splice(0, n))
    arr.sort((a, b) => a - b)
    for(let i = 0; i < arr.length; i++) {
        nums1[i] = arr[i]
    }
};

结果：

59/59 cases passed (64 ms)
Your runtime beats 90.11 % of javascript submissions
Your memory usage beats 31.21 % of javascript submissions (34.8 MB)
时间复杂度 O(m + n)

查阅他人解法

这里看到一个直接用两次 while ，然后直接用 m/n 来计算下标的，没有额外空间，但是本质上也是从后往前遍历。

Ⅰ.两次while

代码：

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // 避免 nums1 = [0,0,0,0], nums2 = [1,2] 这种 nums1.length > nums2.length 并且 m = 0
    // nums1.splice(m, nums1.length - m)
    // 从后开始赋值
    while(m !== 0 && n !== 0) {
        nums1[m + n - 1] = nums1[m - 1] > nums2[n - 1] ? nums1[--m] : nums2[--n]
    }
    // nums2 有剩余
    while(n !== 0) {
        nums1[m + n - 1] = nums2[--n]
    }
};

结果：

59/59 cases passed (56 ms)
Your runtime beats 99.16 % of javascript submissions
Your memory usage beats 64.26 % of javascript submissions (33.8 MB)
时间复杂度 O(m + n)

思考总结

碰到数组操作，会优先考虑双指针法，具体指针方向可以由题目逻辑来决定。

（完）

本文为原创文章，可能会更新知识点及修正错误，因此转载请保留原出处，方便溯源，避免陈旧错误知识的误导，同时有更好的阅读体验
如果能给您带去些许帮助，欢迎 ⭐️star 或 ✏️ fork
(转载请注明出处：https://chenjiahao.xyz)

加载全部内容

【Leetcode 做题学算法周刊】第四期

背景

目录

Easy

67.二进制求和

题目描述

题目分析设想

查阅他人解法

查阅他人解法

思考总结

69.x的平方根

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

70.爬楼梯

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

83.删除排序链表中的重复元素

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

88.合并两个有序数组

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结