木又连续日更第41天(41/100)
木又的第190篇leetcode解题报告
数学
类型第6篇解题报告
leetcode第172题:阶乘后的零
https://leetcode-cn.com/problems/factorial-trailing-zeroes
【题目】
给定一个整数 n,返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
【思路】
只有5的倍数乘以偶数才会增加1个0,在n!中,5的个数肯定少于2的个数,所以求得5的个数就行。
如何求得5的个数呢,直接n/5?好像有问题,比如25!会少计算一个5。
原来,5的倍数1*5, 2*5, 3*5, 4*5, 5*5,每隔5次便会多一个5,依次类推,每隔5*5次,会再多一个5…
那么对于数n,不断对5求余,将其商累加即可。
【代码】
python版本
class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
# 5的个数
count = n
res = 0
while count > 0:
count /= 5
res += count
return res
C++版本
class Solution {
public:
int trailingZeroes(int n) {
int count = n, res = 0;
while(count > 0){
count /= 5;
res += count;
}
return res;
}
};