内容简介：Koko loves to eat bananas. There areKoko can decide her bananas-per-hour eating speed of
题目描述：
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
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Fortran 95/2003程序设计
中国电力出版社 / 2009-8 / 88.00元
Fortran是计算世界最早出现的高级程序设计语言之一，随着面向对象编程时代的到来，Fortran语言不仅保持了发展的步伐，而且继续在科学计算方面领先。《Fortran95/2003程序设计(第3版)》在第2～7章介绍了Fortan语言基础知识，为初学者提供入门学习资料；在第8～15章介绍了Fortran语言高级特性，为深入用好Fortran语言提供支持；在第16章讲述了Fortran语言面向对象......一起来看看 《Fortran 95/2003程序设计》 这本书的介绍吧!
Markdown 在线编辑器
Markdown 在线编辑器
html转js在线工具
html转js在线工具