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

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 0875. 愛吃香蕉的珂珂 ## 題目地址(875. 愛吃香蕉的珂珂) <https://leetcode-cn.com/problems/koko-eating-bananas/description/> ## 題目描述 ``` <pre class="calibre18">``` 珂珂喜歡吃香蕉。這里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警衛已經離開了,將在 H 小時后回來。 珂珂可以決定她吃香蕉的速度 K (單位:根/小時)。每個小時,她將會選擇一堆香蕉,從中吃掉 K 根。如果這堆香蕉少于 K 根,她將吃掉這堆的所有香蕉,然后這一小時內不會再吃更多的香蕉。 珂珂喜歡慢慢吃,但仍然想在警衛回來前吃掉所有的香蕉。 返回她可以在 H 小時內吃掉所有香蕉的最小速度 K(K 為整數)。 示例 1: 輸入: piles = [3,6,7,11], H = 8 輸出: 4 示例 2: 輸入: piles = [30,11,23,4,20], H = 5 輸出: 30 示例 3: 輸入: piles = [30,11,23,4,20], H = 6 輸出: 23 提示: 1 <= piles.length <= 10^4 piles.length <= H <= 10^9 1 <= piles[i] <= 10^9 ``` ``` ## 前置知識 - 二分查找 ## 公司 - 字節 ## 思路 符合直覺的做法是,選擇最大的堆的香蕉數,然后試一下能不能行,如果不行則直接返回上次計算的結果,如果行,我們減少 1 個香蕉,試試行不行,依次類推。計算出剛好不行的即可。這種解法的時間復雜度比較高,為 O(N?M)O(N \* M)O(N?M),其中 N 為 piles 長度, M 為 Piles 中最大的數。。 這道題如果能看出來是二分法解決,那么其實很簡單。為什么它是二分問題呢?我這里畫了個圖,我相信你看了就明白了。 ![](https://img.kancloud.cn/4b/04/4b045d9a3ad9eba0ca9ac4c3d7301b3d_936x787.jpg) > 香蕉堆的香蕉個數上限是 10^9, 珂珂這也太能吃了吧? ## 關鍵點解析 - 二分查找 ## 代碼 代碼支持:Python,JavaScript 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">canEatAllBananas</span><span class="hljs-params">(self, piles, H, K)</span>:</span> t = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> pile <span class="hljs-keyword">in</span> piles: t += math.ceil(pile / K) <span class="hljs-keyword">return</span> t <= H <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minEatingSpeed</span><span class="hljs-params">(self, piles: List[int], H: int)</span> -> int:</span> l, r = <span class="hljs-params">1</span>, max(piles) <span class="hljs-title"># [l, r) , 左閉右開的好處是如果能找到,那么返回 l 和 r 都是一樣的,因為最終 l 等于 r。</span> <span class="hljs-keyword">while</span> l < r: mid = (l + r) >> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> self.canEatAllBananas(piles, H, mid): r = mid <span class="hljs-keyword">else</span>: l = mid + <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> l ``` ``` JavaScript Code: ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">canEatAllBananas</span>(<span class="hljs-params">piles, H, mid</span>) </span>{ <span class="hljs-keyword">let</span> h = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> pile <span class="hljs-keyword">of</span> piles) { h += <span class="hljs-params">Math</span>.ceil(pile / mid); } <span class="hljs-keyword">return</span> h <= H; } <span class="hljs-title">/** * @param {number[]} piles * @param {number} H * @return {number} */</span> <span class="hljs-keyword">var</span> minEatingSpeed = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">piles, H</span>) </span>{ <span class="hljs-keyword">let</span> lo = <span class="hljs-params">1</span>, hi = <span class="hljs-params">Math</span>.max(...piles); <span class="hljs-title">// [l, r) , 左閉右開的好處是如果能找到,那么返回 l 和 r 都是一樣的,因為最終 l 等于 r。</span> <span class="hljs-keyword">while</span> (lo <= hi) { <span class="hljs-keyword">let</span> mid = lo + ((hi - lo) >> <span class="hljs-params">1</span>); <span class="hljs-keyword">if</span> (canEatAllBananas(piles, H, mid)) { hi = mid - <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> { lo = mid + <span class="hljs-params">1</span>; } } <span class="hljs-keyword">return</span> lo; <span class="hljs-title">// 不能選擇hi</span> }; ``` ``` **復雜度分析** - 時間復雜度:O(max(N,N?logM))O(max(N, N \* logM))O(max(N,N?logM)),其中 N 為 piles 長度, M 為 Piles 中最大的數。 - 空間復雜度:O(1)O(1)O(1) ## 模板 分享幾個常用的的二分法模板。 ### 查找一個數 ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">binarySearch</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> target)</span> </span>{ <span class="hljs-title">// 左右都閉合的區間 [l, r]</span> <span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> right = nums.length - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span>(left <= right) { <span class="hljs-keyword">int</span> mid = left + (right - left) / <span class="hljs-params">2</span>; <span class="hljs-keyword">if</span>(nums[mid] == target) <span class="hljs-keyword">return</span> mid; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (nums[mid] < target) <span class="hljs-title">// 搜索區間變為 [mid+1, right]</span> left = mid + <span class="hljs-params">1</span>; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (nums[mid] > target) <span class="hljs-title">// 搜索區間變為 [left, mid - 1]</span> right = mid - <span class="hljs-params">1</span>; } <span class="hljs-keyword">return</span> -<span class="hljs-params">1</span>; } ``` ``` ### 尋找最左邊的滿足條件的值 ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">binarySearchLeft</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> target)</span> </span>{ <span class="hljs-title">// 搜索區間為 [left, right]</span> <span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span>; <span class="hljs-keyword">int</span> right = nums.length - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span> (left <= right) { <span class="hljs-keyword">int</span> mid = left + (right - left) / <span class="hljs-params">2</span>; <span class="hljs-keyword">if</span> (nums[mid] < target) { <span class="hljs-title">// 搜索區間變為 [mid+1, right]</span> left = mid + <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (nums[mid] > target) { <span class="hljs-title">// 搜索區間變為 [left, mid-1]</span> right = mid - <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (nums[mid] == target) { <span class="hljs-title">// 收縮右邊界</span> right = mid - <span class="hljs-params">1</span>; } } <span class="hljs-title">// 檢查是否越界</span> <span class="hljs-keyword">if</span> (left >= nums.length || nums[left] != target) <span class="hljs-keyword">return</span> -<span class="hljs-params">1</span>; <span class="hljs-keyword">return</span> left; } ``` ``` ### 尋找最右邊的滿足條件的值 ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">binarySearchRight</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> target)</span> </span>{ <span class="hljs-title">// 搜索區間為 [left, right]</span> <span class="hljs-keyword">int</span> left = <span class="hljs-params">0</span> <span class="hljs-keyword">int</span> right = nums.length - <span class="hljs-params">1</span>; <span class="hljs-keyword">while</span> (left <= right) { <span class="hljs-keyword">int</span> mid = left + (right - left) / <span class="hljs-params">2</span>; <span class="hljs-keyword">if</span> (nums[mid] < target) { <span class="hljs-title">// 搜索區間變為 [mid+1, right]</span> left = mid + <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (nums[mid] > target) { <span class="hljs-title">// 搜索區間變為 [left, mid-1]</span> right = mid - <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (nums[mid] == target) { <span class="hljs-title">// 收縮左邊界</span> left = mid + <span class="hljs-params">1</span>; } } <span class="hljs-title">// 檢查是否越界</span> <span class="hljs-keyword">if</span> (right < <span class="hljs-params">0</span> || nums[right] != target) <span class="hljs-keyword">return</span> -<span class="hljs-params">1</span>; <span class="hljs-keyword">return</span> right; } ``` ``` > 如果題目重點不是二分,也就是說二分只是眾多步驟中的一步,大家也可以直接調用語言的 API,比如 Python 的 bisect 模塊。 更多題解可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_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>

                              哎呀哎呀视频在线观看