文章目錄

• 思路
• • 方法1
  • 方法2
• 代碼
• • 方法1
  • 方法2

思路

方法1

末尾每一個(gè)0都能看做是一個(gè)10
0的數(shù)量就轉(zhuǎn)換成n!=123*…n形成的10的數(shù)量
每一個(gè)10可以看作是25
10的數(shù)量就轉(zhuǎn)換成形成25的數(shù)量
5的數(shù)量：
第零個(gè)5=05
第一個(gè)5=15
第二個(gè)5=25
第三個(gè)5=35
第四個(gè)5=45
第五個(gè)5=55
第六個(gè)5=55
……

2的數(shù)量：
等價(jià)于偶數(shù)數(shù)量
第0個(gè)5～第1個(gè)5之間存在偶數(shù)，于是存在2
第1個(gè)5～第2個(gè)5之間存在偶數(shù)，于是存在2
……

由此可得是要有一個(gè)5，那么就會(huì)存在至少一個(gè)2與之相匹配
于是有2*5的數(shù)量就轉(zhuǎn)換成計(jì)算5的數(shù)量

方法2

序列0：1,2,3,4,5,6,7,8…<=n
序列1：5,10,15,20,25,30…5*m<=n
m=n/5

序列2：1,2,3,4,5,6,7,8…
序列3：5,10,15,20,25,30…5*m1<=m
m1=m/5

序列4：1,2,3,4,5,6,7,8…
序列5：5,10,15,20,25,30…5*m2<=m1
m2=m1/5
……
mi=m(i-1)/5
mi<5,停止迭代

m為1～n中能被5整除的數(shù)
m1為1～n中能被25整除的數(shù)
m2為1～n中能被125整除的數(shù)
……
于是5的數(shù)量=m+m1+…+m(i-1)

代碼

方法1

int trailingZeroes(int n){int ret=0, temp;for(int i=0;i<=n;i+=5){temp=i;while(temp%5==0 && temp/5>0){ret++;temp=temp/5;}}return ret; }

方法2

int trailingZeroes(int n){int ret=0;while(n>0){ret+=n/5;n/=5;}return ret; }

總結(jié)

以上是生活随笔為你收集整理的Leetcode题库 172.阶乘后的零(C实现)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。