leetcode875. 爱吃香蕉的珂珂(java)
二分查找
- 爱吃香蕉的珂珂
- 二分查找
- 上期经典
爱吃香蕉的珂珂
难度 - 中等
LC - 875.爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 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 <= piles.length <= 1E4
piles.length <= h <= 1E9
1 <= piles[i] <= 1E9

二分查找
由于存在「吃完这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉」的条件,因此不会存在多堆香蕉共用一个小时的情况,即每堆香蕉都是相互独立,同时可以明确每堆香蕉的耗时为 ⌈piles[i]k⌉⌉(其中 k 为速度)。
因此我们可以二分 k 值,在以 k 为分割点的数组上具有「二段性」:
小于 k 的值,总耗时 ans 必然不满足 ans≤h;
大于等于 k 的值,总耗时 ans 必然满足 ans≤h。
然后我们需要确定二分的范围,每堆香蕉至少消耗一个小时,因此大于 max(piles[i])的速度值 k 是没有意义的(与 k=max(piles[i]) 等价),因此我们可以先对 piles 进行一次遍历,找最大值,再二分;也可以直接利用数据范围 1<=piles[i]<=1e9
确定一个粗略边界进行二分。
最后的 getTime函数,只需要计算当前速率 k 所对应的总耗时 ans,再与 h 做比较即可。
代码演示:
public int minEatingSpeed(int[] piles, int h) {int left = 1;int right = 0;//找出最大一堆的个数 吃香蕉的速度最大就是这个,在大没有意义了for (int pile : piles) {right = Math.max(right, pile);}while(left < right){int mid = left + (right - left) / 2;long time = getTime(piles,mid) ;if(time <= h){right = mid;}else if(time > h){left = mid + 1;}}return left;}/*** 计算用时* speed 吃香蕉的速度*/public long getTime(int[] piles, int speed) {long time = 0;for (int pile : piles) {int curTime = (pile + speed - 1) / speed;time += curTime;}return time;}
上期经典
LC34. 在排序数组中查找元素的第一个和最后一个位置
相关文章:
leetcode875. 爱吃香蕉的珂珂(java)
二分查找 爱吃香蕉的珂珂二分查找 上期经典 爱吃香蕉的珂珂 难度 - 中等 LC - 875.爱吃香蕉的珂珂 珂珂喜欢吃香蕉。这里有 n 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 h 小时后回来。 珂珂可以决定她吃香蕉的速度 k (单位&…...
LeetCode-406-根据身高重建队列
题目描述: 假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造…...
JVM——类加载与字节码技术—编译期处理+类加载阶段
3.编译期处理 编译期优化称为语法糖 3.1 默认构造器 3.2 自动拆装箱 java基本类型和包装类型之间的自动转换。 3.3泛型集合取值 在字节码中可以看见,泛型擦除就是字节码中的执行代码不区分是String还是Integer了,统一用Object. 对于取出的Object&…...
C#|如何调试进依赖动态库中
第一步:打开项目属性 第二步 打开debug的本地调试可用 第三步 把要调试的代码拖进主界面打断点就可以进断点了...
全新版本QStack云管系统3.5.3 附详细安装教程
源码介绍: QStack云管系统3.5.3,全新版本下载安装包详细搭建教程。 涵盖了服务器、云主机、代理IP等多种云产品管理运维和安全存储。 同时,QStack还支持对接运营众多公有云厂商产品资源,满足不同用户的需求。 通过开放API和插…...
SLB 负载均衡
优质博文:IT-BLOG-CN 一、简介 SLB (Server Loader Balancer)将访问流量根据转发策略分发到后台多台服务器的流量分发控制服务,来实现多台服务器提供相同的业务服务。负载均衡扩展了应用的服务能力,增强了应用的可用性。主要用于…...
多核调度预备知识
进程调度的本质 任务/进程切换 即:上下文切换,内核对处理器上执行的进程进行切换“上下文” 指:寄存器的值“上下文切换”指: 将寄存器的值保存到内存中(进程被剥夺处理器,停止执行)将另一组寄存器的值从内存中加载到…...
什么是Git?解释Git的分布式版本控制系统的优势?
1、什么是Git?解释Git的分布式版本控制系统的优势? Git是一个开源的分布式版本控制系统,用于跟踪和管理代码库的版本历史。它允许用户在本地计算机上跟踪和管理代码库的更改,并与其他人协作开发项目。Git的分布式特性意味着它不需…...
软考高级系统架构设计师系列论文九十五:图书馆网络应用体系安全设计
软考高级系统架构设计师系列论文九十五:图书馆网络应用体系安全设计 一、网络应用体系安全设计相关知识点二、摘要三、正文四、总结一、网络应用体系安全设计相关知识点 软考高级系统架构设计师:计算机网络...
qt 实现音视频的分贝检测系统
项目场景: 目前的产品经常播放m3u8流,有的视频声音正常,有的视频声音就偏低,即使放到最大音量声音也是比较小,所以就产生了某种需求,能否自动感知视频声音的大小,如果发现声音比较小的情况&…...
SSM框架和Spring Boot+Mybatis框架的性能比较?
SSM框架和Spring BootMybatis框架的性能比较,没有一个绝对的答案,因为它们的性能受到很多因素的影响,例如项目的规模、复杂度、需求、技术栈、团队水平、测试环境、测试方法等。因此,我们不能简单地说哪个框架的性能更好ÿ…...
6个月的测试,来面试居然要18K,我一问连8K都不值
2023年7月份我入职了深圳某家创业公司,刚入职还是很兴奋的,到公司一看我傻了,公司除了我一个自动化测试,公司的测试人员就只有2个开发3个前端1个测试还有2个UI,在粗略了解公司的业务后才发现是一个从零开始的项目&…...
优美而高效:解决服务器通信问题
题目背景 在这个问题中,我们面临着一幅服务器分布图。图中的每个单元格可能有服务器(标记为1)或者没有(标记为0)。我们的任务是找出能够与至少一台其他服务器进行通信的服务器数量。 算法思路 为了解决这个问题&…...
C++模板的模板参数(五)
1.模板的模板参数 在C中,模板的模板参数(Template Template Parameters)是一种特殊的模板参数,允许我们将另一个模板作为模板参数传递给一个模板。这种技术可以用于实现更灵活和通用的模板设计。 模板的模板参数使用两个 “temp…...
基于jeecg-boot的flowable流程加签功能实现
更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码: https://gitee.com/nbacheng/nbcio-boot 前端代码:https://gitee.com/nbacheng/nbcio-vue.git 在线演示(包括H5) : http://122.227.135.243:9888 今天我…...
day-03 基于TCP的服务器端/客户端
一.理解TCP和UDP TCP(Transmission Control Protocol)和UDP(User Datagram Protocol)是两种常见的传输层协议,用于在计算机网络中提供可靠的数据传输。 1.TCP: 连接导向:TCP是一种面向连接的…...
匿名对象和一般对象的区别
1.格式的不同 一般对象的格式: Object obj new Object(); 匿名对象的格式: new Object(); 2.作为参数传递机制的不同 2.1先看看一般对象的使用机制 执行步骤: 1.首先程序进入main()函数,执行Object obj,…...
[MyBatis系列⑥]注解开发
🍃作者简介:准大三本科网络工程专业在读,持续学习Java,努力输出优质文章 ⭐MyBatis系列①:增删改查 ⭐MyBatis系列②:两种Dao开发方式 ⭐MyBatis系列③:动态SQL ⭐MyBatis系列④:核心…...
[ACL2023] Exploring Lottery Prompts for Pre-trained Language Models
Exploring Lottery Prompts for Pre-trained Language Models 文章链接 清深的工作,比较有意思的一篇。作者先给出假设,对于分类问题,在有限的语料空间内总能找到一个prompt让这个问题分类正确,作者称之为lottery prompt。为此&…...
【Python编程】将同一种图片分类到同一文件夹下,并且将其分类的路径信息写成txt文件进行保存
注:数据结构同上一篇博文类似 一、代码 import os import cv2 import shutilpath0os.getcwd()\\apple\\RGB path1os.getcwd()\\apple\\tof_confidence # path2os.getcwd()\\apple\\tof_depth # path3os.getcwd()\\apple\\tof_depthRGB # path4os.getcwd()\\apple\…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
