当前位置: 首页 > 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\…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...