力扣labuladong——一刷day26

力扣labuladong——一刷day26"/>

力扣labuladong——一刷day26

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 前言
• 一、力扣875. 爱吃香蕉的珂珂
• 二、力扣1011. 在 D 天内送达包裹的能力
• 三、力扣410. 分割数组的最大值

二分搜索的泛化问题
首先从问题中抽象出自变量X，就是题目要求取的最值
其次，抽象出映射函数F(X)，捋清对应关系，使其单调
最后，计算F(X) == target，返回X

前言

一、力扣875. 爱吃香蕉的珂珂

class Solution {public int minEatingSpeed(int[] piles, int h) {int left = 1, right = 1000000000;while(left <= right){int mid = left + (right-left)/2;if(fun(mid,piles) == h){right = mid - 1;}else if(fun(mid,piles) > h){left = mid + 1;}else{right = mid - 1;}}return left;}public long fun(int k, int[] piles){long hour = 0;for(int i = 0; i < piles.length; i ++){hour += piles[i]/k;if(piles[i]%k > 0){hour ++;}}return hour;}
}

二、力扣1011. 在 D 天内送达包裹的能力

class Solution {public int shipWithinDays(int[] weights, int days) {int left = 0, right = 0;for(int i = 0; i < weights.length; i ++){left = Math.max(left,weights[i]);right += weights[i];}while(left <= right){int mid = left + (right - left)/2;if(fun(mid, weights) == days){right = mid - 1;}else if(fun(mid, weights) > days){left = mid + 1;}else{right = mid - 1;}}return left;}public int fun(int k, int[] weights){int day = 0;for(int i = 0; i < weights.length;){int cap = k;while(i < weights.length){if(cap < weights[i])break;else cap -= weights[i++];}day ++;}return day;}
}

三、力扣410. 分割数组的最大值

class Solution {public int splitArray(int[] nums, int k) {int left = 0, right = 0;for(int i = 0; i < nums.length;i++){left = Math.max(left,nums[i]);right += nums[i];}while(left <= right){int mid = left + (right - left)/2;if(fun(mid, nums) == k){right = mid - 1;}else if(fun(mid, nums) > k){left = mid + 1;}else{right = mid - 1;}}return left;}public int fun(int x, int[] nums){int m = 0;for(int i = 0; i < nums.length;){int cap = x;while(i < nums.length){if(cap < nums[i])break;else cap -= nums[i];i ++;}m ++;}return m;}
}