tags: Leetcode medium binary search array python c++

875. Koko Eating Bananas

[題目連結:] https://leetcode.com/problems/koko-eating-bananas/

題目:

解題想法:

• 此題為有n串香蕉，第i串有piles[i]根香蕉

  • 守衛h小時回來
  • 設一小時能吃k根香蕉
    • 吃完第i串後無法再同一小時內吃另外第j串
    • 若第i串有x根香蕉，且x<k，則依舊需要等該小時過完，才能繼續下一串，意思為: 若有餘數需無條件進位1小時
  • 求k使得能以最慢速度吃完所有香蕉

• Binary Search二分法變化題:

  • 搜查範圍為1~max(piles)之間
    • 大於max肯定不是最慢速度了
  • 二分找適當的速度之下可以全部吃完且滿足時間內

Python:

class Solution(object):
    def minEatingSpeed(self, piles, h):
        """
        :type piles: List[int]
        :type h: int
        :rtype: int
        """
        #二分搜的變化
        #範圍為1與max(piles)之間 大於max肯定不是最慢速度
        #二分找適當的速度之下可以全部吃完且滿足時間內
        minSpeed=1
        maxSpeed=max(piles)
        while minSpeed<=maxSpeed:
            mid=(minSpeed+maxSpeed)/2
            totalHour=0
            for val in piles:
                carry=0 if val%mid==0 else 1 #餘數需多加1小時
                totalHour+=(val/mid)+carry
            if totalHour<=h: #吃太快了
                maxSpeed=mid-1
            else:
                minSpeed=mid+1
        return minSpeed

C++:

• C++找最大原素: *max_element
  • https://blog.csdn.net/A_Eagle/article/details/7373165
• 因為此題範圍 piles.length <= h <= 109
  • 第11行用long long int，避免overflow用

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int min=1;
        int max=*max_element(piles.begin(), piles.end());
        while (min<=max){
            int mid=min+(max-min)/2;
            long long int totalHours=0;
            for (auto val: piles){
                int carry= (val%mid==0)? 0: 1;
                totalHours+=int(val/mid)+carry;
            }
            if (totalHours<=h)
                max=mid-1;
            else
                min=mid+1;
        }
        return min;
    }
};