栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LeetCode——875.爱吃香蕉的珂珂

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode——875.爱吃香蕉的珂珂

通过万岁!!!

  • 题目:就是给你一个数组,然后让你找到一个数k,使得数组中每个数/k向上取整的值之和最小。
  • 思路:这里我的思路跟之前的双指针分巧克力是一样的,我们找到理论上的最小值,然后找到最大值,然后二分查找找到满足条件的最小的值即可。每次都去调用一个函数,判断当前的k(也就是代码中的mid),是不是满足全部吃完,如果满足,则说明k太大了,则右指针到mid,吃不完,则k太小了,则左指针右移。
  • 技巧:双指针进行二分查找。

java代码

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int len = piles.length;
        int max = -1;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, piles[i]);
        }
        if (h == len) {
            return max;
        }
        // k最小的值应该是数组中最大的值/h,这时候我们只考虑最大的。如果还有其他的,那么速度一定还需要再快,所以这是k的最小值。
        int l = max / h, r = max, mid;
        while (l <= r) {
            mid = l + (r - l) / 2;
            int t = isEatAll(piles, h, mid);
            if (t == -1) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }


    public int isEatAll(int[] piles, int h, int k) {
        int t = 0;
        for (int i = 0; i < piles.length; i++) {
            if (piles[i] <= k) {
                ++t;
            } else {
                t += Math.ceil(piles[i] * 1.0 / k);
            }
        }
        if (t <= h) {// 吃得完
            return -1;
        } else {// 吃不完
            return 1;
        }
    }
}
  • 总结:题目不是很难,但是我的效率并不高。
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/956882.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号