当前位置: 首页 > news >正文

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 堆香蕉&#xff0c;第 i 堆中有 piles[i] 根香蕉。警卫已经离开了&#xff0c;将在 h 小时后回来。 珂珂可以决定她吃香蕉的速度 k &#xff08;单位&…...

LeetCode-406-根据身高重建队列

题目描述&#xff1a; 假设有打乱顺序的一群人站成一个队列&#xff0c;数组 people 表示队列中一些人的属性&#xff08;不一定按顺序&#xff09;。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi &#xff0c;前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造…...

JVM——类加载与字节码技术—编译期处理+类加载阶段

3.编译期处理 编译期优化称为语法糖 3.1 默认构造器 3.2 自动拆装箱 java基本类型和包装类型之间的自动转换。 3.3泛型集合取值 在字节码中可以看见&#xff0c;泛型擦除就是字节码中的执行代码不区分是String还是Integer了&#xff0c;统一用Object. 对于取出的Object&…...

C#|如何调试进依赖动态库中

第一步&#xff1a;打开项目属性 第二步 打开debug的本地调试可用 第三步 把要调试的代码拖进主界面打断点就可以进断点了...

全新版本QStack云管系统3.5.3 附详细安装教程

源码介绍&#xff1a; QStack云管系统3.5.3&#xff0c;全新版本下载安装包详细搭建教程。 涵盖了服务器、云主机、代理IP等多种云产品管理运维和安全存储。 同时&#xff0c;QStack还支持对接运营众多公有云厂商产品资源&#xff0c;满足不同用户的需求。 通过开放API和插…...

SLB 负载均衡

优质博文&#xff1a;IT-BLOG-CN 一、简介 SLB (Server Loader Balancer&#xff09;将访问流量根据转发策略分发到后台多台服务器的流量分发控制服务&#xff0c;来实现多台服务器提供相同的业务服务。负载均衡扩展了应用的服务能力&#xff0c;增强了应用的可用性。主要用于…...

多核调度预备知识

进程调度的本质 任务/进程切换 即&#xff1a;上下文切换&#xff0c;内核对处理器上执行的进程进行切换“上下文” 指&#xff1a;寄存器的值“上下文切换”指&#xff1a; 将寄存器的值保存到内存中(进程被剥夺处理器&#xff0c;停止执行)将另一组寄存器的值从内存中加载到…...

什么是Git?解释Git的分布式版本控制系统的优势?

1、什么是Git&#xff1f;解释Git的分布式版本控制系统的优势&#xff1f; Git是一个开源的分布式版本控制系统&#xff0c;用于跟踪和管理代码库的版本历史。它允许用户在本地计算机上跟踪和管理代码库的更改&#xff0c;并与其他人协作开发项目。Git的分布式特性意味着它不需…...

软考高级系统架构设计师系列论文九十五:图书馆网络应用体系安全设计

软考高级系统架构设计师系列论文九十五:图书馆网络应用体系安全设计 一、网络应用体系安全设计相关知识点二、摘要三、正文四、总结一、网络应用体系安全设计相关知识点 软考高级系统架构设计师:计算机网络...

qt 实现音视频的分贝检测系统

项目场景&#xff1a; 目前的产品经常播放m3u8流&#xff0c;有的视频声音正常&#xff0c;有的视频声音就偏低&#xff0c;即使放到最大音量声音也是比较小&#xff0c;所以就产生了某种需求&#xff0c;能否自动感知视频声音的大小&#xff0c;如果发现声音比较小的情况&…...

SSM框架和Spring Boot+Mybatis框架的性能比较?

SSM框架和Spring BootMybatis框架的性能比较&#xff0c;没有一个绝对的答案&#xff0c;因为它们的性能受到很多因素的影响&#xff0c;例如项目的规模、复杂度、需求、技术栈、团队水平、测试环境、测试方法等。因此&#xff0c;我们不能简单地说哪个框架的性能更好&#xff…...

6个月的测试,来面试居然要18K,我一问连8K都不值

2023年7月份我入职了深圳某家创业公司&#xff0c;刚入职还是很兴奋的&#xff0c;到公司一看我傻了&#xff0c;公司除了我一个自动化测试&#xff0c;公司的测试人员就只有2个开发3个前端1个测试还有2个UI&#xff0c;在粗略了解公司的业务后才发现是一个从零开始的项目&…...

优美而高效:解决服务器通信问题

题目背景 在这个问题中&#xff0c;我们面临着一幅服务器分布图。图中的每个单元格可能有服务器&#xff08;标记为1&#xff09;或者没有&#xff08;标记为0&#xff09;。我们的任务是找出能够与至少一台其他服务器进行通信的服务器数量。 算法思路 为了解决这个问题&…...

C++模板的模板参数(五)

1.模板的模板参数 在C中&#xff0c;模板的模板参数&#xff08;Template Template Parameters&#xff09;是一种特殊的模板参数&#xff0c;允许我们将另一个模板作为模板参数传递给一个模板。这种技术可以用于实现更灵活和通用的模板设计。 模板的模板参数使用两个 “temp…...

基于jeecg-boot的flowable流程加签功能实现

更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a; https://gitee.com/nbacheng/nbcio-boot 前端代码&#xff1a;https://gitee.com/nbacheng/nbcio-vue.git 在线演示&#xff08;包括H5&#xff09; &#xff1a; http://122.227.135.243:9888 今天我…...

day-03 基于TCP的服务器端/客户端

一.理解TCP和UDP TCP&#xff08;Transmission Control Protocol&#xff09;和UDP&#xff08;User Datagram Protocol&#xff09;是两种常见的传输层协议&#xff0c;用于在计算机网络中提供可靠的数据传输。 1.TCP&#xff1a; 连接导向&#xff1a;TCP是一种面向连接的…...

匿名对象和一般对象的区别

1.格式的不同 一般对象的格式&#xff1a; ​ Object obj new Object(); ​ 匿名对象的格式&#xff1a; ​ new Object(); 2.作为参数传递机制的不同 2.1先看看一般对象的使用机制 执行步骤&#xff1a; 1.首先程序进入main()函数&#xff0c;执行Object obj&#xff0c;…...

[MyBatis系列⑥]注解开发

&#x1f343;作者简介&#xff1a;准大三本科网络工程专业在读&#xff0c;持续学习Java&#xff0c;努力输出优质文章 ⭐MyBatis系列①&#xff1a;增删改查 ⭐MyBatis系列②&#xff1a;两种Dao开发方式 ⭐MyBatis系列③&#xff1a;动态SQL ⭐MyBatis系列④&#xff1a;核心…...

[ACL2023] Exploring Lottery Prompts for Pre-trained Language Models

Exploring Lottery Prompts for Pre-trained Language Models 文章链接 清深的工作&#xff0c;比较有意思的一篇。作者先给出假设&#xff0c;对于分类问题&#xff0c;在有限的语料空间内总能找到一个prompt让这个问题分类正确&#xff0c;作者称之为lottery prompt。为此&…...

【Python编程】将同一种图片分类到同一文件夹下,并且将其分类的路径信息写成txt文件进行保存

注&#xff1a;数据结构同上一篇博文类似 一、代码 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\…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...