算法学习之旅

清疚 2022-08-03 05:21 274阅读 0赞

问题：设计一个算法，计算出n阶乘中尾部零的个数  
例如: 11! = 39916800，因此应该返回 2  
挑战：O(logN)的时间复杂度

想法1：  
找出1–n中每个数字能够被5或者10整除的次数，加在一起就是答案。但是时间复杂度是O(N2).代码如下：\`public static long trailingZeros(long n) \{  
// write your code here  
long five=0;  
long count=0;  
for(long i=1;i<=n;i++)\{  
if(i%10==0)\{  
long j=i;  
while(j>1 && j%10==0)\{  
j/=10;  
count++;  
\}  
if(j%5==0)\{  
while(j>1 && j%5==0)\{  
j/=5;  
count++;  
\}  
\}  
\}else if(i%5==0)\{  
long k=i;  
while(k>1 && k%5==0)\{  
k/=5;  
count++;  
\}  
\}

}
         return count;
    }

想法2.统计1—n 能被5整除的次数，累加求和，代码类似上边

想法3：对想法2进行优化，只对1—n之中能够被5整除的数进行统计。代码如下：  
public static long trailingZeros(long n) \{  
// write your code here  
long five=0;  
long count=0;  
if(n<5)\{  
return 0;  
\}else if(n==5)\{  
return 1;  
\}  
for(long i=5;i<=n;i+=5)\{  
if(i%5==0)\{  
long j=i;  
while(j>0 && j%5==0)\{  
j/=5;  
count++;  
\}  
\}  
\}  
return count;  
\}  
《编程之美》上的想法3：  
公式：Z = \[N/5\] +\[N/52\] +\[N/53\] + …（不用担心这会是一个无穷的运算，因为总存在一个K，使得5K > N，\[N/5K\]=0。）  
5的倍数贡献一个5，5的平方贡献两个5~~~.  
代码如下：  
int num = 0, i;  
for(i=5; i<=n; i\*=5)  
\{  
num += n/i;  
\}  
return num;  
又简洁，执行效率又高，与君共勉之。

发表评论取消回复

表情：

评论列表（有 0 条评论，274人围观）

还没有评论，来说两句吧...

相关阅读

相关【项目】Spring学习之旅（正在学习）

Spring框架是目前最流行和最广泛使用的Java框架之一，它有着强大的社区支持和丰富的文档资源。Spring框架可以与其他主流的技术和框架集成，如MyBatis、Hib...

淩亂°似流年/ 2024年05月01日 03:57/ 0 赞/ 97 阅读

相关学习编程之旅

一位孤独的学生，踏进了编程的世界里。他经历了许多不愉快的事情，因为自己的无知和初学者的迷茫而孤独。直到这位学生遇到了他的老师和一个充满温暖的开发团队，他才真正体验到编程的美妙之

深藏阁楼爱情的钟/ 2024年03月22日 05:52/ 0 赞/ 113 阅读

相关【算法之旅】基础算法之递归

![请添加图片描述][ea689b325bd64e3d99e44e943c5dbdb3.png] 一名软件工程专业学生的算法之旅，记录自己从零开始学习数据结构与算法，从小白

以你之姓@/ 2023年09月25日 20:20/ 0 赞/ 151 阅读

相关 Spark学习烦躁之旅

1.什么是Spark spark是一个集群运算框架，因为使用了基于内存的运算和DAG优化使得其运算速度大大的加快。spark相当于是hadoop中map reduce的一

约定不等于承诺〃/ 2022年11月21日 11:20/ 0 赞/ 212 阅读

相关 Java学习之旅（二四）：数组排序算法

冒泡排序在程序设计中，经常需要将一组数列进行排序，这样更加方便统计与查询。程序常用的排序方法有冒泡排序、选择排序和快速排序等。冒泡排序是最常用的数组排序算法之一，它排序数组

亦凉/ 2022年11月20日 04:50/ 0 赞/ 200 阅读

相关 Spring Boot 学习之旅

1. Spring Boot默认读取的application.properties有点坑，并没有主动去掉每一行后边的空格，如 encoding.spring.thyme

蔚落/ 2022年09月24日 07:27/ 0 赞/ 227 阅读

相关 JPA学习之旅（一）

最近项目中使用到了JPA，所以趁机学习一下JPA相关的知识。我是跟着《尚硅谷的视频》学习的！看了视频中，老师讲的第一节知识：老师有这么一句

客官°小女子只卖身不卖艺/ 2022年09月23日 08:54/ 0 赞/ 211 阅读

相关算法学习之旅

问题：设计一个算法，计算出n阶乘中尾部零的个数例如: 11! = 39916800，因此应该返回 2 挑战：O(logN)的时间复杂度想法1：找出1–n中每

清疚/ 2022年08月03日 05:21/ 0 赞/ 275 阅读

相关爬蜥学习之旅

编程语言 [java之旅总览][java] 算法 [算法][Link 1] 网络 [网络][Link 2] 机器学习与数据挖掘 [机器学习与数据挖

超、凢脫俗/ 2022年03月16日 14:23/ 0 赞/ 232 阅读

相关 Javascript学习之旅系列

基础知识篇　　[Javascript基础知识篇(1): 初识Javascript][Javascript_1_ _Javascript] 　　[Javascript基

秒速五厘米/ 2021年12月21日 04:33/ 0 赞/ 286 阅读