[LeetCode]Koko Eating Bananas

题目描述:

LeetCode 875. Koko Eating Bananas

Koko loves to eat bananas.  There are N piles of bananas, the i-th pile has piles[i] bananas.  The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K.  Each hour, she chooses some pile of bananas, and eats K bananas from that pile.  If the pile has less than K bananas, she eats all of them instead, and won't eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

  • 1 <= piles.length <= 10^4
  • piles.length <= H <= 10^9
  • 1 <= piles[i] <= 10^9

题目大意:

数组piles表示若干堆香蕉,需要在H小时内吃完。Koko每小时任选一堆,可以至多吃掉Speed根。

求最小的Speed

解题思路:

二分枚举答案(Binary Search)

时间复杂度 O( N * log(N) )

给定吃香蕉的速度Speed时,用O(N)的代价可以求出吃完所有香蕉的用时T

当T <= H时,表示Speed足够,否则表示Speed不足。

Python代码:

class Solution(object):
    def minEatingSpeed(self, piles, H):
        """
        :type piles: List[int]
        :type H: int
        :rtype: int
        """
        tryEat = lambda s: sum(int(math.ceil(1.0 * p / s)) for p in piles)
        left, right = 1, sum(piles)
        while left <= right:
            mid = (left + right) / 2
            if tryEat(mid) <= H: right = mid - 1
            else: left = mid + 1
        return left

 

本文链接:http://bookshadow.com/weblog/2018/07/22/leetcode-koko-eating-bananas/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论