闵行做网站公司青岛网站制作

任务背景

---

问题来自力扣题目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