LeetCode、875. 爱吃香蕉的珂珂【中等,最小速度二分】

这篇具有很好参考价值的文章主要介绍了LeetCode、875. 爱吃香蕉的珂珂【中等,最小速度二分】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。

涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。

博主所有博客文件目录索引:博客目录索引(持续更新)

视频平台:b站-Coder长路


LeetCode、875. 爱吃香蕉的珂珂【中等,最小速度二分】

来源:LeetCode专题《LeetCode 75》

题目及分类

题目链接:LeetCode、875. 爱吃香蕉的珂珂

类型:基础算法/二分


思路分析及代码实现

思路:

本题说让我们找到一个最少的每小时吃的香蕉数可以正好在有限时间内吃完,可以看到给我们的用例中数据量特别大,我们不可能将所有的每小时速度都去尝试模拟跑一遍,那么绝对会超时,我们选择好相应的左、右边界,然后来进行尝试二分处理。

LeetCode、875. 爱吃香蕉的珂珂【中等,最小速度二分】,# LeetCode,算法刷题,leetcode,算法,职场和发展

代码:

复杂度分析:时间复杂度O(n);空间复杂度O(1)

class Solution {

    //对吃的最小速度进行二分
    //1000个位置 每个位置上限为亿
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1, r = 1000000010;
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(mid, piles, h)) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    //check可以吃完,可以吃完返回true
    public boolean check (int k, int[] piles, int h) {
        int hh = 0;
        for (int i = 0; i < piles.length; i ++) {
            int curPile = piles[i];
            if (k >= curPile) hh ++;
            else hh += (int)Math.ceil(1.0 * curPile / k); //对于curPile / k可能会得到double类型,那么我们这里就需要提前*1.0让其变成浮点数
            if (hh > h) return false;
        }
        // if (k == 3) System.out.println(hh);
        return h >= hh ? true : false;
    }
}

LeetCode、875. 爱吃香蕉的珂珂【中等,最小速度二分】,# LeetCode,算法刷题,leetcode,算法,职场和发展

代码优化

尝试优化,缩小左右边界:

①优化1:计算总和及某个元素最大值

long sum = 0;
int max = piles[0];
for (int pile: piles) {
    sum += pile;
    max = Math.max(max, pile);
}
//设置边界值
int l = (int)(sum / h), r = max;

LeetCode、875. 爱吃香蕉的珂珂【中等,最小速度二分】,# LeetCode,算法刷题,leetcode,算法,职场和发展

原因:因为我们只是取所有数组中最大的那个元素,那么一旦我们数组中某个元素特别大,那么就会导致我们预想的直接失效。

②优化2:适当缩减右边界,提升效率

class Solution {

    //对吃的最小速度进行二分
    //1000个位置 每个位置上限为亿
    public int minEatingSpeed(int[] piles, int h) {
        int n = piles.length;
        long sum = 0;
        for (int pile: piles) {
            sum += pile;
        }
        //设置边界值  对于r尽可能相对大一些(我们将小时数尽量减小,这样就可以相对拉大速度,扩展右边界)
        int l = (int)(sum / h), r = (int)(sum / (h - n + 1) + 1);
        // System.out.printf("l=%d, r=%d\n", l, r);
        //进行二分
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(mid, piles, h)) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    //check可以吃完,可以吃完返回true
    public boolean check (int k, int[] piles, int h) {
        int hh = 0;
        for (int i = 0; i < piles.length; i ++) {
            int curPile = piles[i];
            if (k >= curPile) hh ++;
            else hh += (int)Math.ceil(1.0 * curPile / k); //对于curPile / k可能会得到double类型,那么我们这里就需要提前*1.0让其变成浮点数
            if (hh > h) return false;
        }
        // if (k == 3) System.out.println(hh);
        return h >= hh ? true : false;
    }
}

LeetCode、875. 爱吃香蕉的珂珂【中等,最小速度二分】,# LeetCode,算法刷题,leetcode,算法,职场和发展


资料获取

大家点赞、收藏、关注、评论啦~

精彩专栏推荐订阅:在下方专栏👇🏻

  • 长路-文章目录汇总(算法、后端Java、前端、运维技术导航):博主所有博客导航索引汇总
  • 开源项目Studio-Vue—校园工作室管理系统(含前后台,SpringBoot+Vue):博主个人独立项目,包含详细部署上线视频,已开源
  • 学习与生活-专栏:可以了解博主的学习历程
  • 算法专栏:算法收录

更多博客与资料可查看👇🏻获取联系方式👇🏻,🍅文末获取开发资源及更多资源博客获取🍅


整理者:长路 整理时间:2024.1.22文章来源地址https://www.toymoban.com/news/detail-822016.html

到了这里,关于LeetCode、875. 爱吃香蕉的珂珂【中等,最小速度二分】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 1347. 制造字母异位词的最小步骤数 (中等,Counter)

    闲来无事,今天多做一题 条件很宽,可以任意替换,且排列相同也可以 所以只要统计每个字母在 s 中比在 t 中多出现的次数之和即可 学习 python 求字符的 ASCII码 需要使用内置函数 ord() python 有一个collections.Counter模块,它可以直接统计一个字符串中字符出现的次数,且它返回

    2024年02月07日
    浏览(43)
  • 【LeetCode-中等题】78. 子集

    1、子集去重版本 2、组合非去重版本 3、组合去重版本 注意:这里的nums数组里面的元素是各不相同的,所以不存在去重操作 参考讲解视频:回溯算法解决子集问题,树上节点都是目标集和! | LeetCode:78.子集 根据nums[1,2,3] 可以画出树图,收获的结果集为所有节点,并且根据

    2024年02月09日
    浏览(28)
  • Leetcode—22.括号生成【中等】

    之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

    2024年01月23日
    浏览(74)
  • 【图论】Leetcode 200. 岛屿数量【中等】

    给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例 1: 输入:grid = [ [“1”,“1”,“1”,“

    2024年04月15日
    浏览(43)
  • 【LeetCode-中等题】79. 单词搜索

    需要一个标记数组 来标志格子字符是否被使用过了 先找到word 的第一个字符在表格中的位置,再开始递归 递归的结束条件是如果word递归到了最后一个字符了,说明能在矩阵中找到单词 剪枝条件 就是如果已经找到单词了 res = true 了 后面就不需要递归了,还有如果下标越界、

    2024年02月09日
    浏览(37)
  • 【LeetCode-中等题】189. 轮转数组

    思路:通过,开辟数组 取模运算寻找新位置------ 位置(i+k)mod n =新位置 思路: 1、先全部翻转 2、在根据k 的值 对k-1 的两边区域进行翻转 3、注意 k如果 数组长度 就会出现下标越界,所以需要开始就k对数组长度取模 k %=n

    2024年02月11日
    浏览(31)
  • 【LeetCode-中等题】46. 全排列

    1、子集去重版本 2、组合去重版本 3、子集非去重版本 这题中nums中的数各不相同,所以不需要去重: 而下面这题,nums中的数会存在重复值,就需要去重: 参考讲解视频:代码随想录—全排列不去重版本 关键在于递归之后还要还原做回溯动作: 所以最后,我们统计到的res才

    2024年02月09日
    浏览(48)
  • 【LeetCode-中等题】73. 矩阵置零

    参考链接:614,矩阵置零 先设置两个boolean 变量来判断第一行第一列临时数组是否存在0,存在0,说明第一列或第一行要全体置0 先遍历矩阵,将出现0的位置的第一行第一列置为0,后续可以根据第一行或列是否为0,来将对应的行或列全体置为0 根据第一行第一列的置0行列,来

    2024年02月09日
    浏览(34)
  • 【贪心算法】Leetcode 55. 跳跃游戏【中等】

    给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1: 输入 :nums = [2,3,1,1,4] 输出: true 解释 :可以先跳 1 步,从下标

    2024年04月28日
    浏览(50)
  • 【图论】Leetcode 994. 腐烂的橘子【中等】

    在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一: 值 0 代表空单元格; 值 1 代表新鲜橘子; 值 2 代表腐烂的橘子。 每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,

    2024年04月15日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包