网站建设实训内容,东莞seo排名优化服务,免费的代码分享网站,网站视频播放器用什么做的#x1f4d1;前言
本文主要是二分查找#xff08;进阶#xff09;的文章#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ #x1f3ac;作者简介#xff1a;大家好#xff0c;我是青衿#x1f947; ☁️博客首页#xff1a;CSDN主页放风讲故事 #x1f304;每日…前言
本文主要是二分查找进阶的文章如果有什么需要改进的地方还请大佬指出⛺️ 作者简介大家好我是青衿 ☁️博客首页CSDN主页放风讲故事 每日一句努力一点优秀一点 目录 文章目录 前言**目录**二分法1. 爱吃香蕉的珂珂2. 在 D 天内送达包裹的能力 文章末尾 二分法
二分法的特性 1题目满足单调性 2待求解的值是0到无限的一个值
1. 爱吃香蕉的珂珂
leetcode875 珂珂喜欢吃香蕉。这里有 n 堆香蕉第 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 104 piles.length h 109 1 piles[i] 109
思路 1.满足单调性待求解的值是1到1000000000的一个值 2.定义 target 是在一个在左闭右闭的区间里也就是[left, right] 3.终止条件为right left; 4.求最小速度即求左边界可以结合单调递减的图去写 本题注意点 1.因为取值左闭右边f(x)函数需要取long类型因为速度如果用1去计算取值int类型值会溢出 Java代码如下
class Solution {public int minEatingSpeed(int[] piles, int H) {int left 1;int right 1000000000;while (left right) {int mid left (right - left) / 2;//求最小速度即求左边界结合单调递减if (f(piles, mid) H) {right mid - 1;} else if(f(piles, mid) H) {right mid - 1;} else {left mid 1; }}return right 1;}// 定义速度为 x 时需要 f(x) 小时吃完所有香蕉// f(x) 随着 x 的增加单调递减long f(int[] piles, int x) {long hours 0;for (int i 0; i piles.length; i) {hours piles[i] / x;if (piles[i] % x 0) {hours;}}return hours;}
}2. 在 D 天内送达包裹的能力
leetcode1011
传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。 传送带上的第 i 个包裹的重量为 weights[i]。每一天我们都会按给出重量weights的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。 返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。 示例 1
输入weights [1,2,3,4,5,6,7,8,9,10], days 5 输出15 解释 船舶最低载重 15 就能够在 5 天内送达所有包裹如下所示 第 1 天1, 2, 3, 4, 5 第 2 天6, 7 第 3 天8 第 4 天9 第 5 天10
请注意货物必须按照给定的顺序装运因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 示例 2
输入weights [3,2,2,4,1,4], days 3 输出6 解释 船舶最低载重 6 就能够在 3 天内送达所有包裹如下所示 第 1 天3, 2 第 2 天2, 4 第 3 天1, 4 示例 3
输入weights [1,2,3,1,1], days 4 输出3 解释 第 1 天1 第 2 天2 第 3 天3 第 4 天1, 1 提示 1 days weights.length 5 * 104 1 weights[i] 500 思路 1与上一题类似都是求最小即左边界 本题注意点 1.如果left取最小值right取最大值会溢出
代码如下
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 (right - left) / 2 left; if(f(weights,mid) days) {right mid - 1;}else if(f(weights,mid) days) {right mid - 1;}else {left mid 1;}}return right 1;}//x为运载能力f(x)返回需要的天数,时间复杂度为o(n)//f(x)是单调递减的public int f(int[] weight,int x){int n weight.length;int sum 0;int k 0;int i 0;while(i n) {k x;while(i n k weight[i] ) {k k - weight[i]; i;}sum;}return sum;}}
文章末尾
