<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 0172. 階乘后的零 ## 題目地址(172. 階乘后的零) <https://leetcode-cn.com/problems/factorial-trailing-zeroes/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數 n,返回 n! 結果尾數中零的數量。 示例 1: 輸入: 3 輸出: 0 解釋: 3! = 6, 尾數中沒有零。 示例 2: 輸入: 5 輸出: 1 解釋: 5! = 120, 尾數中有 1 個零. 說明: 你算法的時間復雜度應為 O(log n) 。 ``` ``` ## 前置知識 - [遞歸](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) ## 公司 - 阿里 - 騰訊 - 百度 - bloomberg ## 思路 我們需要求解這n個數字相乘的結果末尾有多少個0,由于題目要求log的復雜度,因此暴力求解是不行的。 通過觀察,我們發現如果想要結果末尾是0,必須是分解質因數之后,2 和 5 相乘才行,同時因數分解之后發現5的個數遠小于2, 因此我們只需要求解這n數字分解質因數之后一共有多少個5即可. ![](https://img.kancloud.cn/41/b5/41b5138e5bbcb80060877f941d4d25a6_649x331.jpg) 如圖如果n為30,那么結果應該是圖中紅色5的個數,即7。 ![](https://img.kancloud.cn/21/25/212511bf341a2fa80bef696c4f83e7fe_639x400.jpg) 我們的結果并不是直接f(n) = n / 5, 比如n為30, 25中是有兩個5的。 類似,n為150,會有7個這樣的數字,通過觀察我們發現規律`f(n) = n/5 + n/5^2 + n/5^3 + n/5^4 + n/5^5+..` ![](https://img.kancloud.cn/1a/cb/1acb85700ac1db3c0c585101e1ec8059_615x325.jpg) 如果可以發現上面的規律,用遞歸還是循環實現這個算式就看你的了。 ## 關鍵點解析 - 數論 ## 代碼 - 語言支持:JS,Python Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=172 lang=javascript * * [172] Factorial Trailing Zeroes */</span> <span class="hljs-title">/** * @param {number} n * @return {number} */</span> <span class="hljs-keyword">var</span> trailingZeroes = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">n</span>) </span>{ <span class="hljs-title">// tag: 數論</span> <span class="hljs-title">// if (n === 0) return n;</span> <span class="hljs-title">// 遞歸: f(n) = n / 5 + f(n / 5)</span> <span class="hljs-title">// return Math.floor(n / 5) + trailingZeroes(Math.floor(n / 5));</span> <span class="hljs-keyword">let</span> count = <span class="hljs-params">0</span>; <span class="hljs-keyword">while</span> (n >= <span class="hljs-params">5</span>) { count += <span class="hljs-params">Math</span>.floor(n / <span class="hljs-params">5</span>); n = <span class="hljs-params">Math</span>.floor(n / <span class="hljs-params">5</span>); } <span class="hljs-keyword">return</span> count; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">trailingZeroes</span><span class="hljs-params">(self, n: int)</span> -> int:</span> count = <span class="hljs-params">0</span> <span class="hljs-keyword">while</span> n >= <span class="hljs-params">5</span>: n = n // <span class="hljs-params">5</span> count += n <span class="hljs-keyword">return</span> count <span class="hljs-title"># 遞歸</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">trailingZeroes</span><span class="hljs-params">(self, n: int)</span> -> int:</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> <span class="hljs-keyword">return</span> n // <span class="hljs-params">5</span> + self.trailingZeroes(n // <span class="hljs-params">5</span>) ``` ``` **復雜度分析** - 時間復雜度:O(logN)O(logN)O(logN) - 空間復雜度:O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看