LeetCode演算法題-Factorial Trailing Zeroes（Java實現）
摘要：
這是悅樂書的第183
次更新，第185
篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第42題（順位題號是172）。給定一個整數n，返回n！中的尾隨零數。例如：
輸入：3
輸出：0
...
這是悅樂書的第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 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！