
mzoe666888
2022/04/25阅读:18主题:兰青
爱吃香蕉的猩猩
大厂算法面试题《爱吃香蕉的猩猩》:既想舒舒服服的吃香蕉,又想在规定时间内吃完香蕉,猩猩该如何通过它的聪明才智做到呢?快来一起学习吧!
一、题目
珂珂喜欢吃香蕉。这里有 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
二、分析
题目求的是最小速度吃香蕉,猩猩能懒则懒,只要保证在警卫回来前吃完就行
贪图的不是吃的有多快,贪图的是在规定时间内以最小速度吃完即可
最小速度怎么求? 先搞定速度怎么求?
先找出每堆香蕉中的最多的香蕉数(R)是多少?然后从1~R
香蕉数范围内二分,求出中间位置的香蕉数,就是每小时吃的香蕉数,也就是吃的速度(每小时吃这么多根香蕉),以这个速度吃完所有香蕉需要的时间是多少?
怎么算每堆吃完的时间?每一堆香蕉吃完的时间为每一堆的香蕉数除以吃的速度,向上取整
如果吃完的时间大于警卫回来的时间,则吃的速度太慢,需要加大吃香蕉的速度,即需要吃更多的香蕉数(L = M + 1),如果吃完时间小于等于警卫回来的时间,则当前吃的速度还可以,但是猩猩又太懒,不想吃那么快,则减少吃的香蕉(R = M - 1),看能不能还满足时间要求,这不就是二分么!!!
猩猩吃完一堆的香蕉所需要的时间是多少?利用公式计算或者工具类,比如想达到 7/2 等于 4的效果,怎么弄?result = (7+2-1) / 2 = 4,比如 8/2 = (8+2-1) / 2 = 4
这猩猩太聪明了,既能慢慢悠悠的吃,又能吃完所有香蕉,真是聪明绝顶!

三、实现
public static int minEatingSpeed(int[] piles, int h) {
int L = 1;
int R = 0;
// 找出每堆中的最大香蕉数
for (int pile : piles) {
R = Math.max(R, pile);
}
int ans = 0;
int M = 0;
while (L <= R) {
M = L + ((R - L) >> 1);
if (hours(piles, M) <= h) {
ans = M;
R = M - 1;
} else {
L = M + 1;
}
}
return ans;
}
// 以speed的速度吃完所有香蕉,需要几个小时
// 时间向上取整
public static int hours(int[] piles, int speed) {
int ans = 0;
int offset = speed - 1;
for (int pile : piles) {
ans += (pile + offset) / speed;
}
return ans;
}
作者介绍
