【刷算法】LeetCode- 阶乘后的零

layman 发布于2019-08-23 10:42 / 2363人阅读

摘要：原题地址中国题目描述给定一个整数，返回结果尾数中零的数量。示例输入输出解释尾数中有个零说明你算法的时间复杂度应为。分析首先暴力破解法就是直接把最终的结果求出来然后看末尾有几个，但是这样做的时间复杂度肯定是太大了。

原题地址：LeetCode中国-172

题目描述

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

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:

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

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

分析

首先暴力破解法就是直接把最终的结果求出来然后看末尾有几个0，但是这样做的时间复杂度肯定是太大了。

然后考虑到末尾的0是怎么形成的，首先10=2*5，20=2*2*5，30=3*2*5 ... 100=10*2*5

所以，问题的关键是看阶乘里面2和5的数量，但是因为显然2出现的数量大于5出现的数量，拿5的阶乘来举例子：

5！= (1) * (2) * (3) * (2*2) * (5)

出现了3个2、1个5，但是末尾只有1个0，所以阶乘末尾0的个数就是阶乘式中5的个数。但是如解法1的代码所示，时间复杂度还是太高。

继续考虑，对于50!，我们可以写成：

5 ... 2*5 ... 3*5 ... 4*5 ... 5*5 ... 6*5 ... 7*5 ... 8*5 ... 9*5 ... 10 * 5

可以看出来从5到10*5一共有10个5，但是对于10来说，从1到10还有2个5，所以50！的结果末尾有12个0

解法1（不符合要求的时间复杂度）

var trailingZeroes = function(n) {
  var count  = 0;
    
  for(var i = 1;i <= n;i++){
    var temp = i;
    while(temp%5 === 0){
      count++;
      temp /= 5;
    }
  }
  
  return count;
};

上面这个解法的时间复杂度是n*(logn)，不符合题意

解法2

var trailingZeroes = function(n) {
  var count  = 0;
    
  while(n) {
    count += divide(n,5);
    n = divide(n,5);
  }
  
  return count;
};
  
function divide(n, m) {
  return Math.floor(n/m);
}

云服务器 GPU云服务器阶乘c语言算法数组 LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96610.html

LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
＜LeetCode天梯＞Day026 反转链表（递归法+（迭代法）双链表法） | 初级算法 | Py

摘要：关于递归这里提一两点递归基本有这几步递归的模板，终止条件，递归调用，逻辑处理。 ?作者简介：大家好，我是车神哥，府学路18号的车神? ?个人主页：应无所住而生...

imingyu 2021-11-17 09:33 评论0 收藏0
小李飞刀：python你慢点飞，我的脑子还在后面追

摘要：默认参数设置默认参数时，有几点要注意一是必选参数在前，默认参数在后，否则的解释器会报错二是如何设置默认参数。注意此处，获得的其实是的拷贝，函数内对的改变不会影响到。使用递归函数需要注意防止栈溢出。总是在最前面的叨逼叨最近总是在想成长这两个很常常被提起的事情，这对于一个已经25岁的半中年而言，已经是一个不太能高频提起的词。但是，最近一些事情吧，总让我觉得我的生长期似乎比正常人来的晚了...

kevin 2019-07-30 18:40 评论0 收藏0