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

Python世界:力扣题解875,珂珂爱吃香蕉,中等

Python世界:力扣题解875,珂珂爱吃香蕉,中等

    • 任务背景
    • 思路分析
    • 代码实现
    • 坑点排查
    • 测试套件
    • 本文小结

任务背景


问题来自力扣题目875 Koko Eating Bananas,大意如下:

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

翻译下,需求是:对给定无序数组表示N堆香蕉,找到最小吃香蕉的速度k,且在h小时内吃完。

思路分析


初步分析,该题可以转化为二分法查找左边界问题,需要思考的是找到上下范围和比较条件。

最小速度,若取数组中的最小值去吃,作为最慢速度吃,假如时间足够长,可能还不够慢。故:最小吃的速度设为1,但不一定能h内吃完。

最大速度,可取数组中的最大值,则数组的长度即为耗时,而已知条件数组的长度len<=h。

最小速度能保证吃完,但耗时最大,最大速度能一定吃完,耗时最小。目标是找到h小时内吃完的最小速度,即不断向左偏移满足条件的边界。

初步思路:

  • 确定速度k的上下限
  • 找满足条件的左边界(右侧满足概率较大),第一个满足条件的左值
  • 比较条件为:吃完所耗时间<=目标时间

代码实现


import math as mtclass Solution(object):def minEatingSpeed(self, piles, h):""":type piles: List[int]:type h: int:rtype: int"""def consumed_hours(piles, k):hours = 0for val in piles:if val <= k:hours += 1# print(hours)else:# hours += int(mt.ceil(val / k))val_mod = 0if (val % k != 0):val_mod = 1hours += (val // k) + val_mod# print(hours)return hours# range: [low, high)low = 1high = max(piles) + 1while (low < high):mid = low + (high - low) // 2hours = consumed_hours(piles, mid)# print(mid, hours, h)if (hours <= h):high = mid# print(high)else:low = mid + 1return max(high, 1)

坑点排查


代码实现很快,也都本地通过了用例。以上代码中问题行18已注释。

但出现一个神奇的现象是,本地通过,但提交线上通不过,实在奇怪。

问题解决

通过添加打印定位到hours += int(mt.ceil(val / k)),本地和线上计算结果不一致。

将此行代码修改如下,即可通过:

val_mod = 0
if (val % k != 0):val_mod = 1
hours += (val // k) + val_mod

根因分析

踩坑不可怕,可怕的是不知道为何有坑,否则下次还会踏入同样的河流。

同样的代码,本地python跑ok,一上去跑,输出结果就不同。这么一个神奇的问题怎能轻易放过?

仔细分析代码:hours += int(mt.ceil(val / k)) ,查看是线上线下val/k结果存储不一致。

  • 线下版本,val/k,两整数相除不尽,保存为浮点结果。故符合预期,通过用例。
  • 线上版本,val/k,两整数相除不尽,截断保存为整数。不符合预期,用例失败。

再进一步分析,两者之间的python版本差异查看:

import sys
print(sys.version)

通过以上代码可得:

  • 线下版本,3.7.7 (tags/v3.7.7:d7c567b08f, Mar 10 2020, 10:41:24) [MSC v.1900 64 bit (AMD64)]
  • 线上版本,2.7.18 (default, Oct 15 2023, 16:43:11) ,[GCC 11.4.0]

可初步判断为线上版本python2.x较老,整数相除模拟的是C实现,而线下版本python3.x较新,整数相除不尽结果是浮点。

测试套件


测试套demo:

import unittestdef test_base(self, piles, h, ret):sol = Solution()res = sol.minEatingSpeed(piles, h)self.assertEqual(res, ret)# 编写测试套
class TestSol(unittest.TestCase):def test_special1(self):ret = 4piles = [5,4,3,2,1]h = 6test_base(self, piles, h, ret)def test_special2(self):ret = 4piles = [1,2,3,4,5]h = 6test_base(self, piles, h, ret)def test_common1(self):ret = 23piles = [30,11,23,4,20]h = 6test_base(self, piles, h, ret)def test_common2(self):ret = 30piles = [30,11,23,4,20]h = 5test_base(self, piles, h, ret)def test_common3(self):ret = 4piles = [3,6,7,11]h = 8test_base(self, piles, h, ret)# 测试套版本主调
if __name__ == '__main__':print('start!')unittest.main() # 启动单元测试print('done!')

本文小结


二分法到好写,主要坑点在于排查相同代码,结果线上线下val/k运行结果有差异的问题,写python得多注意规避。

相关链接:

  1. C刷题:LeetCode 875. 爱吃香蕉的珂珂 (中等),link
  2. C刷题:二分查找原始版、查找左侧边界/右侧边界模板大总结 | 二分法,link

相关文章:

Python世界:力扣题解875,珂珂爱吃香蕉,中等

Python世界&#xff1a;力扣题解875&#xff0c;珂珂爱吃香蕉&#xff0c;中等 任务背景思路分析代码实现坑点排查测试套件本文小结 任务背景 问题来自力扣题目875 Koko Eating Bananas&#xff0c;大意如下&#xff1a; Koko loves to eat bananas. There are n piles of bana…...

Java设计模式 —— Java七大设计原则详解

文章目录 前言一、单一职责原则1、概述2、案例演示 二、接口隔离原则1、概述2、案例演示 三、依赖倒转原则1、概述2、案例演示 四、里氏替换原则1、概述2、案例演示 五、开闭原则1、概述2、案例演示 六、迪米特法则1、概述2、案例演示 七、合成/聚合复用原则1、概述2、组合3、聚…...

SpringBoot学习记录(六)配置文件参数化

SpringBoot学习记录&#xff08;六&#xff09;配置文件参数化 一、参数提取到配置文件中二、yml配置文件三、ConfigurationProperties注解实现批量属性注入 一、参数提取到配置文件中 定义在代码中的参数的值分散在各个不同的文件中&#xff0c;不便于后期维护管理&#xff0…...

android 使用MediaPlayer实现音乐播放--获取音乐数据

前面已经添加了权限&#xff0c;有权限后可以去数据库读取音乐文件&#xff0c;一般可以获取全部音乐、专辑、歌手、流派等。 1. 获取全部音乐数据 class MusicHelper {companion object {SuppressLint("Range")fun getMusic(context: Context): MutableList<Mu…...

.net 8使用hangfire实现库存同步任务

C# 使用HangFire 第一章:.net Framework 4.6 WebAPI 使用Hangfire 第二章:net 8使用hangfire实现库存同步任务 文章目录 C# 使用HangFire前言项目源码一、项目架构二、项目服务介绍HangFire服务结构解析HangfireCollectionExtensions 类ModelHangfireSettingsHttpAuthInfoUs…...

第 22 章 - Go语言 测试与基准测试

在Go语言中&#xff0c;测试是一个非常重要的部分&#xff0c;它帮助开发者确保代码的正确性、性能以及可维护性。Go语言提供了一套标准的测试工具&#xff0c;这些工具可以帮助开发者编写单元测试、表达式测试&#xff08;通常也是指单元测试中的断言&#xff09;、基准测试等…...

VB.Net笔记-更新ing

目录 1.1 设置默认VS的开发环境为VB.NET&#xff08;2024/11/18&#xff09; 1.2 新建一个“Hello&#xff0c;world”的窗体&#xff08;2024/11/18&#xff09; 1.3 计算圆面积的小程序&#xff08;2024/11/18&#xff09; 显示/隐式 声明 &#xff08;2024/11/18&…...

centos 服务器 docker 使用代理

宿主机使用代理 在宿主机的全局配置文件中添加代理信息 vim /etc/profile export http_proxyhttp://127.0.0.1:7897 export https_proxyhttp://127.0.0.1:7897 export no_proxy"localhost,127.0.0.1,::1,172.171.0.0" docker 命令使用代理 例如我想在使用使用 do…...

python语言基础

1. 基础语法 Q: Python 中的变量与数据类型有哪些&#xff1f; A: Python 支持多种数据类型&#xff0c;包括数字&#xff08;整数 int、浮点数 float、复数 complex&#xff09;、字符串 str、列表 list、元组 tuple、字典 dict 和集合 set。每种数据类型都有其特定的用途和…...

Python中的Apriori库详解

文章目录 Python中的Apriori库详解一、引言二、Apriori算法原理与Python实现1、Apriori算法原理2、Python实现1.1、数据准备1.2、转换数据1.3、计算频繁项集1.4、提取关联规则 三、案例分析1、导入必要的库2、准备数据集3、数据预处理4、应用Apriori算法5、生成关联规则6、打印…...

MongoDB比较查询操作符中英对照表及实例详解

mongodb比较查询操作符中英表格一览表 NameDescription功能$eqMatches values that are equal to a specified value.匹配值等于指定值。$gtMatches values that are greater than a specified value.匹配值大于指定值。$gteMatches values that are greater than or equal to…...

掌上单片机实验室 – RT-Thread + ROS2 初探(25)

在初步尝试RT-Thread之后&#xff0c;一直在琢磨如何进一步感受它的优点&#xff0c;因为前面只是用了它的内核&#xff0c;感觉和FreeRTOS、uCOS等RTOS差别不大&#xff0c;至于它们性能、可靠性上的差异&#xff0c;在这种学习性的程序中&#xff0c;很难有所察觉。 RT-Threa…...

‌Kotlin中的?.和!!主要区别

目录 1、?.和!!介绍 2、使用场景和最佳实践 3、代码示例和解释 1、?.和!!介绍 ‌Kotlin中的?.和!!主要区别在于它们对空指针的处理方式。‌ ‌?.&#xff08;安全调用操作符&#xff09;‌&#xff1a;当变量可能为null时&#xff0c;使用?.可以安全地调用其方法或属性…...

iframe嵌入踩坑记录

iframe嵌入父子页面token问题 背景介绍 最近在做在平台A中嵌入平台B某个页面的需求&#xff0c;我负责的是平台B这边&#xff0c;使这个页面被嵌入后能正常使用。两个平台都实现了单点登录。 其实这是第二次做这个功能了&#xff0c;原本以为会很顺利&#xff0c;但没想到折腾…...

面试小札:Java的类加载过程和类加载机制。

Java类加载过程 加载&#xff08;Loading&#xff09; 这是类加载过程的第一个阶段。在这个阶段&#xff0c;Java虚拟机&#xff08;JVM&#xff09;主要完成三件事&#xff1a; 通过类的全限定名来获取定义此类的二进制字节流。这可以从多种来源获取&#xff0c;如本地文件系…...

Spring 上下文对象

1. Spring 上下文对象概述 Spring 上下文对象&#xff08;ApplicationContext&#xff09;是 Spring 框架的核心接口之一&#xff0c;它扩展了 BeanFactory 接口&#xff0c;提供了更多企业级应用所需的功能。ApplicationContext 不仅可以管理 Bean 的生命周期和配置&#xff0…...

Wireshark抓取HTTPS流量技巧

一、工具准备 首先安装wireshark工具&#xff0c;官方链接&#xff1a;Wireshark Go Deep 二、环境变量配置 TLS 加密的核心是会话密钥。这些密钥由客户端和服务器协商生成&#xff0c;用于对通信流量进行对称加密。如果能通过 SSL/TLS 日志文件&#xff08;例如包含密钥的…...

测试人员--如何区分前端BUG和后端BUG

在软件测试中&#xff0c;发现一个BUG并不算难&#xff0c;但准确定位它的来源却常常让测试人员头疼。是前端页面的问题&#xff1f;还是后台服务的异常&#xff1f;如果搞错了方向&#xff0c;开发人员之间的沟通效率会大大降低&#xff0c;甚至导致问题久拖不决。 那么&#…...

【Vue】指令扩充(指令修饰符、样式绑定)

目录 指令修饰符 按键修饰符 事件修饰符 双向绑定指令修饰符 输入框 表单域 下拉框 单选按钮 复选框 样式绑定 分类 绑定class 绑定style tab页切换示例 指令修饰符 作用 借助指令修饰符&#xff0c;可以让指令的功能更强大 分类 按键修饰符&#xff1a;用来…...

Ubuntu20.04 Rk3588 交叉编译ffmpeg7.0

firefly 公司出的rk3588的设备&#xff0c;其中已经安装了gcc 交叉编译工具&#xff0c;系统版本是Ubuntu20.04。 使用Ubuntu20.04 交叉编译ffmpeg_ubuntu下配置ffmpeg交叉编译器为arm-linux-gnueabihf-gcc-CSDN博客文章浏览阅读541次。ubuntu20.04 交叉编译ffmpeg_ubuntu下配…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Nginx server_name 配置说明

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

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...