《力扣面试150题》题单拓展——二分法

发布时间 2023-11-29 16:42:33作者: 小柴cyl

《力扣面试150题》题单拓展——二分法

困难题:找第K大/小

1. 基础知识

首先可以确定答案的上下界

单调性分析:如果当前答案为m时,可以满足,一定有一侧是一定满足的,另一侧不一定,需要去探索

bool is_ok(){
    
}

int l, r;
int ans;
while(l <= r){
    int m = l+((r-l)>>1);
    if(is_ok()){
        ans = m;
        r = m-1;		//根据情况而定
    }
    else
        l = m+1;
}
return ans;

2. is_ok()

我认为对于不同的题,整体主函数都是一样的,唯一的难点就是怎么去更好更快的判断出当前答案m是否满足要求,定制此函数才是最难的

875.爱吃香蕉的珂珂

判断在m速度下,吃完所有香蕉需要的时间是否小于期限h小时

a/b 向上取整:(a+b-1)/b


1283.使结果不超过阈值的最小除数