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得多注意规避。
相关链接:
- C刷题:LeetCode 875. 爱吃香蕉的珂珂 (中等),link
- C刷题:二分查找原始版、查找左侧边界/右侧边界模板大总结 | 二分法,link
相关文章:
Python世界:力扣题解875,珂珂爱吃香蕉,中等
Python世界:力扣题解875,珂珂爱吃香蕉,中等 任务背景思路分析代码实现坑点排查测试套件本文小结 任务背景 问题来自力扣题目875 Koko Eating Bananas,大意如下: 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学习记录(六)配置文件参数化 一、参数提取到配置文件中二、yml配置文件三、ConfigurationProperties注解实现批量属性注入 一、参数提取到配置文件中 定义在代码中的参数的值分散在各个不同的文件中,不便于后期维护管理࿰…...

android 使用MediaPlayer实现音乐播放--获取音乐数据
前面已经添加了权限,有权限后可以去数据库读取音乐文件,一般可以获取全部音乐、专辑、歌手、流派等。 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语言中,测试是一个非常重要的部分,它帮助开发者确保代码的正确性、性能以及可维护性。Go语言提供了一套标准的测试工具,这些工具可以帮助开发者编写单元测试、表达式测试(通常也是指单元测试中的断言)、基准测试等…...

VB.Net笔记-更新ing
目录 1.1 设置默认VS的开发环境为VB.NET(2024/11/18) 1.2 新建一个“Hello,world”的窗体(2024/11/18) 1.3 计算圆面积的小程序(2024/11/18) 显示/隐式 声明 (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 中的变量与数据类型有哪些? A: Python 支持多种数据类型,包括数字(整数 int、浮点数 float、复数 complex)、字符串 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之后,一直在琢磨如何进一步感受它的优点,因为前面只是用了它的内核,感觉和FreeRTOS、uCOS等RTOS差别不大,至于它们性能、可靠性上的差异,在这种学习性的程序中,很难有所察觉。 RT-Threa…...
Kotlin中的?.和!!主要区别
目录 1、?.和!!介绍 2、使用场景和最佳实践 3、代码示例和解释 1、?.和!!介绍 Kotlin中的?.和!!主要区别在于它们对空指针的处理方式。 ?.(安全调用操作符):当变量可能为null时,使用?.可以安全地调用其方法或属性…...

iframe嵌入踩坑记录
iframe嵌入父子页面token问题 背景介绍 最近在做在平台A中嵌入平台B某个页面的需求,我负责的是平台B这边,使这个页面被嵌入后能正常使用。两个平台都实现了单点登录。 其实这是第二次做这个功能了,原本以为会很顺利,但没想到折腾…...
面试小札:Java的类加载过程和类加载机制。
Java类加载过程 加载(Loading) 这是类加载过程的第一个阶段。在这个阶段,Java虚拟机(JVM)主要完成三件事: 通过类的全限定名来获取定义此类的二进制字节流。这可以从多种来源获取,如本地文件系…...
Spring 上下文对象
1. Spring 上下文对象概述 Spring 上下文对象(ApplicationContext)是 Spring 框架的核心接口之一,它扩展了 BeanFactory 接口,提供了更多企业级应用所需的功能。ApplicationContext 不仅可以管理 Bean 的生命周期和配置࿰…...

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

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

【Vue】指令扩充(指令修饰符、样式绑定)
目录 指令修饰符 按键修饰符 事件修饰符 双向绑定指令修饰符 输入框 表单域 下拉框 单选按钮 复选框 样式绑定 分类 绑定class 绑定style tab页切换示例 指令修饰符 作用 借助指令修饰符,可以让指令的功能更强大 分类 按键修饰符:用来…...
Ubuntu20.04 Rk3588 交叉编译ffmpeg7.0
firefly 公司出的rk3588的设备,其中已经安装了gcc 交叉编译工具,系统版本是Ubuntu20.04。 使用Ubuntu20.04 交叉编译ffmpeg_ubuntu下配置ffmpeg交叉编译器为arm-linux-gnueabihf-gcc-CSDN博客文章浏览阅读541次。ubuntu20.04 交叉编译ffmpeg_ubuntu下配…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...

基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...

python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...

Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...