fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
二分搜索怎么用？我又总结了套路 :: labuladong的算法小抄
Python Banana 啥也不说了， 谢labuladong
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def f(piles, x):
hours = 0
for i in range(len(piles)):
hours += piles[i] // x
if piles[i]%x>0:
hours += 1
return hours
left = 1
right = max(piles)
while left < right:
mid = (right+left) // 2
if f(piles, mid) <= h:
right = mid
else:
left = mid + 1
return right
为啥js代码这段没过提交，我寻思着和那段java代码不是一样的吗， 珂珂吃香蕉那个题目
var minEatingSpeed = function(piles, h) {
let left = 1
let right = 1000000000 + 1
while(left < right) {
let mid = Math.floor(left + (right - left) / 2)
console.log(left, right, f(piles, mid))
if(f(piles, mid) <= h) {
right = mid
} else {
left = mid + 1
}
}
return left
// 定义：速度为 x 时，需要 f(x) 小时吃完所有香蕉
// f(x) 随着 x 的增加单调递减
function f(piles, x) {
let hours = 0
for(let i = 0;i < piles.length;i++) {
hours += piles[i] / x
if(piles[i] % x > 0) {
hours++
}
}
return hours
}
};
- 爱吃香蕉的珂珂 js 版，我用的两端都封闭的二分搜索
/**
* @param {number[]} piles
* @param {number} h
* @return {number}
*/
var minEatingSpeed = function(piles, h) {
let left = 1;
let right = 1000000000;
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (f(piles, mid) === h) {
// 搜索左侧边界，则需要收缩右侧边界
right = mid - 1;
} else if (f(piles, mid) < h) {
// 需要让 f(x) 的返回值大一些
right = mid - 1;
} else if (f(piles, mid) > h) {
// 需要让 f(x) 的返回值小一些
left = mid + 1;
}
}
return left;
}
// 定义：速度为 x 时，需要 f(x) 小时吃完所有香蕉
// f(x) 随着 x 的增加单调递减
function f(piles, x) {
let hours = 0;
for (let i = 0; i < piles.length; i++) {
hours += Math.floor(piles[i] / x);
if (piles[i] % x > 0) {
hours++;
}
}
return hours;
}
爱吃香蕉的珂珂 python version
import math
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
# 问题转化，搜索区间是[1,max_piles]
# nums[mid]用于计算以当前的速度吃完香蕉的时间是多少小时
# 需要求满足条件的最小speed，实际上就是左边界问题，因为不同的速度消耗时间是相同的
def f(piles, speed):
hours = 0
for pile in piles:
hours += math.ceil(pile / speed)
return hours
left, right = 1, max(piles) + 1
while left < right:
speed = left + (right - left) // 2
hours = f(piles, speed)
if hours > h: # 要加快速度
left = speed + 1
elif hours < h:
right = speed
elif hours == h:
right = speed
return left
- 在D天内送达包裹的能力（中等）
# @lc code=start
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
def f(weights, capacity):
cur = 0
days = 0
for i, weight in enumerate(weights):
if cur + weight <= capacity:
cur += weight
else:
cur = weight
days += 1
return days + 1
# 至少有一天承载了一天最重的包裹，所以最小值是max(weights)
left, right = max(weights), sum(weights) + 1
while left < right:
capacity = left + (right - left) // 2
need_days = f(weights, capacity)
if need_days > days: # 增大容量
left = capacity + 1
elif need_days < days:
right = capacity
elif need_days == days:
right = capacity
return left
//java1011
class Solution {
public int shipWithinDays(int[] weights, int days) {
int left = 0, right = 0;
for(int weight : weights){
//最大运力保证刚好一次性运完所有包裹
right += weight;
//包裹不能拆开运所以至少保证载重能承载任意一个包裹；
left = Math.max(left, weight);
}
while(left < right){
int mid = left + (right - left) / 2;
if(weightSum(weights, mid) > days){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
public int weightSum(int[] weights, int speed){
int sum = 0;
int res = 0;
for(int weight : weights){
sum += weight;
if(sum > speed){
res += 1;
sum = weight;
}
}
//加上最后一个不超载无法触发sum > speed 要补1，如果超载则最后一个要单独运输一次还要补1；
return res + 1;
}
}
第三题有一点点区别，那个单调函数用了贪心的思想。
单调函数的入参是maxSum，返回值表示最少分割次数。
对于一个给定的最大和 maxSum，最少能分割 minSplitTimes 次，那么 minSplitTimes ≤ m说 明当前的maxSum满足要求，那么继续缩小 maxSum ，看看有没最佳（小）的值。
class Solution {
public int splitArray(int[] nums, int m) {
//分析:求的是分组的数,和如何分组才能让某一组的组内元素之和是固定分组情况下所有情况的sum=min的min是多少
//1.m分的越多:最大:每个元素为一组,那此时的maxSum就是nums中的最大元素的值
//2.m分得越少:最小:整个nums为一组,此时的maxSum就是nums中所有元素之和
//所以我们在研究分组的数量和最终的maxSum的关系
if(nums==null||nums.length==0) return 0;
int left=0;
int right=0;
for(int i=0;i<nums.length;i++){
left=Math.max(left,nums[i]);
right+=nums[i];
}
right++;//因为要左闭右开
while(left<right){
int mid=left+(right-left)/2;
if(f2(nums,mid)<m){
//分的组数太多了
right=mid;
}else if(f2(nums,mid)>m){
//组数分的太少了
left=mid+1;
}else{
//左边界
right=mid;
}
}
return left;
}
private int f2(int[] nums,int x){
//让f(x)返回值是分组数,x为定死的maxSum
int groups=1;
int sum=0;
for(int i=0;i<nums.length;i++){
if(sum+nums[i]<=x){
sum+=nums[i];
}else{
groups++;
sum=nums[i];
}
}
return groups;
}
}
东哥，有个问题实在想请教，楼上看了一圈没有发现和我有一样问题的，就吃香蕉那题，我之前用Python写的，二分用的是双闭区间没有任何问题。今天用Java刷的时候也是同样的逻辑，但是用双闭区间就出问题了。
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1;
int right = 1;
for (int pile : piles){
right = Math.max(right, pile);
}
while (left <= right){
int mid = left + (right - left) / 2;
// System.out.print(left + ", " + right + ", " + mid);
// System.out.print(", " + eatingTime(piles, mid) + ", ");
if (eatingTime(piles, mid) > h){left = mid + 1;}
else if (eatingTime(piles, mid) < h){right = mid - 1;}
else if (eatingTime(piles, mid) == h){right = mid - 1;}
// System.out.println(left + ", " + right + ", " + mid);
}
return left;
}
public int eatingTime(int[] piles, int k){
int hours = 0;
for (int i = 0; i < piles.length; i++){
hours += piles[i] / k;
if (piles[i] % k != 0){
hours ++;
}
}
return hours;
}
}
倒在了测试用例piles = [805306368,805306368,805306368], h = 1000000000 然后我debug的时候发现是我代码里eatingTime(piles, mid)的返回值居然出现了负数，我查了一下应该是int类型越界了，需要long类型。之前Python代码通过是因为python的int范围更大。 但是改成左闭右开区间之后就没有这个问题了，下面的代码正确通过了。我真的在想是否二分采用左闭右开可以非常有效的规避掉这些情况，双闭区间逻辑上也没有任何问题，但是遇到这种情况感觉非常难第一时间想到出bug的原因。
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1;
int right = 1;
for (int pile : piles){
right = Math.max(right, pile);
}
right ++;
while (left < right){
int mid = left + (right - left) / 2;
// System.out.print(left + ", " + right + ", " + mid);
System.out.print(", " + eatingTime(piles, mid) + ", ");
if (eatingTime(piles, mid) > h){left = mid + 1;}
else if (eatingTime(piles, mid) < h){right = mid;}
else if (eatingTime(piles, mid) == h){right = mid;}
// System.out.println(left + ", " + right + ", " + mid);
}
return left;
}
public int eatingTime(int[] piles, int k){
int hours = 0;
for (int i = 0; i < piles.length; i++){
hours += piles[i] / k;
if (piles[i] % k != 0){
hours ++;
}
}
return hours;
}
}
今天遇到了跟楼上一模一样的问题，Java双闭区间同样的写法几天前还能过今天就不行了，但右开区间没问题，想了很久没明白为什么，持续关注这个问题，希望有大神指教
@Burkhardttt @zhao-zihan 我也遇到了这个问题，不知道这样解释对不对，有点马后炮的感觉。也就是那个spendTime函数越界了，spendTime函数越界的原因是速度放的太慢了，导致时间拉的太长嘛。这就说明此时速度过于小了，也就是mid小了，那么下一次搜索的区间就是left = mid + 1。 也就是实际吃的时间不能<=0，小了的话要往大了放
while(left <= right){
int mid = left + (right - left) / 2;
int actualTime = spendTime(mid, piles);
if(actualTime > h){
//速度不够，h小时内吃不完
left = mid + 1;
}else if (actualTime < h && actualTime > 0){
//速度太快了，放慢一点
right = mid - 1;
}else if(actualTime == h){
//要找最小值，继续往左压缩
right = mid - 1;
}else if(actualTime <= 0){
left = mid + 1;
}
}
return left;
@Tallminsome 你把我代码copy过去你那跑跑应该就可以了，配合我注释掉的System.out打印的那些信息，在测试用例piles = [805306368,805306368,805306368], h = 1000000000的时候我的eatingTime最终返回了一个负值，Java出现负值就是表示越界了，这个测试用例产生的正数超过了Java int的范围。我这次长记性了，Java的int范围是真的小，以后见到这种数字很大的测试用例就知道肯定是越界了，然后就可以focus on问题的根源了。右开区间能过我感觉也算运气，因为所有的测试用例没有越界的，我觉得肯定有那么一些测试用例能让你怎么写都过不了，直接用long才行。
@YuanzuoZhang 看我的第二版代码，二分改成左闭右开区间就过了。 我没有硬着头皮接着双闭区间了，但是因为是java int越界导致的问题，我想着可以强制类型转换一下把int换成long应该可以解决，以后debug看到测试用例的数字很大的时候就要往int越界这方面想了，java的int确实范围小动不动就越界。
Java 双闭区间，倔强青铜改也不知道为啥改对了，应该是@Burkhardttt 说的int溢出:
The 'int' boundaries are -2147483648 to 2147483647. 最大的test case是piles = [805306368,805306368,805306368], h = 1000000000, 乍一看好像也没有超出范围，不过也只能是这个case运算之后超了int的上界，然后被JVM转成Integer.MIN_VALUE了
The results are specified by the language and independent of the JVM version: Integer.MAX_VALUE + 1 == Integer.MIN_VALUE and Integer.MIN_VALUE - 1 == Integer.MAX_VALUE. The same goes for the other integer types.
Reference
class Solution {
public int minEatingSpeed(int[] piles, int h) {
//as eating time monotonely decreases as eating speed increases
//need to get the min speed under constraint of h hours
//so search the left bound of eating speed(to get longer eating time)
// using long to prevent from exceeding
long left = 1;
long right = 1000000000;
while (left <= right) {
long mid = left + (right - left) / 2;
if (eatingTime(piles, mid) <= h) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return (int) left;
}
public long eatingTime(int[] piles, long speed) {
long time = 0;
for (long pile : piles) {
time += pile / speed;
if (pile % speed > 0) {
time++;
}
}
return time;
}
}
吃香蕉双闭区间c++解法
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
unsigned int lo = 1;
unsigned int hi = 1e9;
while(lo <= hi){
unsigned int mid = lo + (hi - lo) / 2;
unsigned int time = 0;
for(auto p:piles){
time += ceil(double(p)/double(mid));
}
if(time == h) hi = mid - 1;
if(time > h) lo = mid + 1;
if(time < h) hi = mid - 1;
}
return lo;
}
};
用unsigned int的原因也是因为int会导致越界，但是我认为强行套用双闭区间也不容易解释，因为这道题的case导致不需要检查返回的lo是否存在于整个[1, 1e9]区间的情况
class Solution {
public:
unsigned int f(vector<int>piles,int x){
unsigned int hours = 0;
for (unsigned int i = 0; i < piles.size(); i++) {
hours += piles[i] / x;
if (piles[i] % x > 0) {
hours++;
}
}
return hours;
}
int minEatingSpeed(vector<int>& piles, int h) {
unsigned int left = 1;//速率的边界，最小
unsigned int right = 1000000000 + 1;//速率的边界，最大
while (left <= right) {
unsigned int mid = left + (right - left) / 2;
if (f(piles, mid) <= h) {
right = mid-1;
} else {
left = mid + 1;
}
}
return left;
}
};
python split array
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
#二分搜索算法，x为最小子串和，f(x)为最小子串和对应的分段数，target为目标分段数
#找到目标分段数target下，最小的子串和
#即为找到target目标分段数区间的左端点
left = max(nums)
right = sum(nums) + 1
while left < right:
mid = (left + right)//2
segs = 0
load = 0
for num in nums:
if load + num < mid:
load += num
elif load + num == mid:
segs += 1
load = 0
else:
segs += 1
load = num
if load != 0:
segs += 1
if segs <= m:
right = mid
else:
left = mid + 1
return left
判断搜索方向的函数也可以简单return一个boolean，也减少了前面提到溢出的问题：
·class Solution {
public int minEatingSpeed(int[] piles, int h) {
int left = 1;
int right = 0;
for (int pile : piles) {
right = Math.max(right, pile);
}
int mid = 0;
while(left <= right) {
mid = left + (right - left)/2;
if (canFinish(piles, h, mid)) {
right = mid-1;
} else {
left = mid+1;
}
}
return left;
}
private boolean canFinish(int[] piles, int h, int speed) {
for (int pile : piles) {
h = h - (pile/speed) - (pile%speed > 0 ? 1 : 0);
if (h < 0) {
return false;
}
}
return true;
}
}·
