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

6次阅读

共计 7325 个字符，预计需要花费 19 分钟才能阅读完成。

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

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

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

171.Excel 表列序号
172. 阶乘后的零
190. 颠倒二进制位
191. 位 1 的个数
198. 打家劫舍

题目地址

给定一个 Excel 表格中的列名称，返回其相应的列序号。

例如，

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

示例:

输出: "A"
输入: 1

输出: "AB"
输入: 28

输出: "ZY"
输入: 701

这道题其实就是下面 168 题的逆推导，也是就 26 进制转 10 进制。所以解法也很间接，做转换即可。无非区别在于正序和倒序解决罢了。

Ⅰ. 正序转换

代码：

/**
 * @param {string} s
 * @return {number}
 */
var titleToNumber = function(s) {
    let res = 0
    for(let i = 0; i < s.length; i++) {res = res * 26 + (s.charCodeAt(i) - 'A'.charCodeAt() + 1)
    }
    return res
};

后果：

1000/1000 cases passed (84 ms)
Your runtime beats 69.77 % of javascript submissions
Your memory usage beats 33.33 % of javascript submissions (36.1 MB)
工夫复杂度：O(n)

Ⅱ. 倒序转换

代码：

/**
 * @param {string} s
 * @return {number}
 */
var titleToNumber = function(s) {
    let res = 0
    let mul = 1
    for(let i = s.length - 1; i >= 0; i--) {res += (s.charCodeAt(i) - 'A'.charCodeAt() + 1) * mul
        mul *= 26
    }
    return res
};

后果：

1000/1000 cases passed (100 ms)
Your runtime beats 20.5 % of javascript submissions
Your memory usage beats 100 % of javascript submissions (34.7 MB)
工夫复杂度：O(n)

看了一下解法，大部分都是惯例的倒序解法。正序的话其实就是秦九韶算法。

这道题没有什么难度，就是一个进制转换的过程，比拟容易想到的也就是倒序遍历，转换求解。

题目地址

给定一个整数 n，返回 n! 后果尾数中零的数量。

示例:

输出: 3
输入: 0
解释: 3! = 6, 尾数中没有零。输出: 5
输入: 1
解释: 5! = 120, 尾数中有 1 个零.

阐明: 你算法的工夫复杂度应为 O(log n)。

这道题显著不适宜算进去阶乘的值再来算有多少个零，因为很容易溢出，且复杂度高。所以这里须要找到法则，这里法则还很显著，零的产生肯定是由 2x5(4 看作 2x2)，所以实质上还是看 5 的数量，当然 5^n 还须要再累加。

Ⅰ. 累加 5 的每个幂的个数

代码：

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
    let res = 0
    while (n) {
        n = n / 5 | 0
        res += n
    }
    return res
};

后果：

502/502 cases passed (76 ms)
Your runtime beats 55.62 % of javascript submissions
Your memory usage beats 100 % of javascript submissions (34.5 MB)
工夫复杂度：O(log(n))

其实除 5 也能够等同于 xxx/5 + xxx/25 + xxx/125 + xxx/5^n，当 5^n 超过阶乘数的时候，必然取 0。

代码：

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {
    let res = 0
    let num = 5
    while (n >= num) {
        res += n / num | 0
        num *= 5
    }
    return res
};

后果：

502/502 cases passed (76 ms)
Your runtime beats 55.62 % of javascript submissions
Your memory usage beats 100 % of javascript submissions (34.3 MB)
工夫复杂度：O(log(n))

没有看见更优的算法，然而看到一个偏硬核的，其实也就是下面的解法的提前枚举。因为咱们之前数值运算有 MAX 边界，所以 5^n 是可枚举。

Ⅰ. 枚举

代码：

/**
 * @param {number} n
 * @return {number}
 */
var trailingZeroes = function(n) {return (n/5 | 0)+(n/25 | 0)+(n/125 | 0)+(n/625 | 0)+(n/3125 | 0)+(n/15625 | 0)+(n/78125 | 0)+(n/390625 | 0)
    +(n/1953125 | 0)+(n/9765625 | 0)+(n/48828125 | 0)+(n/244140625 | 0)+(n/1220703125 | 0);
};

后果：

502/502 cases passed (80 ms)
Your runtime beats 37.95 % of javascript submissions
Your memory usage beats 100 % of javascript submissions (34.4 MB)
工夫复杂度：O(log(n))

枚举的形式纯属一乐，这道题的实质还是找到 5 的关键点，将问题进行转换求解即可。

题目地址

颠倒给定的 32 位无符号整数的二进制位。

示例:

输出: 00000010100101000001111010011100
输入: 00111001011110000010100101000000
解释: 输出的二进制串 00000010100101000001111010011100 示意无符号整数 43261596，因而返回 964176192，其二进制示意模式为 00111001011110000010100101000000。输出：11111111111111111111111111111101
输入：10111111111111111111111111111111
解释：输出的二进制串 11111111111111111111111111111101 示意无符号整数 4294967293，因而返回 3221225471 其二进制示意模式为 10111111111111111111111111111111。

提醒：

请留神，在某些语言（如 Java）中，没有无符号整数类型。在这种状况下，输出和输入都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其外部的二进制示意模式都是雷同的。
在 Java 中，编译器应用二进制补码记法来示意有符号整数。因而，在下面的示例 2 中，输出示意有符号整数 -3，输入示意有符号整数 -1073741825。

进阶:
如果屡次调用这个函数，你将如何优化你的算法？

看到这道题，显著关键点就在各种位运算符的应用。然而也能够取巧通过字符串解决，所以上面就尝试从这两个方向去作答。

Ⅰ. 位运算

代码：

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
    let t = 32, r = 0;
    while(t--) {r = (r << 1) + (n & 1); // 输入后果左移并加上最初一位
        n >>= 1 // 待处理数字右移
    }
    return r >>> 0;
};

后果：

600/600 cases passed (100 ms)
Your runtime beats 49.62 % of javascript submissions
Your memory usage beats 70.65 % of javascript submissions (39.4 MB)
工夫复杂度：O(1)

Ⅱ. 字符串解决

代码：

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
    return parseInt(n.toString(2).split('').reverse().join('').padEnd(32, 0),
        2
    )
};

后果：

600/600 cases passed (104 ms)
Your runtime beats 33.27 % of javascript submissions
Your memory usage beats 88.8 % of javascript submissions (39.1 MB)
工夫复杂度：O(1)

这里还看见另外一种位运算符的应用

Ⅰ. 位移 + 换位

代码：

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
    let t = 32, r = 0;
    while(t--) {r = (r << 1) | (n & 1); // 输入后果左移并末位替换
        n >>= 1 // 待处理数字右移
    }
    return r >>> 0;
};

后果：

600/600 cases passed (96 ms)
Your runtime beats 61.41 % of javascript submissions
Your memory usage beats 91.5 % of javascript submissions (39 MB)
工夫复杂度：O(1)

这题的考点也就在位运算了，相熟相熟很容易就能解决。不过相熟位运算符对于一些运算来讲还是十分有意义的。

题目地址

编写一个函数，输出是一个无符号整数（以二进制串的模式），返回其二进制表达式中数字位数为 1 的个数（也被称为汉明分量）。

示例:

输出：00000000000000000000000000001011
输入：3
解释：输出的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。输出：00000000000000000000000010000000
输入：1
解释：输出的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。输出：11111111111111111111111111111101
输入：31
解释：输出的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提醒：

请留神，在某些语言（如 Java）中，没有无符号整数类型。在这种状况下，输出和输入都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其外部的二进制示意模式都是雷同的。
在 Java 中，编译器应用二进制补码记法来示意有符号整数。因而，在下面的示例 2 中，输出示意有符号整数 -3，输入示意有符号整数 -1073741825。

进阶:
如果屡次调用这个函数，你将如何优化你的算法？

做了上道题之后，这道题，还能够应用位运算符来解决。同样，通过字符串获取也能够实现，但这显然不是这题的考点。

Ⅰ. 位运算

代码：

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let t = 32, r = 0;
    while(t--) {if (n & 1 === 1) r++; // 判断最初一位
        n >>= 1 // 待处理数字右移
    }
    return r;
};

后果：

601/601 cases passed (88 ms)
Your runtime beats 84.03 % of javascript submissions
Your memory usage beats 91.49 % of javascript submissions (38.8 MB)
工夫复杂度：O(1)

Ⅱ. 字符串解决

代码：

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {return n.toString(2).replaceAll('0', '').length
};

后果：

601/601 cases passed (92 ms)
Your runtime beats 68.73 % of javascript submissions
Your memory usage beats 88.54 % of javascript submissions (38.9 MB)
工夫复杂度：O(1)

实现办法就太多了，大同小异，既然考位运算，那就再换成左移作答吧。其余的思路也都大同小异，无非就是加减、几位运算的区别。

Ⅰ. 位运算 - 1 左移

代码：

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
    let t = 32, r = 0;
    while(t--) {if ((n & (1 << (32 - t))) != 0) {r++;}
    }
    return r;
};

后果：

601/601 cases passed (104 ms)
Your runtime beats 21.48 % of javascript submissions
Your memory usage beats 82.75 % of javascript submissions (39 MB)
工夫复杂度：O(1)

说白了如果做了上道题之后，这题就没有什么价值了，只是写法问题，解法可太多了。

题目地址

你是一个业余的小偷，打算偷窃沿街的屋宇。每间房内都藏有肯定的现金，影响你偷窃的惟一制约因素就是相邻的屋宇装有互相连通的防盗零碎，如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警。

给定一个代表每个屋宇寄存金额的非负整数数组，计算你不触动警报安装的状况下，一夜之内可能偷窃到的最高金额。

示例:

输出：[1,2,3,1]
输入：4
解释：偷窃 1 号屋宇 (金额 = 1)，而后偷窃 3 号屋宇 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4。输出：[2,7,9,3,1]
输入：12
解释：偷窃 1 号屋宇 (金额 = 2), 偷窃 3 号屋宇 (金额 = 9)，接着偷窃 5 号屋宇 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12。

提醒：

0 <= nums.length <= 100
0 <= nums[i] <= 400

这道题能够转化一下，简化之后其实就是奇数项和偶数项的和的比拟。最根底的思路就是别离求和，而后记录以后比拟后果后再持续别离求和。如果每次利用上每次的后果的话，那就变成了一个动静布局求解的问题了，所以这道题咱们循序渐进来作答。

Ⅰ. 别离求和

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    let evenTotal = 0, oddTotal = 0;
    for(let i = 0; i < nums.length; i++) {if (i & 1) {evenTotal += nums[i]
            evenTotal = Math.max(evenTotal, oddTotal) // 取两种形式的更大值
        } else {oddTotal += nums[i]
            oddTotal = Math.max(evenTotal, oddTotal) // 取两种形式的更大值
        }
    }
    return Math.max(evenTotal, oddTotal)
};

后果：

69/69 cases passed (84 ms)
Your runtime beats 53.82 % of javascript submissions
Your memory usage beats 61.74 % of javascript submissions (37.6 MB)
工夫复杂度：O(n)

Ⅱ. 动静布局

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length;
    if (len === 0) return 0
    if (len === 1) return nums[0]
    if (len === 2) return Math.max(nums[0], nums[1])
    // dp[i] 示意偷 i + 1 间的最大收益
    let dp = [nums[0], Math.max(nums[0], nums[1])]
    for(let i = 2; i < len; i++) {dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
    }
    return dp[nums.length - 1]
};

后果：

69/69 cases passed (72 ms)
Your runtime beats 95.68 % of javascript submissions
Your memory usage beats 26.94 % of javascript submissions (37.9 MB)
工夫复杂度：O(n)

看了一下解法，根本都是动静布局求解。

这道题如果看多了，根本能间接转化成一个动静布局的问题，有点相似于交易股票。然而这题我更倡议别离求和每次做比拟的形式，这样的话其实空间复杂度是显著更低的。

（完）

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

正文完

javascript

发表至： javascript

2021-01-11

0

关于javascript:day13-正则表达式

前端培训中级阶段5-jQuery的概念与基本使用20190711期

The impacts of using index as key in React

关于javascript:Vue3-组件-ref-注意事项

关于人工智能:个人信息严控的时代AI如何实现安全的智能营销

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

背景

目录

Easy

171.Excel 表列序号

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结

172. 阶乘后的零

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结

190. 颠倒二进制位

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结

191. 位 1 的个数

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结

198. 打家劫舍

题目形容

题目剖析构想

编写代码验证

查阅别人解法

思考总结

站内搜索