每天 3 分钟，走上算法的逆袭之路。
前文合集
代码仓库
GitHub： github.com/meteor1993/…
Gitee： gitee.com/inwsy/LeetC…
题目：阶乘后的零
给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
解题方案一：暴力计算
看到这道题，常人的思维最少应该有先把 n! 算出来，再通过 /10 来计算末尾有多少个 0 。
// 暴力硬算
public int trailingZeroes(int n) {
// 先定义第一个数字
BigInteger bi = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
bi = bi.multiply(BigInteger.valueOf(i));
}
// 定义 0 出现的次数
int count = 0;
while (bi.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
bi = bi.divide(BigInteger.TEN);
count++;
}
return count;
}
我累个擦，直接超时了，然后看下测试用例，竟然执行到一个 4327 的数字，拿 4 位数出来算阶乘，就是计算机来算我都觉得累得慌，这个测试用例我服了，甘拜下风。
么得办法了，看答案吧，我这个智商也就只能想到这种方案了。
解题方案二：计算因子 5
先想一下，啥情况下能产生 0 ，最小的产生因子是 2 * 5 。
借用一个答案上的示例，42 * 75 = 3150 ，这个算式可以拆解如下：
42 = 2 * 3 * 7
75 = 3 * 5 * 5
42 * 75 = 2 * 3 * 7 * 3 * 5 * 5
这里面只出现了一对 2 和 5 ，所以结果只有一个 0 。
接着看另一个案例，比如求 19! ，这里面包含 5 的因子有 5 、10 、15 ，包含 2 的因子有2、4、6、8、10、12、14、16、18 。
可以看到的规律是每 5 个数字就会有一个包含 5 的因子，而在这 5 个数中间，肯定至少有一个包含 2 的因子，实际上是有 2 个，所以就不需要考虑 2 这个因子了，单纯的考虑 5 就好了，那么算法就演变成了我们需要寻找包含 5 的因子，代码如下：
// 计算因子 5
public int trailingZeroes_1(int n) {
int count = 0;
for (int i = 5; i <= n; i += 5) {
int current = i;
while (current % 5 == 0) {
count++;
current /= 5;
}
}
return count;
}
结果又超时了，我心态崩了啊，答案给的都是超时，看这个输入的数字， TM 18 亿，还敢输入数字再大点嘛。
接着刚才的答案往下看。
答案上还给出了另一种方案，不需要每次检查是否可以被 5 整除，还可以直接检查是否可以被 5 的次幂整除：
public int trailingZeroes_2(int n) {
int count = 0;
for (int i = 5; i <= n; i += 5) {
int powerOf5 = 5;
while (i % powerOf5 == 0) {
count += 1;
powerOf5 *= 5;
}
}
return count;
}
这个方案实际上和上面的方案是一样的，没什么本质的区别。
解题方案三：高效的计算因子 5
接着往下看，更加高效的计算方案。
看下面这个阶乘方案：
n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) *... * n
我们的目标是计算出现了多少个 5 ，从上面这个公式看下来，每隔 5 个数就会出现一次，那么我们使用 n / 5 就可以计算出来。
但是还没有结束，接着看下面的公式变化：
... * (1 * 5) * ... * (1 * 5 * 5) * ... * (2 * 5 * 5) * ... * (3 * 5 * 5) * ... * n
从这个公式可以看出来，每隔 5 个数，出现一个 5 ，每隔 25 个数，出现 2 个 5 ，每隔 125 个数，出现 3 个 5 ，以此类推。。。
最终出现 5 的个数就是 n / 5 + n / 25 + n / 125 ... 。
题解到这一步就能开始写程序了：
// 更加高效的计算因子 5
public int trailingZeroes_3(int n) {
int count = 0;
while (n > 0) {
n /= 5;
count += n;
}
return count;
}
终于出结果了，我太难了，不过 LeetCode 把这道题的难度定成简单真的合适么。。。
