LeetCode - 172 - 阶乘后的零(factorial-trailing-zeroes)

栏目: IT技术 · 发布时间: 5年前

内容简介: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/

  • 题目内容

  1. 给定一个整数 n,返回 n! 结果尾数中零的数量。

  2. 示例 1:

  3. 输入: 3

  4. 输出: 0

  5. 解释: 3! = 6, 尾数中没有零。

  6. 示例 2:

  7. 输入: 5

  8. 输出: 1

  9. 解释: 5! = 120, 尾数中有 1 个零.

  10. 说明: 你算法的时间复杂度应为 O(log n) 

三 解题

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

  • 解题代码

  1. var trailingZeroes = function(n) {

  2. let total = 0;

  3. while (n >= 5) {

  4. n = Math.floor(n / 5);

  5. total += n;

  6. }

  7. return total;

  8. };

四 执行测试

  1. n: 30

  2. return: 7

五 LeetCode Submit

  1. Accepted

  2. 502/502 cases passed (80 ms)

  3. Your runtime beats 92.95 % of javascript submissions

  4. Your memory usage beats 68.18 % of javascript submissions (33.9 MB)

六 解题思路

首先,需要明确的是,这道题不能使用递归,因为超时了。

然后,这道题还需要考虑超限:

  1. var trailingZeroes = function(n) {

  2. let result = 1;

  3. while(n > 0) {

  4. result = result * n;

  5. n--;

  6. }

  7. result = result.toString().split('').reverse();

  8. for (let i = 0; i < result.length; i++) {

  9. if (result[i] !== '0') {

  10. return i;

  11. }

  12. }

  13. return 0;

  14. };

在这份代码中,当你的数字为 30 的时候,你就超限了:

  1. × Wrong Answer

  2. × 21/502 cases passed (N/A)

  3. × testcase: '30'

  4. × answer: 0

  5. × 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 - 迭代

  1. var trailingZeroes = function(n) {

  2. let total = 0;

  3. while (n >= 5) {

  4. n = Math.floor(n / 5);

  5. total += n;

  6. }

  7. return total;

  8. };

题解 2 - 递归

  1. var trailingZeroes = function(n) {

  2. const helper = (n, total) => {

  3. if (n < 5) {

  4. return total;

  5. }

  6. const count = Math.floor(n / 5);

  7. return helper(count, total + count);

  8. };

  9. return helper(n, 0);

  10. };

那么,jsliang 看完题解,以自己意思表述一下:

1. 末尾有 0 是因为其中有 10 的因数,即 2*51*10 这种情况。

2. 找规律:当 n 为 5 时,有 1 个 0,当 n 为 10 时,有 2 个 0……但是,碰到某个特定的数时,会有意外,详情看表格:

n个数
51
102
153
204
256
307
358
409
4510
5012

即当 n 为 25 倍数的时候,还需要将个数调整一次:

  1. var trailingZeroes = function(n) {

  2. let total = 0;

  3. while (n >= 5) {

  4. n = Math.floor(n / 5);

  5. total += n;

  6. }

  7. return total;

  8. };

再结合题意,小伙伴们应该就比较清晰了。

最后,我们就得出了这道题的题解。


不折腾的前端,和咸鱼有什么区别!

LeetCode - 172 - 阶乘后的零(factorial-trailing-zeroes)

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

LeetCode - 172 - 阶乘后的零(factorial-trailing-zeroes)

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。



以上所述就是小编给大家介绍的《LeetCode - 172 - 阶乘后的零(factorial-trailing-zeroes)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

REST实战

REST实战

Jim Webber、Savas Parastatidis、Ian Robinson / 李锟、俞黎敏、马钧、崔毅 / 东南大学出版社 / 2011-10 / 78.00元

为何典型的企业项目无法像你为web所开发的项目那样运行得如此平滑?对于建造分布式和企业级的应用来说,rest架构风格真的提供了一个可行的替代选择吗? 在这本富有洞察力的书中,三位soa专家对于rest进行了讲求实际的解释,并且通过将web的指导原理应用到普通的企业计算问题中,向你展示了如何开发简单的、优雅的分布式超媒体系统。你将会学习到很多技术,并且随着一家典型的公司从最初的小企业逐渐成长为......一起来看看 《REST实战》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具