mzoe666888

V1

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

leetcode

二、分析

题目求的是最小速度吃香蕉,猩猩能懒则懒,只要保证在警卫回来前吃完就行

贪图的不是吃的有多快,贪图的是在规定时间内以最小速度吃完即可

最小速度怎么求? 先搞定速度怎么求?

先找出每堆香蕉中的最多的香蕉数(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

这猩猩太聪明了,既能慢慢悠悠的吃,又能吃完所有香蕉,真是聪明绝顶!

3AA5C3B0.gif
3AA5C3B0.gif

三、实现

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;
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1