题目描述:给定一个整数 n ，返回 n! 结果尾数中零的数量。 示例 1：输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2：输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零。
说明: 你算法的时间复杂度应为 O(log n) 。 题目分析: 虽然这道题标着“简单”，但如果没有数学思维还真觉得不简单。显然，一看这道题你就会想到直接计算阶乘然后求末尾 0 的个数，但这种方法速度太慢了，甚至很容易溢出，所以在这里是行不通的。 那就让我们分析一下，首先，末尾的 0 如何而来，很容易想到，在九九乘法表中，有 2 * 5 = 10 结果末尾有 0 。所以，阶乘结果末尾有多少个 0 ，只要给当前的数乘以 10 就可在结果末尾加一个 0 。 看一个例子，对于 5! = 5 * 4 * 3 * 2 * 1 = 120 ，结果中末尾有一个 0 ，是因为式子中 5 * 2 = 10 得来的，所以只要判断式子中有多少对 5 和 2 即可得到结果末尾 0 的个数。对于 2 来说，每出现两个数总有一个是 2 的倍数，而对于 5 来说，每出现五个数才有一个是 5 的倍数，是 2 的倍数 的数总是比是 5 的倍数 的数要多，所以我们直接找是 5 的倍数 的数就行，例如找到 10 个是 5 的倍数 的数一定会找到超过 10 个是 2 的倍数 的数，所以这 10 个 5 的倍数 的数一定能找到足够多的 2 与之相乘得到 10 。因此通过 n / 5 就可以计算出 5 的个数。继续分析，我们会知道每隔 25 个数出现了两个 5 ，因为 5 * 5 = 25 ，所以还要多算上一个 5 ，即加上 n / 25 个 5 。同理， 5 * 5 * 5 = 125 ，出现了三个 5 ，我们还是一样要加上 n / 125 个 5 ... 最后，应该使用 n / 5 + n / 25 + n / 125 + ... 计算出现 5 的个数。我们直接通过循环统计 5 的个数就行，计算的时候先算 n / 125 再通过 n = n / 5 把 n 更新，再计算 n / 25 ，以防止溢出。 题解一:执行用时: 1 ms 内存消耗: 35 MB class Solution {
public int trailingZeroes(int n) {
// 统计末尾 0 的个数
int zeroCount = 0;
// 当 n 大于 0 循环除于 5 获得 5 的个数
while (n > 0) {
n /= 5;
// 累加计算 5 的个数
zeroCount += n;
}
return zeroCount;
}
}
题解二:执行用时: 1 ms 内存消耗: 35.4 MB class Solution {
// 递归求解法
public int trailingZeroes(int n) {
return n == 0? 0: n / 5 + trailingZeroes(n / 5);
}
}
|
