网站导航固定代码,中国建设银行网站首页怎么销户,做互联网小程序 和网站有没有前景,抚州做网站公司目录 前言
二分求最小值
1283. 使结果不超过阈值的最小除数
2187. 完成旅途的最少时间
1011. 在 D 天内送达包裹的能力
875. 爱吃香蕉的珂珂
3296. 移山所需的最少秒数
475. 供暖器
2594. 修车的最少时间
1482. 制作 m 束花所需的最少天数
3048. 标记所有下标的最早秒…目录 前言
二分求最小值
1283. 使结果不超过阈值的最小除数
2187. 完成旅途的最少时间
1011. 在 D 天内送达包裹的能力
875. 爱吃香蕉的珂珂
3296. 移山所需的最少秒数
475. 供暖器
2594. 修车的最少时间
1482. 制作 m 束花所需的最少天数
3048. 标记所有下标的最早秒数 I
求最小值拓展浮点型
1870. 准时到达的列车最小时速
3453. 分割正方形 I
二分求最大值
275. H 指数 II
2226. 每个小孩最多能分到多少糖果
2982. 找出出现至少三次的最长特殊子字符串 II
2576. 求出最多标记下标
1898. 可移除字符的最大数目
1802. 有界数组中指定下标处的最大值
1642. 可以到达的最远建筑
2861. 最大合金数
总结 前言
二分答案与二分查找【算法深练】二分查找从O(n)到O(log n)以对数级效率秒杀海量数据的解题利刃-CSDN博客有异曲同工之妙与二分查找不同的是二分答案需要自己编写check函数来判断是否成立。二分答案在我们解题中是比较常用的如果一个题目无从下手可以先思考如果在已知答案的情况下对答案进行判断是否更简单如果更简单就可以考虑使用二分来AC。
PS本篇博客中的所有题目均来自于灵茶山艾府 - 力扣LeetCode分享的题单。
二分求最小值
1283. 使结果不超过阈值的最小除数 题解找到一个不大于threshold的整数找到数组中除以该整数后仍然小于thorshold的最小除数。根据nums.lengththreshold如果除数是最大值结果就是nums.length满足条件所以区间就在(0,max(nums)]中对该区间中的所有数进行枚举找到满足条件的最小值时间复杂度是O(N^2)太慢了。当除数变大的时候结果就在减小那不就是单调的吗能使用二分来解决将左右边界分别设置为0和max(nums)进行二分找到满足条件的最小值。细节向上取整a/b就是(ab-1)/b向下取整。 class Solution {//计算如果除数是x结果时多少int div(vectorint nums,int x){int ret0;for(auto e:nums) ret(ex-1)/x;return ret;}
public:int smallestDivisor(vectorint nums, int threshold) {int nnums.size(); //以数组小标表示除数随着下标增大结果也在减小所以可以使用二分int left0,rightranges::max(nums); //使用左开右开的形式 nthreshold所以最大值是除数为nums[n-1]时结果是nwhile(left1right){int midleft(right-left)/2;if(div(nums,mid)threshold) rightmid; //满足条件else leftmid; //不满足条件}return right;}
};
2187. 完成旅途的最少时间 题解与类似当时间在增大时旅途趟数也在增加是递增的可以使用二分进行查找。左右边界怎么进行设置呢右边界可以设置为min(time)*totalTrips表示最快的车独自完成的时间左边界可以直接设置为0也可以设置为min(time)。 class Solution {//时间time内完成的旅途数目long long numsTime(vectorint nums,long long time){long long ret0;for(auto e:nums) rettime/e;return ret;}public:long long minimumTime(vectorint time, int totalTrips) {//以时间作为二分时间越长可以完成的旅途越多是单调的//最长时间可以设置为min(time)*totalTrips即花费最短时间的车辆独自完成时间long long left0,right(long long)ranges::min(time)*totalTrips;while(left1right){long long midleft(right-left)/2;if(numsTime(time,mid)totalTrips) rightmid;else leftmid;}return right;}
};
1011. 在 D 天内送达包裹的能力 题解当运输能力上升时所需要的时间就在减小所以满足递减可以使用二分。在下边界世界设置为0即可上边界设置为全部包裹是max(weight)的情况下需要的载重能力即max(weight)*((n-1)/days1)其中((n-1)/days1)表示一天至多运输货物的数量上边界也可以使用所有货物的总重量表示一天就装完所需的载重能力。 class Solution {//计算运载能力为x时需要的时间long long time(vectorint nums,long long x){long long tmp0,ret0;for(auto e:nums){if(ex) return -1;tmpe;if(tmpx){ret;tmptmpx?0:e;}}if(tmp) ret;return ret;}public:int shipWithinDays(vectorint weights, int days) {//船运载能力越强所需的时间就越短是单调递减的可以使用二分来解决int nweights.size();//右边界设置为如果货物全是weight的最大值当时间为days时需要的运载能力//(n-1)/days1表示包裹数量除以天数向上取整即一天至多需要运输多少个包裹long long left0,rightranges::max(weights)*((n-1)/days1);while(left1right){long long midleft(right-left)/2;int needtime(weights,mid);if(need0needdays) rightmid;else leftmid;}return right;}
};
875. 爱吃香蕉的珂珂 题解速度越快需要的时间就越小单调递减可以使用二分查找下边界可以使用0表示上边界使用piles的和表示。 class Solution {long long hours(vectorint nums,long long v){long long ret0;for(auto e:nums)ret(e-1)/v1;return ret;}public:int minEatingSpeed(vectorint piles, int h) {//速度越大所需要的时间越短单调递减的可以使用二分解决//细节她将吃掉这堆的所有香蕉然后这一小时内不会再吃更多的香蕉。 说明需要进行向上取整int npiles.size();//下边界用0来表示上边界可以用所有的香蕉个数表示long long left0,rightaccumulate(piles.begin(),piles.end(),0LL);while(left1right){long long midleft(right-left)/2;if(hours(piles,mid)h) rightmid;else leftmid;}return right;}
};
3296. 移山所需的最少秒数 题解当花费的时间越多时高度降低的就越多所以可以使用二分来找最小值。下边界可以使用0上边界可以用最快的工人一个人移山所需要的时间。 计算一个工人在t时间内可以降低的高度 class Solution {//计算所有工人在t内降低的高度long long totalHeight(vectorint nums,long long t){long long ret0;for(auto e:nums) retheight(e,t);return ret;}//计算工人在时间t内降低的高度long long height(int worktime,long long t){long long kt/worktime;long long len(-1sqrt(18*k))/2;return len;}public:long long minNumberOfSeconds(int mountainHeight, vectorint workerTimes) {//当时间越多降低的高度越长可以使用二分解决long long left0,right0;long long heig0,mintimeranges::min(workerTimes),each0;//确定上边界rightwhile(heigmountainHeight){eachmintime;righteach;heig;}while(left1right){long long midleft(right-left)/2;if(totalHeight(workerTimes,mid)mountainHeight) rightmid;else leftmid;}return right;}
};
475. 供暖器 题解当半径越大时越满足条件房屋只存在能供暖和不能供暖两种情况所以可以使用二分进行查找对于二分判断是否满足条件不需要考虑太多直接将设置的x带入题目进行检验即可。 class Solution {//检查当前x时候满足条件bool check(vectorint houses,vectorint heaters,int x){int nhouses.size(),mheaters.size();int j0;for(int i0;in;i){if(houses[i]heaters[j]-xhouses[i]heaters[j]x) continue;while(jmhouses[i]heaters[j]x) j;if(jm||houses[i]heaters[j]-x) return false;}return true;}public:int findRadius(vectorint houses, vectorint heaters) {//先对两个数组进行排序sort(houses.begin(),houses.end());sort(heaters.begin(),heaters.end());int left-1,right1000000000; //设置上下边界while(left1right){int midleft(right-left)/2;if(check(houses,heaters,mid)) rightmid;else leftmid;}return right;}
};
2594. 修车的最少时间 题解与上一题类似依旧是使用二分来解决。先确定上下边界下边界直接设为0上边界可以使用最快修理工独自完成所需要的时间。 class Solution {long long check(vectorint ranks,long long t){long long ret0; //统计修理好的车辆for(auto r:ranks) retsqrt(t/r); return ret;}public:long long repairCars(vectorint ranks, int cars) {//确定上下边界long long left0,right0;long long r_minranges::min(ranks);rightr_min*cars*cars;while(left1right){long long midleft(right-left)/2;if(check(ranks,mid)cars) rightmid;else leftmid;}return right;}
};
1482. 制作 m 束花所需的最少天数 题解二分分组循环对时间进行二分下边界使用0上边界可以使用bloomDay中的最大值使用check来判断时间t是否满足条件。 class Solution {//检查在t时刻是否满足条件bool check(vectorint nums,int m,int k,int t){int i0,nnums.size();while(in){while(innums[i]t) i;int starti;while(i-start!kinnums[i]t) i;if(ini-startk) m--;if(m0) return true;}return false;}public:int minDays(vectorint bloomDay, int m, int k) {int nbloomDay.size();if((long long)k*mn) return -1; //数量不够直接返回int left0,rightranges::max(bloomDay); //取上下边界while(left1right){int midleft(right-left)/2;if(check(bloomDay,m,k,mid)) rightmid;else leftmid;}return right;}
};
3048. 标记所有下标的最早秒数 I 题解此题难度较大直接计算时间比较难但是如果已知答案确定答案是否正确就比较简单就是二分。标记所有的下标时间越多越有可能进行标记所以可以根据时间进行二分。 题意转换此题可以理解为有n1场考试[1,n]我们需要对考试进行准备每一场考试需要准备的时间是确定的考试可以有多场根据上面转换后的题意如果考试越靠后就有更多的时间进行准备那就可以只准备每门考试的最后一场即可。
代码细节统计每门考试的最后一场时间当时间到最后一场时必须进行考试看前面可以准备的时间够不够即可。
class Solution {//检查时间为t时是否满足条件bool check(vectorint nums,vectorint changeIndices,int t){int nnums.size();vectorint last_n(n,-1);for(int i0;it;i)last_n[changeIndices[i]-1]i; //存储各个科目最后一次考试时间if(ranges::find(last_n,-1)!last_n.end()) return false; //存在没有考试时间的科目int have0;//i表示时间,changeIndices[i]-1是第几门科目,nums[changeIndices[i]-1]是该门复习需要的时间for(int i0;it;i){if(ilast_n[changeIndices[i]-1]){if(havenums[changeIndices[i]-1]) return false;else have-nums[changeIndices[i]-1];}else have;}return true; }public:int earliestSecondToMarkIndices(vectorint nums, vectorint changeIndices) {int nnums.size(),mchangeIndices.size();if(nm) return -1;int leftn-1,rightm1; //不能确定时间为m时是否满足条件但是m1是一定不满足条件的所以将right置为m1while(left1right){int midleft(right-left)/2;if(check(nums,changeIndices,mid)) rightmid;else leftmid;}return rightm?-1:right;}
};
求最小值拓展浮点型
1870. 准时到达的列车最小时速 题解依旧是二分但是此题需要特别注意的是小数的处理方式以及左右边界的处理细节。细节列车都是整点运行的所以除了最后一辆列车其他的列车运行时间都要进行向上取整。 class Solution {//检查是否满足条件//因为车都是在整数时间发车的所以要进行向上取整bool check(vectorint dist,double hour,int v){int ndist.size();double total0;for(int i0;in-1;i)total(dist[i]-1)/v1;totaldist[n-1]/(double)v;return totalhour;}public:int minSpeedOnTime(vectorint dist, double hour) {//当速度越大时多需要的时间也短可以使用二分的方式来求最小速率int ndist.size();if(n-1hour) return -1; //车次-1时因为最后一次算的是小数而并不需要取整long long left0,rightranges::max(dist); //right用dist中的最大值替代这样每辆车都只需要行驶一个小时double pointhour-(int)hour; //如果最后一次出现小数时就需要对最后一次车速进行判断来确定right是否需要扩大if(point!0dist[n-1]/pointright) rightdist[n-1]/point1;while(left1right){int midleft(right-left)/2;if(check(dist,hour,mid)) rightmid;else leftmid;}return right;}
};
3453. 分割正方形 I 题解易得y一定是存在的所以此题的难点在于如何确定循环条件。此题以y作为二分基准当下方面积更大没有找到准确位置或者上下面积差在题目范围内找到了满足条件的位置但是可能不是最小y 时将rightmid否则将leftmid 循环条件应该如何进行设置 class Solution {//判断以t为分界线是否满足条件bool check(vectorvectorint squares,double t){double down0,up0;for(auto nums:squares){double xnums[0],ynums[1],lennums[2];if(ylent)up len*min(ylen-t,len); //注意此处不能直接将len*(y-len-t)其中间可能有空隙if(yt)down len*min(t-y,len);}return updown||abs(up-down)1e-5; //当下面面积大时right就需要下移当满足条件时right也下移找最小值}public:double separateSquares(vectorvectorint squares) {double left0,right0;for(auto nums: squares)if(nums[1]nums[2]right) rightnums[1]nums[2];for(int i0;i48;i) //通过计算可以设置循环次数来对数据进行精确{double midleft(right-left)/2.0;if(check(squares,mid)) rightmid;else leftmid;}return right;}
};
上面通过计算直接确定了循环的次数但是如果仍然像之前一样写也是可以的
for(int i0;i48;i)可以写成while(left1e-5right)此写法仍然控制了区间长度不超过1e-5. 但是此处不建议用while本题能够过是因为left和right的值较小当left值很大的时候left1e-5的结果可能不再是我们预期的结果此处与浮点数的存储有关下面进行简单解释 存储浮点数的时候会先将浮点数转换为(1.xxxxxxxxxx)*(10^m)的形式在64位下只有52个比特位来存储小数点后面的数据所以浮点数实际上是不连续的也就是说1.0的下一个浮点数是12^(-52)当这个数越大的时候其下一个浮点数也就越大所以当left很大时left1e-5还是left就会进入死循环。 拓展此题如果数据范围较小的话也可以将所有的整数都提升10^5来将浮点数二分转化为整数二分。 二分求最大值
求最大值和求最小值的方法是类似的只不过判断条件不一样。
275. H 指数 II 题解数组是单调递增的当h越大的时候需要的优质论文的个数就越多所以可以使用二分来找到满足条件的h。假设论文被引用的次数h的个数是i当ih时说明满足条件但是不一定是最大的一个让leftmid当ih时说明right太大了所以将right进行缩小right-mid即可。 class Solution {//h表示论文被应用的次数bool check(vectorint nums,int h) {int nnums.size();int posranges::lower_bound(nums,h)-nums.begin();//判断是否有h个值满足条件return n-posh;}public:int hIndex(vectorint citations) {//数据是有序的可以通过二分来进行查找int ncitations.size();int left0,rightcitations[n-1]1;while(left1right){int midleft(right-left)/2;if(check(citations,mid)) leftmid;else rightmid;}return left;}
};
2226. 每个小孩最多能分到多少糖果 题解当直接求答案比较难的时候可以考虑用验证法在已知答案的情况下对答案的正确性进行验证就是二分。使用二分先确定一个分到的糖果数再检验该答案是否正确即可。 class Solution {//能否每人分到x个糖果bool check(vectorint nums,long long x,long long k){long long count0; //记录能有多少人分到x个糖果for(auto e:nums) counte/x;return countk;}public:int maximumCandies(vectorint candies, long long k) {//直接进行求比较难但是如果已知答案判断答案是否正确就比较简单了//已知答案就需要考虑二分long long left0,rightranges::max(candies)1;while(left1right){long long midleft(right-left)/2;if(check(candies,mid,k)) leftmid;else rightmid;}return left;}
};
2982. 找出出现至少三次的最长特殊子字符串 II 当出现了相同子字符串时第一时间想到的是滑动窗口。用滑动窗口求出每一个相同子串每个相同字符串又可以进行分割出更多的子字符串将这些字符串进行统计找出出现三次以上的最长子串。看起来好像可以 class Solution {
public:int maximumLength(string s) {//使用一次滑动窗口unordered_mapstring ,int m;int ns.size();int i0;while(in){int starti;while(ins[start]s[i]) i;//此时相同字符串的长度为i-startint leni-start;string str(s.begin()start,s.begin()i);for(int klen;k0;k--)m[str.substr(0,k)]len-k1; //进行统计}//所有相同的字符串都存储到m中了找长度最长的并且有3个int ret-1;for(auto [str,k]:m){if(k3) retmax(ret,(int)str.size());}return ret;}
};
以上对思路进行实现但是没有过是的。因为当相同字符串很长时就会导致map中存储了大量字符串导致最后内存超出限制。
所以需要对代码进行优化每次统计的时候都是直接把所有的子字符串都统计进去能不能进行一点裁剪可以。对for循环进行修改for(int klen;klen-2k0;k--)只需要统计最长的三个即可因为如果一个相同字符串长度为len则其满足条件的长度至少为len-2。
class Solution {
public:int maximumLength(string s) {//使用一次滑动窗口unordered_mapstring ,int m;int ns.size();int i0;while(in){int starti;while(ins[start]s[i]) i;//此时相同字符串的长度为i-startint leni-start;string str(s.begin()start,s.begin()i);for(int klen;klen-2k0;k--)m[str.substr(0,k)]len-k1; //进行统计}//所有相同的字符串都存储到m中了找长度最长的并且有3个int ret-1;for(auto [str,k]:m){if(k3) retmax(ret,(int)str.size());}return ret;}
};
方法二分组循环二分
统计每个独立的相同字符子串的长度。
如果字符x的最长字符串为L1则其可以形成满足条件的最长子串为L1-2
如果字符x的次长字符串为L2则其可以形成满足条件的最长子串为
当L1L2最长子串是L1-1
当L1 L2最长子串是L2
汇总就是min(L1-1L2)。
如果字符x的第三长字符串为L3则其可以形成满足条件的最长子串为L3
第四长就不需要考虑了考虑第三长是因为如果三个子字符串的长度相等长度就是L3。
class Solution {
public:int maximumLength(string s) {unordered_mapchar ,vectorint m;int i0,ns.size();while(in){int starti;while(ins[i]s[start]) i;m[s[start]].push_back(i-start);}int ret0;for(auto [ch,nums]:m ){sort(nums.begin(),nums.end(),greater());nums.push_back(0); //向后面补上两个数据是的数组长度永远大于等于3nums.push_back(0);retmax({nums[2],min(nums[1],nums[0]-1),nums[0]-2,ret});}return ret0?-1:ret;}
};
2576. 求出最多标记下标 题解排序同向双指针。返回值最大就是数组长度这种情况就是数组一分为二数据前半部分与后半部分一一对应所以可以先对数组进行排序使用一个指针指向数组中间位置一个指向数组尾部判断中间位置数据的两倍是否大于尾部数据如果大于是一组否则说明中间数据太大了向前走找更小的数据。 class Solution {
public:int maxNumOfMarkedIndices(vectorint nums) {//先对数组进行排序再使用同向双指针int nnums.size();sort(nums.begin(),nums.end());int ln/2-1,rn-1,ret0;while(l0rn/2){if(2*nums[l]nums[r]){r--;ret;}l--;}return ret*2;}
};
1898. 可移除字符的最大数目 题解模拟二分。如果直接进行挨个删除效率太低可以同个二分进行优化。先确定给删除的个数再验证p是不是s的子序列即可。 class Solution {bool check(string s,string p,vectorint removable,int x){for(int i0;ix;i) s[removable[i]]0; //对被删除的位置进行修改int ns.size(),mp.size();int j0;for(int i0;injm;i)if(s[i]p[j]) j;return jm;}public:int maximumRemovals(string s, string p, vectorint removable) {//如果一个个的进行移除效率太低了//可以使用二分进行优化int nremovable.size();int left0,rightn1;while(left1right){int midleft(right-left)/2;if(check(s,p,removable,mid)) leftmid;else rightmid;}return left;}
};
1802. 有界数组中指定下标处的最大值 题解当直接进行求解比较难得时候考虑在已知答案得情况下能否进行验证。此题如果直接进行求解比较复杂如果已知index位置得最大数取判断数组总和是否不超过maxSum就很简单求和时需要用到数列求和的公式。 class Solution {bool check(int n,int index,long long maxSum,long long t){long long lindex,rn-index-1;long long all0;if(tl) allt*(t-1)/2-(t-l-1)*(t-l)/2;else allt*(t-1)/2l-t1;if(tr) allt*(t-1)/2-(t-r-1)*(t-r)/2;else allt*(t-1)/2r-t1;return alltmaxSum;}public:int maxValue(int n, int index, int maxSum) {//直接进行模拟难度太大如果已知最大值进行验证就比较简单了int left0,rightmaxSum1;while(left1right){int midleft(right-left)/2;if(check(n,index,maxSum,mid)) leftmid;else rightmid;}return left;}
};
1642. 可以到达的最远建筑 题解在已知到达的高度的情况下判断砖和梯子是否够即可细节为了找到最优解梯子应该使用在需要砖块最多的位置所以可以使用一个小堆找出使用最多的梯子。 class Solution {
public:int furthestBuilding(vectorint heights, int bricks, int ladders) {int nheights.size();//先将每个房子之间的高度差进行统计vectorint heidiff(n-1);for(int i1;in;i) if(heights[i]heights[i-1]) heidiff[i-1]heights[i]-heights[i-1];//进行判断auto check[](int level){//模拟看能否到达level地方 level-1个间隔long long allaccumulate(heidiff.begin(),heidiff.begin()level,0L);priority_queueint,vectorint,greaterint pq; //找出ladders个最大的数for(int i0;ilevelladders0;i) {if(pq.size()ladders)pq.push(heidiff[i]);else if(pq.top()heidiff[i]){pq.pop();pq.push(heidiff[i]);}}//进行求和long long more0;while(!pq.empty()){morepq.top();pq.pop();}return all-morebricks;};int left0,rightn;while(left1right){int midleft(right-left)/2;if(check(mid)) leftmid;else rightmid;}return left;}
};
2861. 最大合金数 题解依旧是验证答案。通过二分来确定答案再对答案进行检测即可。如果答案的预算太大right-mid如果答案预算足够leftmid即可。 class Solution {typedef long long LL;
public:int maxNumberOfAlloys(int n, int k, int budget, vectorvectorint composition, vectorint stock, vectorint cost) {//判断能否创建ret个合金auto check[](LL ret){for(auto nums:composition){LL sum0;for(int i0;in;i)sumcost[i]*max(ret*nums[i]-stock[i],(LL)0);if(sumbudget) return true;}return false;};int left0,right1e8*21; //注意此处上界的取值及要靠你budegt好要考虑stockwhile(left1right){int midleft(right-left)/2;if(check(mid)) leftmid;else rightmid;}return left;}
};
总结
二分答案的关键是check函数的编写和上下界的判断以及什么时候能使用二分二分既能将题目的思路进行转变-----证明一个答案是否正确还能让时间复杂度大幅度下降。
