【一天一道LeetCode】#172. Factorial Trailing Zeroes
2024-10-12 19:08:46
一天一道LeetCode
本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处
(一)题目
Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
(二)解题
题目大意:求n的阶乘算出来的数尾部有多少个0。如5!=120,尾部有1个0,返回1。
解题思路:仔细观察阶乘公式1*2*3….*n,只有2*5=10,这样才能有0,所以一开始想到的解法是算每个数的因子里面还有2和5的个数,这两个数组成一对就代表阶乘尾部有一个0,所以求这两个因子个数的最小值即可。
下面是TLE的版本,超时了。
class Solution {
public:
int trailingZeroes(int n) {
int count2 = 0;
int count5 = 0;
for(int i = 1 ;i <= n ;i++)
{
int temp = i;
while(temp%2==0){//求因子2的个数
count2++;
temp/=2;
}
while(temp%5==0){//求因子5的个数
count5++;
temp/=5;
}
}
return min(count2,count5);//返回较小值。
}
};
超时之后,想了很久,在纸上推算了一下,发现根本不用取这两者的最小值,5的个数一定比2小,这样一来只需要判断因子5的个数就行。
如果想上述解法那样粗暴的判断每一个数中含有因子5的个数肯定是不行了。
于是想到5的因子基本上每隔5个数产生一个,n/5就能找出因子5的个数,
但是诸如25,125这种含有多个因子5的数,一次n/5肯定不对。还需要n/25才行……
这样一直推算下去,最有因子5的总个数为n/5+n/25+n/125+……
根据这个思路可以写下如下代码:
class Solution {
public:
int trailingZeroes(int n) {
int sum = 0;
while(n){
sum+=n/5;
n/=5;
}
return sum;
}
};
最新文章
- 跟我学PHP第二篇- 配置Mysql以及PHP WampServer篇(1)
- 配置TFS2010的用户截图
- php 解析 视频 信息 封面 标题 图片 支持 优酷, 土豆 酷6 56 新浪 qq播客 乐视 乐视
- SQL Server复制入门(一)----复制简介【转】
- Oracle中对象权限与系统权限revoke
- Max Num---hdu2071
- 用TinyXml2读取XML文件的一个简单Demo
- Very Deep Convolutional Networks for Large-Scale Image Recognition
- github 之 下载历史版本
- 测试服务搭建之centos7下安装java
- vue-cli 前端开发,后台接口跨域代理调试问题
- C# 之 GUID格式化
- linux grep find查找文件夹、代码中的某行/字符串
- 《Spring_Four》第一次作业:团队亮相
- JavaScript大杂烩11 - 理解事件驱动
- 05LaTeX学习系列之---TeX的命令行操作
- Entity Framework 6.x 学习之Database First
- html05
- 2018.09.24 bzoj1486: [HNOI2009]最小圈(01分数规划+spfa判负环)
- .net winform 调用类中的webbrowser 报错:当前线程不在单线程单元中,因此无法实例化 ActiveX
热门文章
- hdu 5468(莫比乌斯+搜索)
- bzoj1499[NOI2005]瑰丽华尔兹 单调队列优化dp
- Linux内核异常处理体系结构详解(一)【转】
- Maven集成dubbo时报错 Missing artifact com.alibaba:dubbo:jar:2.8.4
- 地址下拉框,需要js级联js
- webpack dev server 和 sublime text 配合时需要注意的地方
- 炫酷:一句代码实现标题栏、导航栏滑动隐藏。ByeBurger库的使用和实现
- 数据库的case when 使用实例
- 如何扩展/删除swap分区
- norflash启动和nandflash启动