北京哪家公司做网站好,asp网站生成,wordpress插件video player,有哪些网页设计公司二分算法篇#xff1a;二分答案法的巧妙应用 那么看到二分这两个字想必我们一定非常熟悉#xff0c;那么在大学期间的c语言的教学中会专门讲解二分查找#xff0c;那么我们来简单回顾一下二分查找算法#xff0c;我们知道二分查找是在一个有序的序列中寻找一个数在这个序列…二分算法篇二分答案法的巧妙应用 那么看到二分这两个字想必我们一定非常熟悉那么在大学期间的c语言的教学中会专门讲解二分查找那么我们来简单回顾一下二分查找算法我们知道二分查找是在一个有序的序列中寻找一个数在这个序列的位置那么我们可以用二分查找来应用那么二分查找的算法的原理就是我们在这个有序区间[l,r]中寻找目标数x那么我们从中间位置mid处去匹配如果mid处的值大于x那么意味着mid处之后的值也一定大于我们的x(假设是一个升序序列),那么我们去左半边l到mid-1区间处匹配如果小于x那么mid处之前的位置也一定小于我们的x那么我们就去右半边的区间mid1到r区间去匹配每次都取中点位置与x进行比较然后确定下一次搜索的折半区间直到我们的区间长度只剩1或者中点处的值等于我们的mid 代码实现
int get(int l,int r,int target)
{if(lr){int midl(r-l)/2 //写成(lr)/2 可能会有溢出风险if(midtarget){return mid;}else if(midtarget){return get(l,mid-1,target);}else{return get(mid1,r,target);}
}
return -1;
}那么知道了二分查找的原理那么我们分析一下这个算法的时间复杂度那么假设我们的区间长度是n那么我们最坏的情况也就是我们整个区间都没有我们的目标值x那么意味着我们会将整个区间不断的二分直到区间长度为1那么我们也就可以建立一个等式假设我们二分的总次数是m那么每一次会将区间的长度给折半直到为1每次折半就是区间长度不断除以2除了m次最后得到1那么反过来就是我们区间长度为1不断乘以2乘了m次得到长度n所以就有 2 m n 2^mn 2mn 再两边同时取对数则可以得到 m l o g 2 n mlog2^n mlog2n 所以我们二分算法的时间复杂度是log2^n,那么这个时间复杂度是非常优秀的了假设我们的n是21亿的话那么总共要二分的次数也就32次但是我们二分查找有一个局限那就是我们的数据集必须是要有序的 但是我们的二分算法可不止于此很多人以为所谓的二分就是我们c语言学的二分查找那么简单二分在我眼里它可不仅仅是一个所谓具体的一个算法而是一种思想刚才的二分查找可谓是给你端上了一份开胃菜那么真正的大餐就在我们的下文当中
1.二分原理
那么我们二分算法很多人认为我们只有一个数据集是有序或者更贴切的说数据集是具有单调性的那么才可以应用我们的二分。
那么所谓的单调性我们可以用数学中的一次函数来理解那么我们知道一次函数是一个直线那么根据其斜率的正负那么斜率大于0那么该一次函数的y值是随着x的增长而递增反之小于0则是递减那么我们的一次函数就是具有单调性的一个函数那么我们的数据集就好比是在这个一次函数的直线上的一个个点那么我们二分就是在这个直线上取一个点看该点和我们的答案之间的关系如果该点小于我们的答案那么我们就到在沿着直线往上寻找反之则往下寻找那么这就是单调性。
那么话虽没错我们数据集具有某种单调性我们可以应用二分但是我们能二分的场景不一定一定要具有单调性那么我们的二分更为关键的应用那么就是寻找一个性质的边界
那么对于一个我们要寻找的答案来说答案如果具有一个区间假设是[L,R],那么该区间那么可以按照某个性质将我们这个区间给分成了左右两部分那么我们的二分就可以分别寻找着左右两部分的性质的边界那么其中我们可以寻找左半边性质的右边界以及右半边性质的左边界这里左右半边的边界是肯定不能重合的因为我们该性质将该区间分为两个部分也就是这个区间中的每个点只能拥有这两个性质中的其中一个不可能同时具备两个性质所以我们左右边界是不可能重合的。
那么我们找这两个边界我们有两种方式分别是整数二分以及浮点数二分那么这个两种方式都有固定的模版那么我们先来讲解一下整数二分
那么我们首先来寻找右区间的左边界那么我们不知道我们这个左边界的具体位置究竟是哪里那么我们就得通过二分的方式来逐渐逼近那么怎么逼近呢
那么我们每次都取要搜索区间[L,R]的中点mid然后得定义一个check函数那么该函数就是检验这个区间中的任意一点是否满足右区间的性质那么有了check函数那么如果我们该中点mid是满足我们的右区间的性质的话那么我们check函数会返回一个true反之如果该中点不满足右区间的性质而是满足左区间的性质的话则返回一个false那么如果我们将该中点mid代入check函数之后返回的是一个true那么确定从mid到R这个区间是我们的右区间那么我们的右区间的左边界只可能在mid的左侧不可能在右侧所以我们就得去L到mid区间处继续二分所以我们要搜索的区间就是[L,mid]这里的mid替换我们的R注意这里我们一定要取到mid而不是mid-1因为我们这里的区间是左闭右闭的区间那么我们如果是左开右开的话那就是mid-1。
那么如果我们的check函数返回的是false那么说明我们该中点mid不满足右区间的性质那么我们右区间的左边界一定在mid之后并且取不到mid所以我们就到右侧mid1到R处继续二分那么直到区间长度为1从而找到该边界点
同理
对于寻找左区间的右边界那么我们还是一样的思路定义一个check函数那么从中点处检验如果满足该左边界的性质那么则返回true那么说明我们的右边界只可能出现在mid的右侧也就是在区间[mid,R]位置处如果返回false那么mid位置处不满足左区间的性质那么只能在[L,mid-1]处继续去二分
那么寻找右区间的左边界的代码板子如下
//寻找右边界的左边界
while(lr)
{int mid(lr)/2;if(check(mid)){rmid;}else{lmid1;}
}寻找左区间的右边界的代码板子
//寻找左边界的右边界
while(lr)
{int mid(lr1)/2;/*这里假设我们的lr-1那么如果是(lr)/2的话那么向下取整结果会是l会死循环所以为了避免这个情况会加1得到结果是r*/if(check(mid)){lmid;}else{rmid-1;}
}浮点数二分
而我们浮点数二分的思路和我们整数二分的思路是一样的只不过相比于整数二分我们浮点数二分由于精度更高那么我们每次二分划分的边界点更为精确那么如果我们最终二分的区间已经很小趋近于0的时候那么我们就确认找到了边界点
代码板子
while(lr)
{int mid(lr)/2if(check(mid)){lmid;}else{rmid-1;}
}2.二分答案法原理
那么有了我们刚才的二分的原理那么这里我们就可以来了解所谓的二分答案法是什么了那么二分答案发是一个利用二分来求解答案的算法
那么如果我们发现我们该题目的要最终求解的答案明显有一个明确的区间[L,R],
并且答案与我们的题目所给的条件具有一种单调性的关系那么我们就可以定义一个性质然后该性质将我们的答案所在的区间[L,R]给分成了左右两部分区间其中这两部分要么左区间要么是满足该性质右区间则是不满足该性质所以将整个区间一分为二或者则是左区间不满足该性质但右区间满足该性质。
所以我们得根据我们答案与题目所给的条件之间具备的单调性来判断我们满足该性质的区间究竟是左区间还是右区间确定之后我们在利用我们的二分依据该题所编写的check函数来检验中点mid的值是否满足我们定义的该性质从而确定去哪个区间进行二分然后不断二分逐步逼近边界点直到找到这个边界点而整个二分答案法流程中的最难的一步便是我们性质的定义有的难题它的要定义的性质你很难想得到那么性质想不到会导致我们核心的check函数你写不出来那么这个题也就根本做不出来了那么我们只有多连续见得多了才能对这个check函数的编写得心应手。
那么这就是我们的二分答案法的思想那么我们该题能否应用二分答案法的特征就是是否答案有明确的区间并且答案与题目条件是否具备单调性那么满足该特征则可以用我们的二分答案法。
那么我们二分答案法只要也就是解决最大值最小化或者最小值最大化等等问题我们具体能不能使用二分答案法核心还是得看我们对于题目的条件的理解与分析。
那么接下来我就会通过几个例题来具体实战一下看看我们这些题是怎么观察分析以及如何应用我们上面那套二分答案法的流程的。
3.应用实战
题目一爱吃香蕉的珂珂 难度EZ 题目分析那么这里我们知道我们这道题要求我们的最小且满足题目要求的速度那么这里速度是我们要求的答案那么我们分析一下题目的条件我们其实不难发现我们的速度是有一个明显的区间那么每堆香蕉最少只有1个那么也就意味着我们的速度可以是1那么速度最大则是这n堆香蕉的最大值因为我们知道无论速度比这个值还大那么我们一小时再怎么快速吃完该堆香蕉只能陷入等待等到下一小时吃下一堆也就意味着如果速度比这还大那么它对时间的缩短没有任何贡献了所以我们确定了我们的答案也就是速度所在的区间是在[1,max(piles[i])]中那么我们接下来来分析一下答案是否存在某种单调性我们发现这里我们速度越大那么我们吃香蕉的时间只会缩短或者不变反之速度越小那么时间只会变长那么速度越大时间变短或者不变那么也就意味着它越容易在警卫离开的h小时内吃完。
所以我们这里根据前面的分析那么便可以定义性质也就是我们在该速度下能够在h小时内吃完所有的香蕉那么我们根据我们的单调性我们速度越大越容易在h小时内吃完所有的香蕉那么意味着我们满足该性质的一定是这个答案区间的右区间而不是靠左的左区间那么我们接下来就是寻找右区间的左边界那么这个左边界就是我们这个题的答案那么我们根据这个性质来实现一个check函数来检验一下mid是否满足该性质满足返回true不满足返回false至于二分的过程就是我们上文所讲的原理而具体实现check函数的细节我这里也就不再赘述了
代码实现
class Solution {
public:
bool check(int x,int h,vectorintpiles)
{long long sum0;for(int i0;ipiles.size();i){sum(piles[i]x-1)/x;}if(sumh){return false;}return true;
}int minEatingSpeed(vectorint piles, int h) {int l1,r0;for(int i0;ipiles.size();i){if(piles[i]r){rpiles[i];}}while(lr){int mid(lr)/2;if(check(mid,h,piles)){rmid;}else{lmid1;}}return l;}
};那么这里我们看看这个题是不是应用了我们刚才说的那套流程也就是发现我们的答案存在某个区间然后分析答案的单调性根据单调性定义性质写出check函数然后二分那么这就是我们二分答案法的一个分析的思维模式以及套路
1.确定答案所在区间[L,R]
2.分析答案的单调性
3.根据单调性定义性质
4.根据性质写出二分答案法核心的check函数
5.不断二分寻找边界
题目二画家 难度HARD
题目现在我们有k个画匠那么我们有n幅画需要画匠完成其中每幅画完成的时间为n[i] (0in)分钟那么我们每一个画家只能完成连续的m幅画也就是说我们其中一个画家可以分配完成第一幅以及第二幅画但是不能分配完成第一幅以及第三幅画因为不是连续的那么我们画家同时画画那么我们整个n幅画完成的时间就是这k个画家中其中一个完成的最长的那个时间那么我们可以不用分配所有画家去做画可以只分配一个画家或者全部画家并且每个画家分哪些画都是我们自己确定那么问我们k个画家完成这n幅画的最短时间是多少
题目分析
那么这个题我们这里我们要求完成这n幅画的最短时间那么我们就是要让每个画家的完成时间尽可能的短那么我们仔细分析题目的条件那么我们发现我们的每个画家作画时间也是有一个区间的那么我们的画可以是0幅那么我们可以不用分配画家那么理轮上画家的完成时间可以是0同时我们也可以只分配一个画家那么画家的完成时间则是所有画的总时间那么我们便得到了画家的作画时间的一个区间[0,sum(n[i])]那么我们再来分析一下作画时间的单调性那么我们如果给一个画家分配的时间越多那么意味着我们画完这n幅画所需要的画家的数量就越少那么同理如果每个画家分配的时间越少那么我们画完这n幅画所需要的画家的数量就越多那么有了这个单调性我们便可以定义我们的性质每个画家作画的时间不超过t分钟我们能分配不超过k个画家来完成这n幅画。
那么我们可以利用这个性质将我们的答案区间给一分为二那么根据我们刚才分析的单调性我们一个画家分配时间越多那么画完这n幅画所分配的画家的数量越小那么也就意味着我们画家作画时间越长那么越能够满足我们这个性质所以我们确定我们满足这个性质的区间是右区间那么题目的答案也就是得到右区间的左边界那么我们写一个check函数来检验中点mid是否满足该性质来进行二分即可
代码实现
class Solution {
public:
bool check(int x,int k,vectorinttime)
{int ans1;int temp0;for(int i0;itime.size();i){if(time[i]x){return false;//如果本身该幅画的时间就超过了每个画家的最大分配时间那么直接返回false}if(temptime[i]x){ans;temptime[i];}else{temptime[i];}}if(ansk){return true;}
}int minTime(vectorint time, int k) {int l0,r0;for(int i0;itime.size(),i){rtime[i];}while(lr){int mid(lr)/2;if(check(mid,k,time)){rmid;}else{lmid1;}}return l;}
};题目三机器人跳跃 难度MID
题目现在有一个机器人它要跨越n个平台那么这n个平台中每个平台的高度为H[i] (0in),那么我们机器人能够跳跃一个平台的前提条件就是我们这个机器人的能量值k要大于等于该平台的高度那么就能跳跃过去并且成功跳跃该平台机器人的能量值k会加上能量值与平台高度的差值k-H[i]那么现在机器人在跳跃第一个平台之前有一个初始能量值k那么问初始能量值最小为多少能够让机器人跨越所有平台
题目分析那么我们根据题意机器人如果能量值比平台高那么不仅能跨越并且能量值还能够得到增长那么也就意味着我们机器人的能量值越高那么它更有能力跨越平台并且还能获得增长那么能量值越高一定是不吃亏的反而能量值越低会有风险跨不过平台并且增长还少那么根据这个分析我们就找到我们要确定的答案也就是能量值的一个单调性了那么我们看看我们这个能量值的区间理论上我们能量值的最小值可以为0假设平台的高度都为0那么最大值的话能量值最大就只需要达到所有平台的最大高度即可因为达到这个高度根据题意我们就必定足够跨越所有平台即使不加能量的增长那么我们的能量值的区间[0,max(H[i])],那么我们在根据我们之前的单调性定义性质机器人在该能量值下能够跨越所有平台。
那么这个性质能够将我们的区间一分为二并且右区间是满足我们的性质那么这题的答案就是寻找我们右区间的左边界那么我们根据这个性质来编写我们的check函数。
但是这道题我要对check函数的实现提一嘴这里我们的能量的增长可以是指数级的假设我们的平台高度都是2那么我们的初始能量值是4那么我们每次增加的能量值是2,4,8,16那么我们如果这个平台的数量过长那么我们只打我们这里的能量值的增长是一个以2的n次方的速度增长那么指数级的增长是很快的那么就会导致我们最后的能量值我们用int或者long类型接收都会出现溢出的风险所以这里是一个陷阱我们在实现check函数的时候当我们的能量值已经达到和最大平台高度一样的时候我们就确定它能够跨越玩所有的不用在依次往后遍历所以在check函数的实现要注意
代码实现
class Solution {
public:
bool check(int k,int max,vectorintheight)
{for(int i0;iheight.size();i){if(kheight[i]){return false;}if(kmax){return true;}k(k-height[i]);}return true;
}int minEnerge(vectorint height, int k) {int l0,r0;for(int i0;itime.size(),i){rmax(height[i],r);}while(lr){int mid(lr)/2;if(check(mid,r,height)){rmid;}else{lmid1;}}return l;}
};题目四第k小 难度HARD
题目:现在有一个整数序列num那么我们这个序列当中的两个不同位置的数num[i]和num[j] (i!j)可以组成一个数对那么这个数会得到一个得到一个差值这个差值是绝对值那么我们这个数对当中各个不同的数对的差值可以排序那么我们要求其中第k小的差值是什么
例[1,2,1]
[1,2]-1
[1,1]-0
[2,1]-1
第一小的差值是0
题目分析那么这里我们首先可以得到这个差值的区间那么最小只能是0那么最大则是我们这个序列中最大是减去最小数得到那么我们可以首先对整个序列排序然得到差值的最大值那么这个差值的最大值的区间就是[0,max-min],那么这个题其实最难想的就是性质的定义因为这题差值的单调性的具体含义是比较难想这个题的关键就是我们对于一个差值假设差值为m那么我们在这个序列中差值为m的数对可能不只有一个就在上面的以数组[1,2,1]为例子中我们差值为1的数对有两个那么假设我们这个差值为m是我们这个序列的第k小的差值那么意味着我们前面比我们这个差值m还要小的差值有k-1个那么同理对于前面比m还要小的k-1个差值每一个差值所对应的数对也至少有一个对应的数对那么意味着我们包括前面k-1个差值的数对和当前第k小差值的数对加起来总的数对的数量它一定是大于等于k个的那么你的差值越大那么对应的总数对的数量一定会增多反之差值越小对应的总数对一定越少
那么我们可以这样定义我们的性质在差值不超过m的情况下我们的数对的数量大于等于k个
那么我们可以将这个区间一分为二然后右区间是满足性质的区间那么我们就写一个check函数来验证在不超过该MID值下我们的数对的数量是否大于等于k这里我们对数组进行了排序那么我们可以利用滑动窗口来计数实现check函数。
那么这个题难就在难在这个性质的得到以及如何写check函数。
代码实现
class Solution {
public:// 检查函数判断差值不超过mid的数对数量是否大于等于kbool check(int mid, vectorint nums, int k) {int count 0;int n nums.size();int j 0;// 使用滑动窗口计算数对数量for (int i 0; i n; i) {while (j n nums[j] - nums[i] mid) {j;}count j - i - 1; // 计算以i为起点的数对数量if (count k) {return true;}}return count k;}int smallestDistancePair(vectorint nums, int k) {sort(nums.begin(), nums.end()); // 对序列进行排序int l 0, r nums.back() - nums.front(); while (l r) {int mid l (r - l) / 2; // 计算中点if (check(mid, nums, k)) {r mid; // 缩小右边界} else {l mid 1; // 扩大左边界}}return l; }
};4.结语
那么本文就讲述了我们的二分答案法那么看完本篇文章我觉得你应该收获了如何写二分的一个模本以及二分答案法的流程但是我想说的是算法的学习可不仅仅学会了原理就够了还要自己下去不断练习
