Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
s思路: 1. n!中零的個數是因為有2,5這兩個因子。我們就去找有多少個5,多少個2,然后這兩個數的最小者決定了0的個數。嚴格的說,必須都計算,但是從得到結果的角度思考,由于5比2少,所以只需要知道有多少個5即可。 2. 比如:50!50/5就可以得到5的倍數的個數。第一次做的時候,就以為這就完了。其實沒完,因為這兩者不能直接劃等號,比如:5的倍數是5,10,15,20,25,30,35,40,45,50.注意到,25和50各含有兩個5.也就是說,5的倍數的個數不完全等于5的個數。換句話說,5的倍數的個數不嚴格等于5的個數,但是非常接近。現在的問題,就是如何修正?自己之前想到這里,就不知所措,除了stick這個方法就是quit這個方法,忘了還有一條路,就是繼續使用這個方法往后走,比如:50/5=10,把10/5=2,2/5=0,就是一個iterative的過程。也就是說,這個結果不是一蹴而就就能得到,必須允許分步走。這道題的思路自然就出來! 3. 分步iterative走,經常是把一個方法多次運用,逐漸逼近事物真相!
class Solution {public: int trailingZeroes(int n) { // int res=0; while(n){ n/=5; res+=n; } return res; }};新聞熱點
疑難解答