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+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！