/**
* @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)
/**
* @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)
背景
本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
目录
Easy
171.Excel表列序号
题目地址
题目描述
给定一个Excel表格中的列名称,返回其相应的列序号。
例如,
示例:
题目分析设想
这道题其实就是上面168题的逆推导,也是就26进制转10进制。所以解法也很直接,做转换即可。无非区别在于正序和倒序处理罢了。
编写代码验证
Ⅰ.正序转换
代码:
结果:
O(n)
Ⅱ.倒序转换
代码:
结果:
O(n)
查阅他人解法
看了一下解法,大部分都是常规的倒序解法。正序的话其实就是秦九韶算法。
思考总结
这道题没有什么难度,就是一个进制转换的过程,比较容易想到的也就是倒序遍历,转换求解。
172.阶乘后的零
题目地址
题目描述
给定一个整数
n
,返回n!
结果尾数中零的数量。示例:
说明: 你算法的时间复杂度应为 O(log n) 。
题目分析设想
这道题明显不适合算出来阶乘的值再来算有多少个零,因为很容易溢出,且复杂度高。所以这里需要找到规律,这里规律还很明显,零的产生一定是由
2x5(4看作2x2)
,所以本质上还是看5
的数量,当然5^n
还需要再累加。编写代码验证
Ⅰ.累加5的每个幂的个数
代码:
结果:
O(log(n))
其实除5也可以等同于
xxx/5 + xxx/25 + xxx/125 + xxx/5^n
,当5^n超过阶乘数的时候,必然取0。代码:
结果:
O(log(n))
查阅他人解法
没有看见更优的算法,但是看到一个偏硬核的,其实也就是上面的解法的提前枚举。因为我们之前数值运算有MAX边界,所以5^n是可枚举。
Ⅰ.枚举
代码:
结果:
O(log(n))
思考总结
枚举的方式纯属一乐,这道题的本质还是找到5的关键点,将问题进行转换求解即可。
190.颠倒二进制位
题目地址
题目描述
颠倒给定的 32 位无符号整数的二进制位。
示例:
提示:
进阶: 如果多次调用这个函数,你将如何优化你的算法?
题目分析设想
看到这道题,明显关键点就在各种位运算符的使用。但是也可以取巧通过字符串处理,所以下面就尝试从这两个方向去作答。
编写代码验证
Ⅰ.位运算
代码:
结果:
O(1)
Ⅱ.字符串处理
代码:
结果:
O(1)
查阅他人解法
这里还看见另外一种位运算符的使用
Ⅰ.位移+换位
代码:
结果:
O(1)
思考总结
这题的考点也就在位运算了,熟悉熟悉很容易就能处理。不过熟悉位运算符对于一些运算来讲还是非常有意义的。
191.位1的个数
题目地址
题目描述
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为
1
的个数(也被称为汉明重量)。示例:
提示:
进阶: 如果多次调用这个函数,你将如何优化你的算法?
题目分析设想
做了上道题之后,这道题,还可以使用位运算符来处理。同样,通过字符串获取也可以实现,但这显然不是这题的考点。
编写代码验证
Ⅰ.位运算
代码:
结果:
O(1)
Ⅱ.字符串处理
代码:
结果:
O(1)
查阅他人解法
实现方法就太多了,大同小异,既然考位运算,那就再换成左移作答吧。其他的思路也都大同小异,无非就是加减、几位运算的区别。
Ⅰ.位运算-1左移
代码:
结果:
O(1)
思考总结
说白了如果做了上道题之后,这题就没有什么价值了,只是写法问题,解法可太多了。
198.打家劫舍
题目地址
题目描述
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例:
提示:
题目分析设想
这道题可以转化一下,简化之后其实就是奇数项和偶数项的和的比较。最基础的思路就是分别求和,然后记录当前比较结果后再继续分别求和。如果每次利用上每次的结果的话,那就变成了一个动态规划求解的问题了,所以这道题我们循序渐进来作答。
编写代码验证
Ⅰ.分别求和
代码:
结果:
O(n)
Ⅱ.动态规划
代码:
结果:
O(n)
查阅他人解法
看了一下解法,基本都是动态规划求解。
思考总结
这道题如果看多了,基本能直接转化成一个动态规划的问题,有点类似于买卖股票。但是这题我更建议分别求和每次做比较的方式,这样的话其实空间复杂度是明显更低的。
(完)