LeetCode算法题-Factorial Trailing Zeroes(Java实现)

LeetCode算法题-Factorial Trailing Zeroes(Java实现)

这是悦乐书的第183次更新,第185篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第42题(顺位题号是172)。给定一个整数n,返回n!中的尾随零数。例如:

输入:3
输出:0
说明:3! = 6,没有尾随零。

输入:5
输出:1
说明:5! = 120,一个尾随零。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

特殊情况:当n小于等于0的时候,直接返回0。

先把n的阶乘算出来,再转为字符串,接着从字符串的最后一位往前遍历找0出现的次数,没有碰到0就就结束循环。为了避免计算阶乘溢出,使用BigInteger来做计算,借助其multiply方法。

public int trailingZeroes(int n) {
        int result = 0;
        if (n <= 0) {
            return result;
        }
        BigInteger num = new BigInteger("1");
        for (long i=1; i <= n; i++) {
            num = num.multiply(new BigInteger(i+""));
        }
        String str = num + "";
        if (str.lastIndexOf("0") != -1) {
            for (int j = str.length(); j > 0; j--) {
                if ("0".equals(str.substring(j-1, j))) {
                    result++;
                } else {
                    break;
                }
            }
        }
        return result;
}

此解法是一种思路,但是不推荐这么做,时间复杂度是O(n),空间复杂度是0(n)。

03 第二种解法

要判断n做完阶乘后的整数带几个0,可以反过来思考,尾数0可以由那些数相乘得到?0可以由10的倍数来得到,但是n的阶乘我们不能单独判断10出现的次数,还要继续分解,10是2乘以5的结果,任意一个正整数的阶乘,2出现的次数肯定多于5出现的次数,那就计算5出现的次数,到此是否就完了?还没有,因为有些数字自身就是带5的,比如25,125之类的,最后可以归纳成f(n)=n/5 + f(n/5),可以使用递归,也可以使用循环结构。

这是递归的解法。

public int trailingZeroes2(int n) {
    if (n<5) return 0;
    if (n<10) return 1;
    return n/5 + trailingZeroes2(n/5);
}

这是使用循环结构的解法。

public int trailingZeroes3(int n) {
    int result = 0;
    while (n>0) {
        result += n/5;
        n /= 5;
    }
    return result;
}

还有更加疯狂的,一行代码搞定。

public int trailingZeroes4(int n) {
    return n == 0 ? 0 : n/5 + trailingZeroes4(n/5);
}


04 小结

算法专题目前已连续日更超过一个月,算法题文章42+篇,