内容简介:LeetCode - 172 - 阶乘后的零(factorial-trailing-zeroes)
Create by jsliang on 2019-7-8 08:07:23
Recently revised in 2019-7-8 09:14:41
一 目录
不折腾的前端,和咸鱼有什么区别
| 目录 | | --- | | 一 目录 | | 二 前言 | | 三 解题 | | 四 执行测试 | | 五 LeetCode Submit | | 六 解题思路 |
二 前言
难度:简单
涉及知识:数学
题目地址:https://leetcode-cn.com/problems/factorial-trailing-zeroes/
题目内容:
给定一个整数 n,返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
三 解题
小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。
解题代码:
var trailingZeroes = function(n) {
let total = 0;
while (n >= 5) {
n = Math.floor(n / 5);
total += n;
}
return total;
};
四 执行测试
n
:30
return
:7
五 LeetCode Submit
√ Accepted
√ 502/502 cases passed (80 ms)
√ Your runtime beats 92.95 % of javascript submissions
√ Your memory usage beats 68.18 % of javascript submissions (33.9 MB)
六 解题思路
首先,需要明确的是,这道题不能使用递归,因为超时了。
然后,这道题还需要考虑超限:
var trailingZeroes = function(n) {
let result = 1;
while(n > 0) {
result = result * n;
n--;
}
result = result.toString().split('').reverse();
for (let i = 0; i < result.length; i++) {
if (result[i] !== '0') {
return i;
}
}
return 0;
};
在这份代码中,当你的数字为 30 的时候,你就超限了:
× Wrong Answer
× 21/502 cases passed (N/A)
× testcase: '30'
× answer: 0
× expected_answer: 7
个人觉得这是正常思路,但是看到它这里显示 21/502
,那么我就知道,它又想考我的智商了。
智商税得交,谁让你数学没那么好呢!
接着,咱访问下【评论】和【题解】,看看别人怎么破解,其中思路非常 nice 的是:
https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/jie-cheng-hou-de-ling-die-dai-ji-di-gui-jie-fa-by-/
它的题解有两种:
题解 1 - 迭代
var trailingZeroes = function(n) {
let total = 0;
while (n >= 5) {
n = Math.floor(n / 5);
total += n;
}
return total;
};
题解 2 - 递归
var trailingZeroes = function(n) {
const helper = (n, total) => {
if (n < 5) {
return total;
}
const count = Math.floor(n / 5);
return helper(count, total + count);
};
return helper(n, 0);
};
那么,jsliang 看完题解,以自己意思表述一下:
1. 末尾有 0 是因为其中有 10 的因数,即 2*5
、 1*10
这种情况。
2. 找规律:当 n
为 5 时,有 1 个 0,当 n
为 10 时,有 2 个 0……但是,碰到某个特定的数时,会有意外,详情看表格:
n | 个数 |
---|---|
5 | 1 |
10 | 2 |
15 | 3 |
20 | 4 |
25 | 6 |
30 | 7 |
35 | 8 |
40 | 9 |
45 | 10 |
50 | 12 |
即当 n
为 25 倍数的时候,还需要将个数调整一次:
var trailingZeroes = function(n) {
let total = 0;
while (n >= 5) {
n = Math.floor(n / 5);
total += n;
}
return total;
};
再结合题意,小伙伴们应该就比较清晰了。
最后,我们就得出了这道题的题解。
不折腾的前端,和咸鱼有什么区别!
jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。
扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。
以上所述就是小编给大家介绍的《LeetCode - 172 - 阶乘后的零(factorial-trailing-zeroes)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
程序员代码面试指南:IT名企算法与数据结构题目最优解(第2版)
左程云 / 电子工业出版社 / 109.00元
《程序员代码面试指南:IT名企算法与数据结构题目最优解(第2版)》是一本程序员代码面试"神书”!书中对IT名企代码面试各类题目的最优解进行了总结,并提供了相关代码实现。针对当前程序员面试缺乏权威题目汇总这一痛点,本书选取将近300道真实出现过的经典代码面试题,帮助广大程序员的面试准备做到接近万无一失。"刷”完本书后,你就是"题王”!《程序员代码面试指南:IT名企算法与数据结构题目最优解(第2版)》......一起来看看 《程序员代码面试指南:IT名企算法与数据结构题目最优解(第2版)》 这本书的介绍吧!