leetcode第875题爱吃香蕉的珂珂

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;
    }
}
上一篇:0970. Powerful Integers (M)


下一篇:[学习笔记]扩展Lucas定理