我的LeetCode 875. Koko Eating Bananas解决方案出错,求排查
问题核心错误
你的代码在计算吃完所有香蕉所需时间的逻辑上完全错误:
- 题目规则是每小时只能吃同一堆的香蕉,哪怕这堆剩下的不足k根,也得用一整个小时吃完,不能跨堆合并计算总香蕉数再除以k。
- 你当前的
canEatPiles方法是把所有香蕉总和除以k后取整,这种计算方式完全忽略了“每堆单独耗时”的要求,导致二分查找的判断逻辑全部失效。
举个例子,输入piles = [3,6,7,11], h = 8:
- 正确耗时计算:每堆分别算,
ceil(3/4)=1、ceil(6/4)=2、ceil(7/4)=2、ceil(11/4)=3,总和为8小时,刚好符合要求。 - 你的代码计算:总和27除以4取整为7小时,比实际需要的时间少,会让二分逻辑错误地认为更小的k也可行,最终得到错误结果。
修正后的代码
import java.util.Arrays; class Solution { public int maxValueOf(int[] piles) { return Arrays.stream(piles).max().getAsInt(); } public int canEatPiles(int capacityPerHour, int[] piles) { int hours = 0; for (int pile : piles) { // 用整数运算等价实现ceil(pile / capacityPerHour),避免浮点精度问题 hours += (pile + capacityPerHour - 1) / capacityPerHour; } return hours; } public int minEatingSpeed(int[] piles, int h) { int l = 1; int r = maxValueOf(piles); int result = r; // 初始化为最大可能的速度 while (l <= r) { int mid = l + (r - l) / 2; // 避免l+r溢出 int requiredHours = canEatPiles(mid, piles); if (requiredHours <= h) { // 当前速度可行,尝试寻找更小的速度 result = mid; r = mid - 1; } else { // 当前速度太慢,需要加快 l = mid + 1; } } return result; } }
额外优化点说明
- 时间计算优化:用
(pile + capacityPerHour - 1) / capacityPerHour替代Math.ceil,避免浮点数运算的精度损耗,同时提升计算效率。 - 二分边界修正:新增
result变量记录可行的最小k值,避免原代码中循环结束后mid可能不是最优解的问题(循环结束时l > r,此时mid不一定是最后一个可行值)。 - 溢出防护:计算
mid时用l + (r - l)/2代替(l + r)/2,防止当l和r数值过大时出现整数溢出。
内容的提问来源于stack exchange,提问作者Abhinand G
相关产品推荐
相关产品推荐

