【刷算法】LeetCode- 階乘后的零

layman 發布于2019-08-23 10:42 / 2388人閱讀

摘要：原題地址中國題目描述給定一個整數，返回結果尾數中零的數量。示例輸入輸出解釋尾數中有個零說明你算法的時間復雜度應為。分析首先暴力破解法就是直接把最終的結果求出來然后看末尾有幾個，但是這樣做的時間復雜度肯定是太大了。

原題地址：LeetCode中國-172

題目描述

給定一個整數 n，返回 n! 結果尾數中零的數量。

示例 1:

輸入: 3
輸出: 0
解釋: 3! = 6, 尾數中沒有零。
示例 2:

輸入: 5
輸出: 1
解釋: 5! = 120, 尾數中有 1 個零.

說明: 你算法的時間復雜度應為 O(log n) 。

分析

首先暴力破解法就是直接把最終的結果求出來然后看末尾有幾個0，但是這樣做的時間復雜度肯定是太大了。

然后考慮到末尾的0是怎么形成的，首先10=2*5，20=2*2*5，30=3*2*5 ... 100=10*2*5

所以，問題的關鍵是看階乘里面2和5的數量，但是因為顯然2出現的數量大于5出現的數量，拿5的階乘來舉例子：

5！= (1) * (2) * (3) * (2*2) * (5)

出現了3個2、1個5，但是末尾只有1個0，所以階乘末尾0的個數就是階乘式中5的個數。但是如解法1的代碼所示，時間復雜度還是太高。

繼續考慮，對于50!，我們可以寫成：

5 ... 2*5 ... 3*5 ... 4*5 ... 5*5 ... 6*5 ... 7*5 ... 8*5 ... 9*5 ... 10 * 5

可以看出來從5到10*5一共有10個5，但是對于10來說，從1到10還有2個5，所以50！的結果末尾有12個0

解法1（不符合要求的時間復雜度）

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;
};

上面這個解法的時間復雜度是n*(logn)，不符合題意

解法2

var 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);
}

GPU云服務器云服務器階乘c語言算法數組 LeetCode LeetCode_String leetcode_35_SearchIn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/96610.html

LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
＜LeetCode天梯＞Day026 反轉鏈表（遞歸法+（迭代法）雙鏈表法） | 初級算法 | Py

摘要：關于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板，終止條件，遞歸調用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學路18號的車神? ?個人主頁：應無所住而生...

imingyu 2021-11-17 09:33 評論0 收藏0
小李飛刀：python你慢點飛，我的腦子還在后面追

摘要：默認參數設置默認參數時，有幾點要注意一是必選參數在前，默認參數在后，否則的解釋器會報錯二是如何設置默認參數。注意此處，獲得的其實是的拷貝，函數內對的改變不會影響到。使用遞歸函數需要注意防止棧溢出。總是在最前面的叨逼叨最近總是在想成長這兩個很常常被提起的事情，這對于一個已經25歲的半中年而言，已經是一個不太能高頻提起的詞。但是，最近一些事情吧，總讓我覺得我的生長期似乎比正常人來的晚了...

kevin 2019-07-30 18:40 評論0 收藏0