[LeetCode]Koko Eating Bananas

内容简介：Koko loves to eat bananas. There areKoko can decide her bananas-per-hour eating speed of

题目描述：

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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

[LeetCode]Koko Eating Bananas

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

数值方法和MATLAB实现与应用

拉克唐瓦尔德 / 机械工业出版社 / 2004-9 / 59.00元

本书是关于数值方法和MATLAB的介绍，是针对高等院校理工科专业学生编写的教材。数值方法可以用来生成其他方法无法求解的问题的近似解。本书的主要目的是为应用计算打下坚实的基础，由简单到复杂讲述了标准数值方法在实际问题中的实现和应用。本书通篇使用良好的编程习惯向读者展示了如何清楚地表达计算思想及编制文档。书中通过给读者提供大量的可直接运行的代码库以及讲解MARLAB工具箱中内置函数使用的数量方法，帮助......一起来看看《数值方法和MATLAB实现与应用》这本书的介绍吧!

码农工具