长大后想做什么？做回小孩！

0%

LeetCode——阶乘后的零

发表于 分类于 Valine：
本文字数： 439

NO.172 阶乘后的零 简单

Y1hykj.png

思路一：暴力

如果是先计算阶乘 res ，再去数 res 低位有多少个，是行不通的，输入如果较大，阶乘很容易发生溢出，即使使用了 long 、BigInteger 等等大范围类型满足了存下大输入的阶乘结果，计算阶乘的过程和求低位0的过程都是不满足限制时间 O(logn) 的。

思路二：优化暴力，找 5

分析一下阶乘后的 0 是如何产生的，自然想到是每次乘一个 10 低位增加一个 0 ，10=2*5，那么为什么只找 5 ，不考虑 2 呢？

1
2
3
4
5
6
7
5!	= 5 * 4 * 3 * 2 * 1

11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 
    = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1
    
从一个 5 的倍数，到下一个 5 的倍数之间，一定存在偶数！偶数自然是可以拆成 2*x 的形式！
所以只要找到 5，那么一定存在 2 和其配对，得到 10 !

综上所述，只要遍历阶乘中出现的每个数，找 5 出现的次数即可。

注意：要找到的是 5 ！ 例如，25 = 5 * 5 算是 2 个 5 ，125 = 5 * 5 * 5 算是 3 个 5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int trailingZeroes(int n) {
    int count = 0;
    //遍历
    for (int i = 1; i <= n; i++) {
        //是 5 的倍数,统计能分解成几个 5 
        int num = i;
        while (num > 0) {
            if (num % 5 == 0) {
                count ++;
                num /= 5;
            }else {
                break;
            }
        }
    }
    return count;
}

时间复杂度：O(n) 不符合要求，超时！

思路三：隔 5 找 5

每隔 5 个数会出现 5 = 5 一个 5，每隔 25 个数出现 25 = 5 * 5 两个 5，每隔 125 个数出现 125 = 5 * 5 * 5 三个 5。。。以此类推。。。

最终 5 的个数 = n/5 + n/25 + n/125 + ... 

1
2
3
4
5
6
7
8
public int trailingZeroes(int n) {
    int count = 0;
    while (n > 0) {
        count += n/5;
        n/=5;
    }
    return count;
}

时间复杂度：O(logn)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github