資訊專欄INFORMATION COLUMN
摘要：原題地址中國(guó)題目描述給定一個(gè)整數(shù)，返回結(jié)果尾數(shù)中零的數(shù)量。示例輸入輸出解釋尾數(shù)中有個(gè)零說明你算法的時(shí)間復(fù)雜度應(yīng)為。分析首先暴力破解法就是直接把最終的結(jié)果求出來然后看末尾有幾個(gè)，但是這樣做的時(shí)間復(fù)雜度肯定是太大了。
原題地址：LeetCode中國(guó)-172
給定一個(gè)整數(shù) n，返回 n! 結(jié)果尾數(shù)中零的數(shù)量。
示例 1:
輸入: 3
輸出: 0
解釋: 3! = 6, 尾數(shù)中沒有零。
示例 2:
輸入: 5
輸出: 1
解釋: 5! = 120, 尾數(shù)中有 1 個(gè)零.
說明: 你算法的時(shí)間復(fù)雜度應(yīng)為 O(log n) 。
分析首先暴力破解法就是直接把最終的結(jié)果求出來然后看末尾有幾個(gè)0，但是這樣做的時(shí)間復(fù)雜度肯定是太大了。
然后考慮到末尾的0是怎么形成的，首先10=2*5，20=2*2*5，30=3*2*5 ... 100=10*2*5
所以，問題的關(guān)鍵是看階乘里面2和5的數(shù)量，但是因?yàn)轱@然2出現(xiàn)的數(shù)量大于5出現(xiàn)的數(shù)量，拿5的階乘來舉例子：
5！= (1) * (2) * (3) * (2*2) * (5)
出現(xiàn)了3個(gè)2、1個(gè)5，但是末尾只有1個(gè)0，所以階乘末尾0的個(gè)數(shù)就是階乘式中5的個(gè)數(shù)。但是如解法1的代碼所示，時(shí)間復(fù)雜度還是太高。
繼續(xù)考慮，對(duì)于50!，我們可以寫成：
5 ... 2*5 ... 3*5 ... 4*5 ... 5*5 ... 6*5 ... 7*5 ... 8*5 ... 9*5 ... 10 * 5
可以看出來從5到10*5一共有10個(gè)5，但是對(duì)于10來說，從1到10還有2個(gè)5，所以50！的結(jié)果末尾有12個(gè)0
解法1（不符合要求的時(shí)間復(fù)雜度）var trailingZeroes = function(n) {
var count = 0;
for(var i = 1;i <= n;i++){
var temp = i;
while(temp%5 === 0){
count++;
temp /= 5;
}
}
return count;
};
上面這個(gè)解法的時(shí)間復(fù)雜度是n*(logn)，不符合題意
解法2var trailingZeroes = function(n) {
var count = 0;
while(n) {
count += divide(n,5);
n = divide(n,5);
}
return count;
};
function divide(n, m) {
return Math.floor(n/m);
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/96610.html
摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡(jiǎn)介：大家好，我是車神哥，府學(xué)路18號(hào)的車神? ?個(gè)人主頁(yè)：應(yīng)無(wú)所住而生...
摘要：默認(rèn)參數(shù)設(shè)置默認(rèn)參數(shù)時(shí)，有幾點(diǎn)要注意一是必選參數(shù)在前，默認(rèn)參數(shù)在后，否則的解釋器會(huì)報(bào)錯(cuò)二是如何設(shè)置默認(rèn)參數(shù)。注意此處，獲得的其實(shí)是的拷貝，函數(shù)內(nèi)對(duì)的改變不會(huì)影響到。使用遞歸函數(shù)需要注意防止棧溢出。 總是在最前面的叨逼叨 最近總是在想成長(zhǎng)這兩個(gè)很常常被提起的事情，這對(duì)于一個(gè)已經(jīng)25歲的半中年而言，已經(jīng)是一個(gè)不太能高頻提起的詞。但是，最近一些事情吧，總讓我覺得我的生長(zhǎng)期似乎比正常人來的晚了...
閱讀 1695·2021-10-13 09:39
閱讀 3167·2021-10-12 10:11
閱讀 559·2021-09-28 09:36
閱讀 2643·2019-08-30 15:55
閱讀 1393·2019-08-30 13:04
閱讀 636·2019-08-29 17:08
閱讀 1916·2019-08-29 14:14
閱讀 3415·2019-08-28 18:23
