此题出自力扣网题库第172题,我刚开始没有想到,后面看了题解才明白的。
先看看题目,讲得很简单
还有入参的限制,0 <= n <= 104
class Solution {
public int trailingZeroes(int n) {
// TODO ...
}
}
放一个计算器,一会自己可以看看规律
输入数字n: 计算 结果:1
暴力解析,算出答案,再转字符串,计算出末尾零的个数。
这种方法想都不要想,这可是阶乘,数字量很大的,很容易溢出。不然上面用计算器来试试。
不知道你用计算器试过了没有,也不知道你有没有得到规律,我们先一步一步来分析
n
中有多少个10或者10的倍数,就有多少个零
然而,当你用计算器去试了一下,结果发现,5! = 120,这也有一个零
n
中有多少个5的倍数这样的数,就可以正确得到答案了
public int trailingZeroes(int n) {
int count = n / 5;
return count;
}
思维发散至这里,已经很强了,但还不够!!!因为25! = 15511210043330985984000000,足足有6个0,这是为什么???
class Solution {
public int trailingZeroes(int n) {
int count = 0;
while(n >= 5) {
count += n / 5;
n /= 5;
}
return count;
}
}
这道题,我拿到确实懵逼了,直到看完题解才恍然大悟,只能大声高呼,牛逼。
我是半月,祝你幸福!!!