[演算法題] 二分查詢之-愛吃香蕉的珂珂

語言: CN / TW / HK

一、題目描述:

珂珂喜歡吃香蕉。這裡有 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. 確定變數x 一般就是要求的最小值或最大值 2. 確定f(x) f是隨著x的遞增或遞減的函式 3. 確定target f(x)=target約束條件 4. 確定left,right邊界

2.1 遞增和遞減函式

遞增函式:

image.png

遞減函式:

image.png

2.2 解題

按步驟來:

2.2.1. 確定x

x就是 每小時吃香蕉的根數: x根/小時。

2.2.2 確定f(x)

看到target是小時,所以f(x)就是吃完所有香蕉的需要的總小時。

``` int f(int[] piles,x){ int hours=0; for(int i=0;i0){ hours++; } } return hours; }

```

2.2.3.確定約束條件

target==H。相當於找到等於target的元素。

2.2.4 左右邊界確定

left左邊界明顯為1,有邊界,看題目描述: 1 <= piles[i] <= 10^9,因此right取1000000000。當然,因為x表示吃香蕉的根數,它不會超過N堆香蕉的最大根數,所以可以遍歷取得piles[i]中的最大值。

注意,f是遞減的函式!!

public int minEatingSpeed(int[] piles, int H) {     int left = 1;     int right = 1000000000 + 1;          while (left ‹ right) {         int mid = left + (right - left) / 2;         if (f(piles, mid) == H) {             // 搜尋左側邊界,則需要收縮右側邊界             right = mid;         } else if (f(piles, mid) ‹ H) {             // 需要讓 f(x) 的返回值大一些             right = mid;         } else if (f(piles, mid) › H) {             // 需要讓 f(x) 的返回值小一些             left = mid + 1;         }     }     return left; }

最終, 因為要求x的最小值,那麼其實就是求f(x)==target的左邊第一個出現的元素!

所以程式碼如下:

``` class Solution { public int minEatingSpeed(int[] piles, int h) {

    int left=1;
    int right=1000000000;
    while(left<=right){
        int mid=left+(right-left)/2;
       int cost= eatCostTime(mid,piles);
        if(cost> h){
            //因為是遞減函式,所以要讓eatCostTime返回更小的值。因此調整的是左邊界
             left=mid+1;
        }else if(cost< h){
             //因為是遞減函式,所以要讓eatCostTime返回更大的值。因此調整的是左邊界
            right=mid-1;
        }else{
            System.out.println("mid: "+mid);
            if(0==mid||eatCostTime(mid-1,piles)!=h){
                return mid;
            }else{
                right=mid-1;
            }

        }

    }
    // 沒有找到
    return left;

}

public int eatCostTime(int x,int[] piles){
    int hour=0;
    for(int i=0;i<piles.length;i++){
        hour+=piles[i]/x;
        if(piles[i]%x>0){
            hour++;
        }
    }
    return hour;
}

}

```

三 原題連線:

珂珂喜歡吃香蕉