• 1

  • 531

每日一道 LeetCode (41):阶乘后的零

云哥

关注云计算

1星期前

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

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 把这道题的难度定成简单真的合适么。。。

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

云计算

531

相关文章推荐

未登录头像

暂无评论