leetcode第875题爱吃香蕉的珂珂
看了一早晨的帖子,简单的总结一下吧!别真就给忘了
二分的框架主要就是有三种,第一种找目标值,第二种找左值,第三种,找右值,每个都有自己的代码框架,但是也都是大同小异
二分 | right = nums.length | right = nums.length - 1 |
---|---|---|
找左值 | 左闭右开 收紧右侧边界已锁定左侧边界,等于的时候 right = mid | 左闭右闭,收紧右侧边界已锁定左侧边界,等于的时候 right = mid - 1 |
找右值 | 左闭右开,收紧做边界找右值,等于的时候 left = mid + 1,返回值为left - 1,但是其实无所谓的,因为循环跳出的条件就是 left = right | 左闭右闭,收紧左侧边界锁定右侧边界,left = mid + 1; |
class Solution {
public int minEatingSpeed(int[] piles, int h) {
//可以根据二分的代码框架进行一个考量
// 这里就是二分框架的调用了,我感觉经过今天一早晨的学习,二分的代码还算是比较熟悉的
int left = 1;//吃香蕉的速度至少应该为1啊!为0的话永远都吃不完了
int right = 1000000000 + 1;//题目说最大值为10的9次,但是因为是左闭右开,所以加1
while(left < right){
int mid = left + (right - left) / 2;
if (f(piles,mid) == h){
//找左值,锁右边界,限制左值
right = mid;
/得出来的函数值,其实是一个单调递减的函数,所以就和平常单调递增的函数不太一样了
} else if(f(piles, mid) > h){
left = mid + 1;
}else if (f(piles,mid) < h){
right = mid;
}
}
return left;
}
/**
* 速度为x时,需要fx个小时吃完所有的香蕉
* @param piles
* @param x 自变量,要求的最小速度
* @return 返回值肯定就是多少个小时
*/
public int f(int[] piles,int x) {
int hour = 0;
for (int i = 0; i < piles.length; i++) {
hour += piles[i] / x;
if (piles[i] % x != 0) {
hour++;
}
}
return hour;
}
}