這是悅樂書的第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+篇，公眾號對話框回復【數據結構與算法】、【算法】、【數據結構】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支持！
)
)
