2024年5月23日发(作者：犹浩歌)
题目:爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 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 <= <= 10^4
• <= H <= 10^9
• 1 <= piles[i] <= 10^9
语言:cpp
class Solution {
public:
int minEatingSpeed(vector
int lo = 1, hi = pow(10, 9);
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (!possible(piles, H, mi))
lo = mi + 1;
else
hi = mi;
}
return lo;
}
// Can Koko eat all bananas in H hours with eating speed K?
bool possible(vector
int time = 0;
for (int p: piles)
time += (p - 1) / K + 1;
return time <= H;
}
};
语言:java
class Solution {
public int minEatingSpeed(int[] piles, int H) {
int lo = 1;
int hi = 1_000_000_000;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (!possible(piles, H, mi))
lo = mi + 1;
else
hi = mi;
}
return lo;
}
// Can Koko eat all bananas in H hours with eating speed K?
public boolean possible(int[] piles, int H, int K) {
int time = 0;
for (int p: piles)
time += (p-1) / K + 1;
return time <= H;
}
}
语言:java
class Solution {
public int minEatingSpeed(int[] piles, int h) {
// 先确定单调关系 该题目中 耗时和速度是单调递减的关系
// 如果耗时越多则速度越小 ， 速度越小则耗时越大
(piles);
if(h==) return piles[-1];
int left = 1;
int right = piles[-1];
while(left<=right){
int middle = (left + right) / 2;
if(getTime(piles,middle)>h) left = middle+1;
else {
right = middle-1;
}
}
//找到最接近消耗时间 h的速率,该速率为要找的答案
return left;
}
public int getTime(int []piles,int speed){
int res = 0;
for(int bananaNumber:piles){
res = res + (bananaNumber / speed);
if(bananaNumber % speed !=0){
res++;
}
}
return res;
}
}
语言:java
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1;
int right = 1000000000;
while(left < right){
int mid = left + (right - left)/2;
if(f(piles, mid) <= h){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
// 返回以速度v吃完piles中的所有香蕉需要多少小时
public int f(int[] piles, int v){
int hours = 0;
for(int i = 0; i < ; i++){
hours += piles[i]/v;
if(piles[i] % v > 0){
hours++;
}
}
return hours;
}
}
语言:python
class Solution(object):
def minEatingSpeed(self, piles, H):
# Can Koko eat all bananas in H hours with eating speed K?
def possible(K):
return sum((p-1) / K + 1 for p in piles) <= H
lo, hi = 1, max(piles)
while lo < hi:
mi = (lo + hi) / 2
if not possible(mi):
lo = mi + 1
else:
hi = mi
return lo
语言:python
class Solution(object):
def minEatingSpeed(self, piles, h):
def cost_t(speed):
temp = 0
for x in piles:
temp += x//speed + (0+(x%speed>0))
return temp
left, right = 1, max(piles)
while left < right:
mid = left + (right-left)//2
cost = cost_t(mid)
if cost>h:
left = mid+1
elif cost<=h:
right = mid
return left
语言:js
var minEatingSpeed = function(piles, h) {
// 每小时吃 k 根, 最小是 1 根, 从 1 开始试吃
let k = 1
// 一直试吃
while(true) {
// 可以吃完，返回 k
if(canFinish(...)) {
return k
}
// 当不能吃完的时候，多吃一根再试试
k++
}
};
语言:js
// 每小时吃 k, 有 piles 堆, 给了 h 小时
function canFinish(k, h, piles) {
// 假设总时间为 total, 当 total 大于 h 的时候，说明吃不完
let totalTime = 0
// 循环每堆
for (var i = 0; i < ; i++) {
// 当香蕉少于 k 的时候，当成 1 小时算
if (piles[i] <= k) {
totalTime += 1
// 当香蕉大于 k 的时候，多出的部分按1小时记
} else {
totalTime += (piles[i] / k)
}
// 已经超时了？那就直接返回吃不完，不再继续吃
if (totalTime > h) {
return false
}
}
// 最后吃完了
return true
}
语言:js
var minEatingSpeed = function (piles, h) {
// 每小时吃 k 根, 最小是 1 根, 从 1 开始试吃
let k = 1
// 一直试吃
while (true) {
// 可以吃完，返回 k
if (canFinish(k, h, piles)) {
return k
}
// 当不能吃完的时候，多吃一根再试试
k++
}
}
// 每小时吃 k, 有 piles 堆, 给了 h 小时
function canFinish(k, h, piles) {
// 假设总时间为 total, 当 total 大于 h 的时候，说明吃不完
let totalTime = 0
// 循环每堆
for (var i = 0; i < ; i++) {
// 当香蕉少于 k 的时候，当成 1 小时算
if (piles[i] <= k) {
totalTime += 1
// 当香蕉大于 k 的时候，多出的部分按1小时记
} else {
totalTime += (piles[i] / k)
}
// 已经超时了？那就直接返回吃不完，不再继续吃
if (totalTime > h) {
return false
}
}
// 最后吃完了
return true
}
语言:golang
func minEatingSpeed(piles []int, h int) int {
left := 0
right := 0
for _, pile := range piles {
right = max(right, pile)
}
for left < right {
mid := left + (right - left) / 2
if 0 == mid { //如果mid == 0，则每小时吃<1数量也能吃完，则返回1
return 1
}
if getHours(piles, mid) <= h { //如果速度为mid，时间<=h，则速度快，将rig
ht调整到mid
right = mid
} else if getHours(piles, mid) > h { //如果速度为mid，时间>h，则速度慢，将
left调整到mid
left = mid + 1
}
}
return left
}
func getHours(piles []int, x int) int {
hours := 0
for _, pile := range piles {
hours += pile / x //计算pile个香蕉吃几个小时能吃完
if pile % x > 0 {
hours++
}
}
return hours
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
语言:php
class Solution {
/**
* @param Integer[] $piles
* @param Integer $h
* @return Integer
*/
function minEatingSpeed($piles, $h) {
$left=1;
$right=max($piles);
while($left<=$right){
//二分查找
$mid=$left+floor(($right-$left)/2);
if($this->canFinish($piles,$mid,$h)){
$right=$mid-1;
}else{
$left=$mid+1;
}
}
return $left;
}
function canFinish($piles,$speed, $h){
//以speed速度，在h小时内是否可以吃
完所有香蕉
$time=0;
foreach($piles as $k=>$v){
$time+=$this->timeOf($v,$speed);
}
return $time<=$h;
}
function timeOf($num,$speed){
//以speed速度，吃完num数量香蕉，需要多
久
return ceil($num/$speed);
}
}
2024年5月23日发(作者：犹浩歌)
题目:爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 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 <= <= 10^4
• <= H <= 10^9
• 1 <= piles[i] <= 10^9
语言:cpp
class Solution {
public:
int minEatingSpeed(vector
int lo = 1, hi = pow(10, 9);
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (!possible(piles, H, mi))
lo = mi + 1;
else
hi = mi;
}
return lo;
}
// Can Koko eat all bananas in H hours with eating speed K?
bool possible(vector
int time = 0;
for (int p: piles)
time += (p - 1) / K + 1;
return time <= H;
}
};
语言:java
class Solution {
public int minEatingSpeed(int[] piles, int H) {
int lo = 1;
int hi = 1_000_000_000;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (!possible(piles, H, mi))
lo = mi + 1;
else
hi = mi;
}
return lo;
}
// Can Koko eat all bananas in H hours with eating speed K?
public boolean possible(int[] piles, int H, int K) {
int time = 0;
for (int p: piles)
time += (p-1) / K + 1;
return time <= H;
}
}
语言:java
class Solution {
public int minEatingSpeed(int[] piles, int h) {
// 先确定单调关系 该题目中 耗时和速度是单调递减的关系
// 如果耗时越多则速度越小 ， 速度越小则耗时越大
(piles);
if(h==) return piles[-1];
int left = 1;
int right = piles[-1];
while(left<=right){
int middle = (left + right) / 2;
if(getTime(piles,middle)>h) left = middle+1;
else {
right = middle-1;
}
}
//找到最接近消耗时间 h的速率,该速率为要找的答案
return left;
}
public int getTime(int []piles,int speed){
int res = 0;
for(int bananaNumber:piles){
res = res + (bananaNumber / speed);
if(bananaNumber % speed !=0){
res++;
}
}
return res;
}
}
语言:java
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1;
int right = 1000000000;
while(left < right){
int mid = left + (right - left)/2;
if(f(piles, mid) <= h){
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
// 返回以速度v吃完piles中的所有香蕉需要多少小时
public int f(int[] piles, int v){
int hours = 0;
for(int i = 0; i < ; i++){
hours += piles[i]/v;
if(piles[i] % v > 0){
hours++;
}
}
return hours;
}
}
语言:python
class Solution(object):
def minEatingSpeed(self, piles, H):
# Can Koko eat all bananas in H hours with eating speed K?
def possible(K):
return sum((p-1) / K + 1 for p in piles) <= H
lo, hi = 1, max(piles)
while lo < hi:
mi = (lo + hi) / 2
if not possible(mi):
lo = mi + 1
else:
hi = mi
return lo
语言:python
class Solution(object):
def minEatingSpeed(self, piles, h):
def cost_t(speed):
temp = 0
for x in piles:
temp += x//speed + (0+(x%speed>0))
return temp
left, right = 1, max(piles)
while left < right:
mid = left + (right-left)//2
cost = cost_t(mid)
if cost>h:
left = mid+1
elif cost<=h:
right = mid
return left
语言:js
var minEatingSpeed = function(piles, h) {
// 每小时吃 k 根, 最小是 1 根, 从 1 开始试吃
let k = 1
// 一直试吃
while(true) {
// 可以吃完，返回 k
if(canFinish(...)) {
return k
}
// 当不能吃完的时候，多吃一根再试试
k++
}
};
语言:js
// 每小时吃 k, 有 piles 堆, 给了 h 小时
function canFinish(k, h, piles) {
// 假设总时间为 total, 当 total 大于 h 的时候，说明吃不完
let totalTime = 0
// 循环每堆
for (var i = 0; i < ; i++) {
// 当香蕉少于 k 的时候，当成 1 小时算
if (piles[i] <= k) {
totalTime += 1
// 当香蕉大于 k 的时候，多出的部分按1小时记
} else {
totalTime += (piles[i] / k)
}
// 已经超时了？那就直接返回吃不完，不再继续吃
if (totalTime > h) {
return false
}
}
// 最后吃完了
return true
}
语言:js
var minEatingSpeed = function (piles, h) {
// 每小时吃 k 根, 最小是 1 根, 从 1 开始试吃
let k = 1
// 一直试吃
while (true) {
// 可以吃完，返回 k
if (canFinish(k, h, piles)) {
return k
}
// 当不能吃完的时候，多吃一根再试试
k++
}
}
// 每小时吃 k, 有 piles 堆, 给了 h 小时
function canFinish(k, h, piles) {
// 假设总时间为 total, 当 total 大于 h 的时候，说明吃不完
let totalTime = 0
// 循环每堆
for (var i = 0; i < ; i++) {
// 当香蕉少于 k 的时候，当成 1 小时算
if (piles[i] <= k) {
totalTime += 1
// 当香蕉大于 k 的时候，多出的部分按1小时记
} else {
totalTime += (piles[i] / k)
}
// 已经超时了？那就直接返回吃不完，不再继续吃
if (totalTime > h) {
return false
}
}
// 最后吃完了
return true
}
语言:golang
func minEatingSpeed(piles []int, h int) int {
left := 0
right := 0
for _, pile := range piles {
right = max(right, pile)
}
for left < right {
mid := left + (right - left) / 2
if 0 == mid { //如果mid == 0，则每小时吃<1数量也能吃完，则返回1
return 1
}
if getHours(piles, mid) <= h { //如果速度为mid，时间<=h，则速度快，将rig
ht调整到mid
right = mid
} else if getHours(piles, mid) > h { //如果速度为mid，时间>h，则速度慢，将
left调整到mid
left = mid + 1
}
}
return left
}
func getHours(piles []int, x int) int {
hours := 0
for _, pile := range piles {
hours += pile / x //计算pile个香蕉吃几个小时能吃完
if pile % x > 0 {
hours++
}
}
return hours
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
语言:php
class Solution {
/**
* @param Integer[] $piles
* @param Integer $h
* @return Integer
*/
function minEatingSpeed($piles, $h) {
$left=1;
$right=max($piles);
while($left<=$right){
//二分查找
$mid=$left+floor(($right-$left)/2);
if($this->canFinish($piles,$mid,$h)){
$right=$mid-1;
}else{
$left=$mid+1;
}
}
return $left;
}
function canFinish($piles,$speed, $h){
//以speed速度，在h小时内是否可以吃
完所有香蕉
$time=0;
foreach($piles as $k=>$v){
$time+=$this->timeOf($v,$speed);
}
return $time<=$h;
}
function timeOf($num,$speed){
//以speed速度，吃完num数量香蕉，需要多
久
return ceil($num/$speed);
}
}