LeetCode 172 階乘後的0

2022-09-22 06:41:43 字數 1417 閱讀 3800

問題描述:

給定一個整數 n,返回 n! 結果尾數中零的數量。

示例 1:

輸入:3輸出:0解釋:3! = 6, 尾數中沒有零。
示例 2:

輸入:5輸出:1解釋:5! = 120, 尾數中有 1 個零.
說明:你演算法的時間複雜度應為 o(log n)。

times out:時間複雜度o(nlogn),顯然不行

1

class

solution(object):

2def

trailingzeroes(self, n):

3"""

4:type n: int

5:rtype: int

6"""

7if n == 1 or n ==0:

8return

09 nums =[1,1]

10 i = 2

11while i <=n:

13 strs =str(nums[i])

14return strs.count(0)

改進:題目是求尾數中0的個數,100return 2,100 == 10* 10十的因子有兩個。5!= 5 * 4 * 3 * 2 * 1 = 120 有一個因子10 return 1.有5必有2,求5的個數

class

solution(object):

deftrailingzeroes(self, n):

""":type n: int

:rtype: int

"""k =0

res =0

i =0

while

n: k = n // 5res +=k

n =k

return res

可以去掉變數k

1

class

solution(object):

2def

trailingzeroes(self, n):

3"""

4:type n: int

5:rtype: int

6"""

7 res =0

8while n >0:

9 n = n/5

10 res +=n

11return res

2018-09-15 10:47:12