万年网站建设,网站初期缺点,wordpress appdev team,吉粤建设工程股份有限公司网站二分查找 爱吃香蕉的珂珂二分查找 上期经典 爱吃香蕉的珂珂 难度 - 中等 LC - 875.爱吃香蕉的珂珂 珂珂喜欢吃香蕉。这里有 n 堆香蕉#xff0c;第 i 堆中有 piles[i] 根香蕉。警卫已经离开了#xff0c;将在 h 小时后回来。 珂珂可以决定她吃香蕉的速度 k #xff08;单位第 i 堆中有 piles[i] 根香蕉。警卫已经离开了将在 h 小时后回来。 珂珂可以决定她吃香蕉的速度 k 单位根/小时。每个小时她将会选择一堆香蕉从中吃掉 k 根。如果这堆香蕉少于 k 根她将吃掉这堆的所有香蕉然后这一小时内不会再吃更多的香蕉。 珂珂喜欢慢慢吃但仍然想在警卫回来前吃掉所有的香蕉。 返回她可以在 h 小时内吃掉所有香蕉的最小速度 kk 为整数。 示例 1 输入piles [3,6,7,11], h 8 输出4 示例 2 输入piles [30,11,23,4,20], h 5 输出30 示例 3 输入piles [30,11,23,4,20], h 6 输出23 提示 1 piles.length 1E4 piles.length h 1E9 1 piles[i] 1E9 二分查找 由于存在「吃完这堆的所有香蕉然后这一小时内不会再吃更多的香蕉」的条件因此不会存在多堆香蕉共用一个小时的情况即每堆香蕉都是相互独立同时可以明确每堆香蕉的耗时为 ⌈piles[i]k⌉⌉其中 k 为速度。 因此我们可以二分 k 值在以 k 为分割点的数组上具有「二段性」 小于 k 的值总耗时 ans 必然不满足 ans≤h 大于等于 k 的值总耗时 ans 必然满足 ans≤h。 然后我们需要确定二分的范围每堆香蕉至少消耗一个小时因此大于 max(piles[i])的速度值 k 是没有意义的与 kmax(piles[i]) 等价因此我们可以先对 piles 进行一次遍历找最大值再二分也可以直接利用数据范围 1piles[i]1e9 确定一个粗略边界进行二分。 最后的 getTime函数只需要计算当前速率 k 所对应的总耗时 ans再与 h 做比较即可。 代码演示: public int minEatingSpeed(int[] piles, int h) {int left 1;int right 0;//找出最大一堆的个数 吃香蕉的速度最大就是这个,在大没有意义了for (int pile : piles) {right Math.max(right, pile);}while(left right){int mid left (right - left) / 2;long time getTime(piles,mid) ;if(time h){right mid;}else if(time h){left mid 1;}}return left;}/*** 计算用时* speed 吃香蕉的速度*/public long getTime(int[] piles, int speed) {long time 0;for (int pile : piles) {int curTime (pile speed - 1) / speed;time curTime;}return time;}
上期经典
LC34. 在排序数组中查找元素的第一个和最后一个位置
