定制型网站制作公司,什么是网站前台静态化,目前做啥网站致富,前端开发兼职的未来发展java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 数学#xff1a;阶乘的10因子个数数学优化:思路转变为求5的倍数…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 文章目录 数学阶乘的10因子个数数学优化:思路转变为求5的倍数的个数 数学阶乘的10因子个数
解题思路时间复杂度O( n n n)n为5的个数空间复杂度O( 1 1 1) 如果想要求出阶乘一定会超时。所以我们要找到破题点。就是什么条件下阶乘末尾会出现0。我们发现阶乘结果求出来后不断的提出因子10能提出多少次就有几个0. 例如5120. 此时进行因式分解为 10 ∗ ( 12 ) . 10*(12). 10∗(12).一共提出1个10因此一共一个0.10是由2和5构成的。而且5的个数绝对更少。例如120 5 ∗ ( 24 ) 5*(24) 5∗(24) 2 ∗ 2 ∗ 2 ∗ ( 15 ) 2*2*2*(15) 2∗2∗2∗(15).我们发现5的个数决定了阶乘结果中可以和2组成几个10.因此我们可以先尝试统计n的阶乘中5的个数。试一下效果 我们不需要每个阶乘数字都统计例如5中只有5这个数会出现5.因为51*2*3*4*5.明眼人都知道1,2,3,4不会有5的出现。 代码最起码通过了对吗说明想法没错接下来法二会继续优化 class Solution {public int trailingZeroes(int n) {int ans 0;//统计5的个数for (int i 5; i n; i 5) {//只有5,10,15,20,25....会出现5其它数字不会出现5for (int x i; x % 5 0; x / 5) {//统计这些因子中的5的个数。例如100这个因子可以拆解为5*5*4.有两个5ans;//5的个数}}return ans;}
}数学优化:思路转变为求5的倍数的个数
解题思路时间复杂度O( l o g 2 n log_2n log2n)空间复杂度O( 1 1 1) 以1000为例1000 5 ∗ 200 5*200 5∗200 5 ∗ 5 ∗ 40 5*5*40 5∗5∗40 5 ∗ 5 ∗ 5 ∗ 8 5*5*5*8 5∗5∗5∗8 5 ∗ 5 ∗ 5 ∗ 5 ∗ 8 5 5*5*5*5*\dfrac{8}{5} 5∗5∗5∗5∗58.则1000的阶乘的5的个数为2004081 249个为什么对单个数字1000不断除5可以求出1000的阶乘中5的个数呢因为我们需要转变思路从现在开始我们要统计从1到1000中5的倍数出现的次数。 1到1000中5的倍数出现200次, 200个5的倍数分别是 5 , 10 , 15 , 20 , . . . . . , 1000 5,10,15,20,.....,1000 5,10,15,20,.....,1000 此时如果我们将这200个5的倍数全部提出一个5就会获得200个5. 并且因式分解后剩下的值看起来如下 1 ∗ 2 ∗ 3 ∗ 4 ∗ 5 ∗ . . . . ∗ 200 1*2*3*4*5*....*200 1∗2∗3∗4∗5∗....∗200,你会发现它们这些数正好组成了200的阶乘所有的数 此时我们只需要从1到200这些数中找当中5的倍数的个数。也就是 5 , 10 , 15 , 20 , . . . , 200 5,10,15,20,...,200 5,10,15,20,...,200 而200这个阶乘中5的倍数共出现40次我们将40次进行统计然后继续对这40个5的倍数提出一个5的因子。你会发现它们又变成了40的阶乘。 此时继续求40这个阶乘中5的倍数出现的次数。结果如下共8个5的倍数我们将8个5提出后剩下的数字组成了8的阶乘 继续对8求共1个5的倍数5提出1个5后剩下数字只有1了也就不用继续遍历了 最终就可以将所有我们提出的5统计起来2004081 249个。 代码 class Solution {public int trailingZeroes(int n) {int count 0;//统计个数while (n ! 0){//只要n的阶乘中还可以有5就继续n / 5;//获取n这个阶乘中所有5的倍数的个数count n;//统计个数}return count;}
}
