McChen

McChen

关注
发信
关注(28)粉丝(399)

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

背景

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

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

目录

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]
};

结果：

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

Ⅲ.排列组合

代码：

/**
 * @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)

思考总结

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

（完）

11-22 02:32
Powered by LMLPHP ©2024 McChen 0.055179