智能建站价格,电脑无法运行wordpress,营销网站的主题 定位 修改建议,江西省大余县建设局网站力扣labuladong一刷day24天 文章目录 力扣labuladong一刷day24天一、875. 爱吃香蕉的珂珂二、1011. 在 D 天内送达包裹的能力三、410. 分割数组的最大值 一、875. 爱吃香蕉的珂珂
题目链接#xff1a;https://leetcode.cn/problems/koko-eating-bananas/?utm_sourceLCUShttps://leetcode.cn/problems/koko-eating-bananas/?utm_sourceLCUSutm_mediumip_redirectutm_campaigntransfer2china 思路本质上是一个二分搜索左边界的问题每个小时吃多少都可以要找的是每小时吃k个h个小时正好吃完抽取出来计算用多少小时吃完的函数小时数超了应该扩大k小时数少了应该缩小k。
class Solution {public int minEatingSpeed(int[] piles, int h) {int left 1, right 1000000000;while (left right) {int mid left (right - left) / 2;if (f(mid, piles) h) {right mid - 1;}else {left mid 1;}}return left;}long f(int k, int[] piles) {long h 0;for (int i 0; i piles.length; i) {h piles[i] / k;if (piles[i] % k 0) {h;}}return h;}
}二、1011. 在 D 天内送达包裹的能力
题目链接https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/ 思路这题类似上一题有 一个容量K要求在day天运送完成所使用的最小k。在left和right的选取上要先设置好范围最小就是最小的包裹最大就是全体都能放下。计算天数时注意结尾的处理最后没装满或者装多了只要不是正好是0都要多加1天。
class Solution {public int shipWithinDays(int[] weights, int days) {int left 0;int right 1;for (int w : weights) {left Math.max(left, w);right w;}while (left right) {int mid left (right - left) / 2;if (f(weights, mid) days) {right mid - 1;}else {left mid 1;}}return left;}int f(int[] weights, int x) {int day 0, sum 0;for (int i 0; i weights.length; i) {if (sumweights[i] x) {day;sum 0;}else if (sum weights[i] x) {sum weights[i];}else {day;sum weights[i];}}return sum 0 ? day : day1;}
}三、410. 分割数组的最大值
题目链接https://leetcode.cn/problems/split-array-largest-sum/ 思路把数组顺序分成k个区间要求所有的分法当中各个和最大区间的 最小值。其实也就是有很多货物让k天运完求船的最小容量 一样是先确定left和right的边界边界里的数是船的容量不可能说船的容量装不下某一个货物故left应该是所有货物中的最大值。right的话看天数要求天数最少1天right最大为货物总和。 f(mid) 与 k如何调节其实直接分析就行怎么写都可以加入写成f(mid) k 那么说明船容量太大导致天数少了所以缩小容量天数就大了即right mid -1; else就是 f(mid) k 那么就是船的容量太小导致天数多了故扩大容量让天数变下left mid 1;
class Solution {public int splitArray(int[] nums, int k) {int left 0, right 0;for (int i : nums) {left Math.max(left, i);right i;}while (left right) {int mid left (right - left) / 2;if (f(nums, mid) k) {right mid - 1;}else {left mid 1;}}return left;}int f(int[] nums, int c) {int m 0, sum 0;for (int i 0; i nums.length; i) {if (sum nums[i] c) {m;sum 0;} else if (sum nums[i] c) {sum nums[i];}else {m;sum nums[i];}}return sum 0 ? m : m 1;}
}
