前言在这篇文章中，我们将会一起学习二分算法，比上一章的滑动窗口要难上许多（对我来说）。话不多说，我们直接开始。1.二分算法的基本定义一句话概括本质：通过判断左右边界所围成区域的中点的值和目标值的关系，来决定下一步要在该区域的哪半边继续进行同样的操作，直到触发循环的退出条件。讲一讲流程就是(以左右闭区间为例)：假设我们拿到一个升序的序列nums和要查找的目标值target，那么我们开局将左边界left和右边界right都设立在这个序列的两头(举个例子，0和len(nums)-1)，进入循环后先取它的中点mid，判断nums[mid]的值：如果nums[mid]≥target，那就选择左半边进行下一步，使right=mid-1；反之，选择右半边进行下一步，使left=mid+1。周而复始，直到触发循环的退出条件(此处是left>right退出)。2.如何进一步理解二分算法-红蓝染色法可以先去看这个视频：【算法入门】用红蓝染色法学爆二分查找在红蓝染色法中，我们将一个升序数组分成蓝区(<目标值的区域)，空白区和红区(>=目标值的区域)。我们二分就是把对应的元素染色到对应的区域。在这个视频中，博主介绍了三种二分类型，分别是左右开区间、左右闭区间以及左闭右开区间。为了方便，本文章统一使用左右闭区间，即[l,r]。在这个视频中，左右闭区间类型的二分算法在循环结束后，有一件事情是永远不变的，无论红蓝区的标准如何调整：l在红区的最左边，r在蓝区的最右边。如下图所示：并且，按照我上面的分区设定，l会正好指在target上面(如果有)，如果没有target，会指在大于它的第一个数上面。所以如果你要找target或者大于它的第一个数，直接输出nums[l]就行了。那么遇到其他类型又怎么办呢？假设题目就是想让我找>target的第一个数，并且nums中有可能本身就有target，如果还是按照上面的标准划定红蓝区，那么就有可能直接输出target了，这咋整呢？先记住上面永远不变的事情，然后我们再去调整蓝区和红区的标准，就能做到这件事：把红区调整成>target的数全都在这里面，把蓝区调整成≤target的数全都在这里面。再看看上面永远不变的事情，是不是l自然而然就指到了比target大的第一个数上，并且即使有target，也不会指到target上。那么反映到代码上，又会变成咋样呢？先看看最上面情况的代码(蓝区是<目标值的区域，红区是>=目标值的区域)： int lower_bound(vector<int>& nums,int target){ int l=0,r=nums.size()-1; while (l<=r){ int mid=(l+r)/2; //下面这一行代码是最关键的，是决定红蓝区域性质的核心代码 if (nums[mid]<target){ //由于l左边(不包含它自己)是蓝区，如果nums[mid]<target， l=mid+1; //那么将其收入蓝区； }else{ //如果nums[mid]≥target， r=mid-1; //将其收入红区 } } return l;//输出红区的最左边的元素 }结合注释看，你现在一定有所体会了吧？所以，如果我们要求大于target的第一个数，那就按照上面的标准来更改红蓝区：把红区调整成>target的数全都在这里面，把蓝区调整成≤target的数全都在这里面。 int lower_bound(vector<int>& nums,int target){ int l=0,r=nums.size()-1; while (l<=r){ int mid=(l+r)/2; if (nums[mid]<=target){ //由于l左边(不包含它自己)是蓝区，如果nums[mid]<=target， l=mid+1; //那么将其收入蓝区； }else{ //如果nums[mid]>target， r=mid-1; //将其收入红区 } } return l;//输出红区的最左边的元素 }这样一讲，是不是小于target的第一个数等等情况，你也能解决了？如果要找小于target的第一个数，就直接将蓝区改成<target，红区改成≥target，最后l-1就是答案的位置(如果算出来是-1，说明不存在，target就是最小的数)。其他情况就不讲了，举一反三即可。3.题目实战——二分查找型 0809更新做了4天的题目(当然也只限于白天的时间做，晚上或者接近晚上时我要三角洲启动)，属于是要给我燃尽了。这个难度真的比滑动窗口难多了。滑动窗口是这样的：简单题直接秒，中等题有的能秒有的得稍微想想，hard题目有点难度，有的能想出来，没想出来的看题解后也能豁然开朗；二分呢？简单题我得想想到底哪里能用到二分，中等题我绞尽脑汁，hard题连题解也看不懂。别问我为啥中间空着一些题目没做，大部分的题目都是涉及到类(class)等等的概念(除了3488和两道会员题之外其他都是)，我连题意都难以理解，更别说做出来了。等其他正常的算法题做完之后，我再回过头来学习学习类的概念，在其他类型题目的章节中挑几题讲讲。在做出来的题目之中，以下题目是我没使用二分算法做出来的，因为我没想到哪里能用到二分，所以也排除在此次讲解名单之外：1385. 两个数组间的距离值2389. 和有限的最长子序列658. 找到 K 个最接近的元素感兴趣的同学可以自己去做做看。排除掉上面这些题目，剩下的题目，我来挑一些讲解。除了简单题，中等及以上的都有一个共同特质：都是10^5的数据规模，必须要利用二分去卡nlogn的时间复杂度，否则就超时。那我们先从简单题开始吧。3.1 简单题：利用红蓝染色法掌控left指针最终落点由于在第二个章节中，我已经将红蓝染色法讲的比较细致了，所以我在这里题目的讲解中会一笔带过。先看第一题：34. 在排序数组中查找元素的第一个和最后一个位置这道题要求我们找到升序数组中重复元素所在的区间。换句话说，我们只需要二分两次，第一次确定该元素最开始的点位，第二次确定比该元素大1的元素的位置。是时候请出红蓝染色法了！设定红蓝规则如下：蓝区包含<target的数，红区包含>=target的数，由于left指针一定会落在红区的最左边第一位，所以left指向的要么是target，要么是比target大的第一个数。所以在我们的第一次二分中，直接取left就是该元素的左区间。再加个判断：如果nums[left]≠target或者left超出了数组右边界1格，说明不存在该元素，我们直接返回[-1,-1]，都不需要做第二次二分了。如果第一次二分找到了，没退出，那就继续第二次二分。我们需要找到该元素的右边界。继续沿用上面的红蓝规则，我们直接代入target+1，这样最后left一定会停在target+1这个数或者比target+1大的第一个数上，那此时的left-1就一定是target。这时候就不需要判断了，left最多超出数组右边界1格，left-1是一定在界内的(建立在第一次二分合法的前提下)。看代码：class Solution { public: int lower_bound(vector<int>& nums, int target){ int l=0,r=nums.size()-1; while (l<=r){ int mid = (l+r)/2; if (nums[mid]<target){ //因为left左边是蓝区 l = mid+1; //所以按照职责的划分，小于target的数会被l扫过去，进入蓝区，包括nums[mid]本身 }else{ //二分代码的核心就在这几行，别的没啥好讲解的 r = mid-1; } } return l; } vector<int> searchRange(vector<int>& nums, int target) { //解题主程序 int start = lower_bound(nums,target); //查找该元素左边界 if (start==nums.size() || nums[start]!=target){ //按照上面所说的，进行合法性判定 return vector<int>{-1,-1}; //若非法，说明没找到 } int end = lower_bound(nums,target+1)-1; //按照上面所说的，找右边界 return vector<int>{start,end}; } };剩下的基础题目中，下列题目都是和本题一样的红蓝规则，我就不重复讲解了：35. 搜索插入位置2529. 正整数和负整数的最大计数但是有一道题是例外，它的红蓝规则和本题一样，但是我用到了一个新东西——保存答案并提前退出。请看第二题：704. 二分查找其实呢，这道题不用这个新东西也是能做的，就是稍微麻烦一点：在循环退出后，判断left指针是否越界、指向的是不是target，如果是就说明找到了，否则就是没找到。但是，用了这个方法后，我们只需要起一个ans变量，令它初始等于找不到就要返回的值(本题是-1)，并且在二分的判断中插入一条对nums[mid]是否等于target的判断语句，如果是，就将mid存入ans，然后直接break。事后不需要任何判断，直接就能返回ans。class Solution { public: int search(vector<int>& nums, int target) { int l=0,r=nums.size()-1,ans=-1; while (l<=r){ int mid=(l+r)/2; if (nums[mid]<target){ //一样的红蓝规则 l=mid+1; }else if (nums[mid]==target){ //中途插入是否相等的判断 ans=mid; break; }else{ r=mid-1; } } return ans; } };接着我们来讲第三题：744. 寻找比目标字母大的最小字母。这题的红蓝规则和前面两题不一样，让我们一步步来寻找新的规则。它要找比目标字母大的第一个字母，也就是我就算找到了目标字母，也不行，得去找比它大的第一个字母。这种情况下，我们直接令红蓝规则如下：蓝区包含<=target的字母，红区包含>target的字母。由于left一定会落在红区最左边第一个，所以自然而然就落在了比目标字母大的第一个字母上。是不是非常巧？class Solution { public: char nextGreatestLetter(vector<char>& letters, char target) { int l=0,r=letters.size()-1; while (l<=r){ int mid=(l+r)/2; if (letters[mid]<=target){ //蓝区包含<=target的字母 l=mid+1; }else{ r=mid-1; } } if (l==letters.size()){ //如果left超出了数组右边界，说明没找到 return letters[0]; //按照题目要求返回第一个字母 } return letters[l]; } };至此，二分查找的基础题目已经过了一遍。如果上面3题全都掌握，那么你已经基本上掌握了红蓝染色法的精髓。3.2 中等题以及hard题：nlogn是我的底线这一部分的题目，我很难去归纳出几种类型。因为这和上一个滑动窗口的难题一样，重点不在二分查找本身，而是你不知道你该拿二分查找去干啥，在动用二分查找之前该如何转换题目的条件。所以，如果强行归纳，那么这些题目有一个共同点：拿一连串的询问去一串数组里面二分查询啥东西，并且还把排序这个数组的工作交到了你手上，时间复杂度nlogn，别的没了。所以，学会使用各个主流竞赛语言的内建排序方法还是非常重要的，下面来盘点一下。3.2.1 各个主流竞赛语言的内建排序方法1.c++的内建排序方法int main(){ vector<int> nums = {1,1,4,5,1,4}; //初始化数组 sort(nums.begin(),nums.end());//升序排序 sort(nums.begin(),nums.end(),[](auto& a,auto& b){ //降序排序 return a>b; //此处使用lambda规则，其中a和b代指前一个元素和后一个元素，a>b即为我希望前一个比后一个大，实现降序排序 }); }2.c++使用lambda对二维数组进行自定义排序当然这里可以灵活应变，换成pair也是可以的。cpp的lambda还是比较好理解的，我是直接死记硬背的，反正目前就这个场景会用到。int main(){ vector<vector<int>> matrix = {{1,2,3},{5,4,6},{8,9,7}}; sort(nums.begin(),nums.end(),[](auto& a,auto& b){ //这里的a和b代指拨开matrix的第一层元素，即{1,2,3}这样的 return a[0]<b[0]; //这里的意思是取第一位进行比较，即按照第一位的大小进行降序排序 }) }3.python的内建排序方法(包含lambda自定义排序语句，若有不懂，请先去学习python的lambda语句)nums = [1,1,4,5,1,4] nums.sort() #升序排序，直接改变nums本身 nums.sort(reverse=True) #降序排序 sortedNums = sorted(nums) #升序排序，不直接改变nums本身，需要自己拷贝 sortedNums = sorted(nums,reverse=True) #降序排序，不直接改变nums本身，需要自己拷贝 matrix = [[1,2,3],[4,5,6],[7,8,9]] matrix.sort(key=lambda x:x[0]) #此处是按照子列表的第一个数的大小进行升序排序 matrix.sort(key=lambda x:x[0],reverse=True) #此处是按照子列表的第一个数的大小进行降序排序4.Go的内建排序方法不讲它的自定义排序了，纯纯路边，竞赛用这个纯属浪费时间。想学的去滑动窗口的文章里面找，那里面有。sort.Ints([]int)升序排序 int 切片。sort.Float64s([]float64)升序排序 float64 切片。sort.Strings([]string)升序排序 string 切片。不多说。3.2.2 正式开始题目实战首先看第一题：1170. 比较字符串最小字母出现频次我们需要分成两步来解决这个题目。首先解决这个f(s)函数，再利用这个函数去解决题目的问题。如何写这个f(s)函数呢？在这道题目，由于用例比较水，所以你直接遍历数次数也是可以的。但是我们这次学的是二分算法，所以我们可以先排序，后二分：将字符串按照字母序升序排序后，利用二分找重复字母的左边界和右边界，然后减一减就是出现次数(和上面34. 在排序数组中查找元素的第一个和最后一个位置是一样的)。int f(string s){ //1.给字符串排序 aaazz sort(s.begin(),s.end()); //2.找最小字母 char target = s[0]; //3.二分找边界 int l = 0,r = s.size()-1; while (l<=r){ int mid = (l+r)/2; if (s[mid]<=target){ //<=的放蓝区 l = mid+1; }else{ r = mid-1; } } return l; //左边界最终落点即为出现次数 }接下来开始解决题目要求的问题。我们可以看到，题目中的比较都是f(s)求值后的数字之间的比较，所以我们需要先遍历queries和words，一个个调用f(s)将其转换成频率的数值并存入数组。接下来我们只需要对着两个数组处理问题即可。接下来，我们需要获取需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目，并且W 表示词汇表 words 中的每个词。这说明我们可以继续使用二分——一个个取出queries[i]，事先将words数组排序好，然后用二分去找queries[i]，设定蓝区为<=，红区为>，这样最后left一定指向大于 f(queries[i]) 的第一个数。最后再用数组长度-left，直接得出答案。class Solution { public: int f(string s){}//此处省略，同上 vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) { //1.把queries和words全部转换成数组 vector <int> qs,ws,ans; for (int i=0;i<queries.size();i++){ qs.emplace_back(f(queries[i])); } for (int i=0;i<words.size();i++){ ws.emplace_back(f(words[i])); } //2.给ws排序 sort(ws.begin(),ws.end()); //3.单独拎出qs，一个个和ws对比 for (int i=0;i<qs.size();i++){ int k = qs[i],l = 0,r = ws.size()-1; while (l<=r){ int mid = (l+r)/2; if (ws[mid]<=k){ l = mid+1; }else{ r = mid-1; } } ans.emplace_back(ws.size()-l); } return ans; } };接下来来到难度上升的第二题：2563. 统计公平数对的数目这道题，我们需要解决如何计算符合条件的对数。仔细看看题目条件：lower <= nums[i] + nums[j] <= upper，且0 <= i < j < n——按照以往的做题经验，我们只需要揪住其中一个不放，让另一个动起来就行了。否则两个都在动，我们不好处理。那么具体怎么操作呢？看看数据规模，依旧是我们熟悉的10^5，这注定我们的时间复杂度不能超过nlogn，自然而然想到了第一层枚举+第二层二分。我们将nums[i]移项到两边，这样我们的不等式就变成了lower-nums[i] <= nums[j] <= upper-nums[i]，这样我们不是只需要找到符合条件的nums[j]就行了？这样我们就形成了一个基本框架：将数组提前排序好，一层循环遍历找nums[i]，二层二分找符合条件的nums[j]的左边界和右边界，这样我们就能在规定的时间复杂度内完成这道题目。接下来来解决第二个问题：我们该设定咋样的红蓝规则来找到左右边界呢？为了方便，我们规定我们所寻找的是闭区间(像[1,3]这样的)，在本题中，就是[lower-nums[i],upper-nums[i]]这样的区间。先找左边界的位置，我们令蓝区为<，红区为>=，这样left天然就会落在左边界上；再找右边界，我们令蓝区为<=，红区为>，这样left-1就一定会落在右边界的位置。由于上面对红蓝染色法铺垫了太多，此处我讲的十分简略。如果这里你看不懂，退回去从头开始看就行了(那个视频也要看)。这样，我们就知道该如何寻找符合条件的数的左右边界了。接下来还有最后一个问题——计算组数，这也是个难点。由于组数和两个数字的顺序无关，所以为了防止重复，我们只关注第一层枚举出来的数的后面的数，这个数后面有几个符合条件的数，我们就将其与这个数连线，就构成了几个数对。由于我们二分查找的范围是整个数组，有时候left边界甚至left、right两个边界会一起跑到我们枚举的i的左边去，这时候就需要我们加以判断并做出处理，这是决定这道题目能不能做对的关键。首先，如果left超出数组的边界咋整？这说明这个数组里面的数都太小了，没一个数是能符合lower-nums[i]的标准的，这种情况直接跳过，没一个能累加的。其次，如果right<=i呢？按照我们上面不重复的原则，这样也是不能累加的。那么，如果i被夹在left和right中间呢？此时，只需要取max(left,i+1)作为左边界就行了，我们需要主动舍弃<i+1的部分，因为这样会重复。至此，本题思路讲述完毕，比上一题多了一些巧思，尤其在边界处理上还是有些难度，上代码：class Solution { public: long long upper_bound(vector<int>& nums, int upper){ //找右边界 int l=0,r=nums.size()-1; while (l<=r){ int mid = l+(r-l)/2; if (nums[mid]<=upper){ l = mid+1; }else{ r = mid-1; } } return l-1; } long long lower_bound(vector<int>& nums, int lower){ //找左边界 int l=0,r=nums.size()-1; while (l<=r){ int mid = l+(r-l)/2; if (nums[mid]<lower){ l = mid+1; }else{ r = mid-1; } } return l; } long long countFairPairs(vector<int>& nums, int lower, int upper) { //1.给nums排序 sort(nums.begin(),nums.end()); //2.开始二分找合格的数字的范围并累加 long long sum = 0; for (int i=0;i<nums.size()-1;i++){ int k = nums[i],low = lower-k,up = upper-k; //这里是对原不等式的移项操作 int left = lower_bound(nums,low); int right = upper_bound(nums,up); if (left>=nums.size() || right<=i){ //很重要的判断 continue; } sum+=right-max(left,i+1)+1; //处理i夹在l和r中间的情况 } return sum; } };接下来来到第三题：LCP 08. 剧情触发时间这道题比第二题略微简单一些，和第一题难度差不多，这是我主观上的感受，因为我想了一会也算是想出来了。主要思路就是这样：把每日的递增量累加起来，自然而然就形成了一个每个值都上升的二维数组；然后单独拎出每个剧情触发的要求requirements[i]，里面有三个数，我们再单独拎出其中的每个数requirements[i][j]，使用二分找到它开始达标的第一天的位置(红蓝规则如下：蓝区<，红区>=，这样left的落点就是刚刚开始达标的第一天的位置)，把三个数的位置都找出来并记录，最后选出最大(最靠右)的那个位置，就是3个全都达标的天数。这利用了每个值都上升的特性，只要前面达标了，不管多后面它都会达标。这题是真正的巧思，如果没想到这一点，用其他方法我也不知道怎么做。上代码：class Solution { public: int betterMax(vector<int> nums){ //用来求数组最大值的函数 int maxNum=nums[0]; //所以cpp和go能不能学一下python的max()？尤其是go for (auto x:nums){ maxNum=max(maxNum,x); } return maxNum; } vector<int> getTriggerTime(vector<vector<int>>& increase, vector<vector<int>>& requirements) { //1.写出自动升序的实时属性数量 vector<vector<int>> curNum(increase.size()+1,vector<int>(3,0)); for (int i=1;i<=increase.size();i++){ for (int j=0;j<3;j++){ curNum[i][j]=increase[i-1][j]+curNum[i-1][j]; //累加增量，此事在前缀和中亦有记载 } } //2.遍历reqs vector<int> ans(requirements.size(),-1); for (int i=0;i<requirements.size();i++){ vector<int> tempAns(3,0); bool flag = true; //触发器，如果其中有一个属性无法在规定天数内达到要求，就直接退出，没必要再算后面的属性了 for (int j=0;j<3;j++){ int req = requirements[i][j],l=0,r=curNum.size()-1; while (l<=r){ //二分找开始的天数 int mid = l+(r-l)/2; if (curNum[mid][j]<req){ l = mid+1; }else{ r = mid-1; } } if (l>curNum.size()-1){ //如果left落在了最后一位，说明 flag=false; break; } tempAns[j]=l; } if (!flag){ continue; } ans[i]=betterMax(tempAns); } return ans; } };接下来来到第四题：2070. 每一个查询的最大美丽值，从这道题开始，还有下面的第五题，我都没想出来，看题解做出来的，好在题解也是看懂了。看完题目了？那就先看题解吧：灵神的题解，看里面的方法二，方法一我没看懂。方法二的精髓是这个《左侧最大值》的算法，这使得我们可以直接对着处理好的数组二分查找，十分方便。看看我的代码：class Solution { public: vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) { //1.按照价格大小排序 sort(items.begin(),items.end(),[](auto& a,auto& b){ return a[0]<b[0]; }); //2.原地构建左边的最大美丽值 for (int i=1;i<items.size();i++){ items[i][1]=max(items[i-1][1],items[i][1]); } //3.二分查找价格的正确位置 vector<int> ans(queries.size(),0); for (int i=0;i<queries.size();i++){ int l=0,r=items.size()-1,k = queries[i]; while (l<=r){ int mid = l+(r-l)/2; if (items[mid][0]<=k){ l = mid+1; }else{ r = mid-1; } } if (l-1>=0){ //这里依旧需要留心处理边界 ans[i]=items[l-1][1]; } } return ans; } };接下来来到本次讲解的最后一题，第五题：1818. 绝对差值和这题我依旧是没想出来，看了题解做出来的，请先阅读该题解。看完题解后，我豁然开朗，但是仍然有一点搞不明白：它为何不处理重复取元素的情况？毕竟nums1和nums12，后者排序了，去后者二分查找是极有可能找到一个和前者nums1[i]相等的元素的。后面明白了：即使重复了又如何？重复找到了最小的元素，不就说明我不需要用别的元素替换自己吗。毕竟题目也没强制要求必须替换。贴上我的代码：class Solution { public: int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) { //1.拷贝一份nums1，然后排序 vector<int> nums12=nums1; sort(nums12.begin(),nums12.end()); //2.对于nums1中的每一个元素，二分找和nums2[i]最接近的元素，并一直累加 long long sum=0,mod=1000000007,maxDiff=-1; for (int i=0;i<nums1.size();i++){ long long tempAns = abs(nums1[i]-nums2[i]),newAns=0; sum+=tempAns; int l=0,r=nums12.size()-1; while (l<=r){ int mid = l+(r-l)/2; if (nums12[mid]<nums2[i]){ l = mid+1; }else{ r = mid-1; } } if (l-1<0){ // newAns = abs(nums12[l]-nums2[i]); }else if (l>nums12.size()-1){ newAns = abs(nums12[l-1]-nums2[i]); }else{ newAns = min(abs(nums12[l]-nums2[i]),abs(nums12[l-1]-nums2[i])); } if (abs(tempAns-newAns)>maxDiff){ maxDiff=abs(tempAns-newAns); } } //3.直接sum-最大值就是答案 return (sum-maxDiff)%mod; } };至此，这一章节已经全部更新完毕。4.题目实战——二分答案型4.1 求最小 0814更新4.1.1 简介这一部分的题目，一句话概括：用二分算法去猜答案，然后再通过时间复杂度O(n)及以内的算法来判断我猜出来的答案对不对，再通过算法的计算结果来判断答案是大了还是小了，直到退出二分，即获得答案。下面放一个偷来的代码模板，能很完美的概括这一系列的题目：class Solution: # 计算满足 check(x) == True 的最小整数 x def binarySearchMin(self, nums: List[int]) -> int: # 二分猜答案：判断 mid 是否满足题目要求 def check(mid: int) -> bool: # TODO left = # 循环不变量：check(left) 恒为 False right = # 循环不变量：check(right) 恒为 True while left + 1 < right: # 开区间不为空 mid = (left + right) // 2 if check(mid): # 说明 check(>= mid 的数) 均为 True right = mid # 接下来在 (left, mid) 中二分答案 else: # 说明 check(<= mid 的数) 均为 False left = mid # 接下来在 (mid, right) 中二分答案 # 循环结束后 left+1 = right # 此时 check(left) == False 而 check(left+1) == check(right) == True # 所以 right 就是最小的满足 check 的值 return right这次的题目在前面也是偏简单的，主要是后面的一些题目真的挺难的。尤其是最后一题，我看题解也理解了半天。其实二分算法本身是一样的，这种类型的题目，主要就两个难点：第一个，也是最主要的，就是判断答案是否正确的算法，这是区分各个题目的一个东西；第二个，就是对二分算法上下界的判断，也基本得预先处理题目中的数组才能给出明确的上下界。我将上面的题目分为以下几类(是我自己做题的主观感受，如果想要客观评价，上方图片的顺序就是由简单到难)：1.基础题(我能较快做出来)1283. 使结果不超过阈值的最小除数2187. 完成旅途的最少时间1011. 在 D 天内送达包裹的能力875. 爱吃香蕉的珂珂2.进阶题(我需要思考一下才能做出来)3639. 变为活跃状态的最小时间 和 滑动窗口->不定长滑窗->求子数组个数->越长越合法 知识点梦幻联动(至少我的做法是这样) 讲解1482. 制作 m 束花所需的最少天数 这应该是没有固定模板，手搓的检查算法2594. 修车的最少时间 这题我也是受下面3296的启发才做出来的，如果没受启发，难度应该介于进阶和困难之间，比3296略简单3.困难题(我想不出来，看了题解才能做出来)3296. 移山所需的最少秒数 彻底干碎算法题目做太多的思维定式 讲解475. 供暖器 又是一个新思路 讲解4.地狱题(我看了题解还得理解很久，才能彻底弄懂)3048. 标记所有下标的最早秒数 I 讲解其中会讲解的题目也已经在上面标记了出来。4.1.2 部分题目的讲解先讲解第一题：3639. 变为活跃状态的最小时间，先看题。关键部分：如果 子字符串 包含 至少 一个 '*' ，则认为该子字符串有效。如果字符串中 有效子字符串 的总数大于或等于 k，则称该字符串为 活跃 字符串。看到这两句，你是不是想起了什么？没想起来的自己去https://blog.lecspace.com/index.php/archives/76/复习一下。不卖关子了，这就是 滑动窗口->不定长滑窗->求子数组个数->越长越合法 这一部分的知识点。我们可以在第一层使用二分猜答案，再在第二层使用越小越合法的老知识点，对*进行计数，并数出满足上述条件的子数组个数，再把它和k比较，就完事。看我的代码，有详细注释：class Solution { public: int minTime(string s, vector<int>& order, int k) { //解题主程序 //1.找二分的上下界并初始化 long long l = 0,r = order.size()-1,ans=-1; //2.开始二分 while (l<=r){ long long mid = l+(r-l)/2; string newS = s; //复制一份字符串便于我们处理 for (int idx=0;idx<=mid;idx++){ newS[order[idx]]='*'; //按照题目要求替换字符串 } //滑窗数符合要求的子字符串数量 long long left=0,cnt=0,count=0; //cnt是数*个数的，count是数符合条件的子数组个数的 for (long long right=0;right<newS.size();right++){ if (newS[right]=='*'){ cnt++; } while (cnt>=1){ //一直推到不符合条件为止 if (newS[left]=='*'){ cnt--; } left++; } count+=left; } //下面开始比较 if (count>=k){ //字符串中有效子字符串的总数大于或等于k ans = mid; //事先记录下答案 r = mid-1; //去尝试更小的 }else{ l = mid+1; } } return ans; } };接着来讲第二题：3296. 移山所需的最少秒数，先看题。看完题目了，先看一下我当时看的题解。这题属于是给我震惊到了。当时我看到题目的这个式子： workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x ，我第一时间想到的是去做一个前缀和，来处理1+2+3+...+x这个式子，然后后面就不知道该如何处理了。首先，这个式子是一个很经典的等差数列，根本用不着前缀和，只需要用最经典的x(1+x)/2的等差数列求和公式就行了。并且，我们二分的是答案——秒数。这个式子是算秒数的，如果你用前缀和，意味着你永远无法拆开这个式子，没法进行如题解一样的左右移项的操作，最终来达到化秒数这个结果成为能代入计算是否符合的变量。知道要拆开式子后，这道题目最后的难点就是处理上下限了。题解讲的很清楚了，此处不再赘述。class Solution { public: long long minNumberOfSeconds(int mountainHeight, vector<int>& workerTimes) { //1.先找上下界 long long maxTime=workerTimes[0]; for (auto x:workerTimes){ //这里枚举workerTimes是为了找到最大的时间，用于计算上界 if (x>maxTime){ maxTime=x; } } //2.开始二分答案 long long l=1,r=maxTime*mountainHeight*(mountainHeight+1)/2,minTime=r; //此处的r就是和题解一样计算上界 while (l<=r){ long long mid = l+(r-l)/2,total=0; for (auto x:workerTimes){ long long k=mid/x,sqr = floor(sqrt(8*k+1)); //按照题解的思路进行开方计算 sqr = (long long)floor(sqrt(8.0L*k + 1.0L)); //此处要注意上下取整的处理 total += (sqr - 1) / 2; //由于结果越大越好，为了确保合法性，我们选择下取整 if (total >= mountainHeight) break; // 剪枝 } if (total>=mountainHeight){ //经典的二分判断+结果记录 minTime=min(minTime,mid); r = mid-1; }else{ l = mid+1; } } return minTime; } };看来做算法题，有时候也不能局限于算法技巧，数学上的一些知识也是可以运用的。然后，来看看第三题：475. 供暖器，先看题。看完题目来看题解。这道题的题意还是比较好理解的，二分的目的性也很强，最主要的难点就是想出一个时间复杂度在O(n)之类的算法来验证我此次二分出来的半径是否合法。但是我怎么就是想不出来。题解的思路也是非常新奇：直接摆脱传统二分模板，外层遍历每一个屋子，然后使用二分找离每个屋子最近的供暖器，然后每个屋子都遍历过去，维护一个距离的最大值，就是我们所求的最小半径。看代码：class Solution { public: int findRadius(vector<int>& houses, vector<int>& heaters) { //1.升序排heaters sort(heaters.begin(),heaters.end()); //2.遍历房屋，二分找离每个屋子最近的供暖器 int maxRange=0; for (int i=0;i<houses.size();i++){ int target = houses[i],l=0,r=heaters.size()-1; while (l<=r){ //二分找的是供暖器，不是答案 int mid = l+(r-l)/2; if (heaters[mid]<target){ l = mid+1; }else{ r = mid-1; } } if (l==0){ //这里处理left停在数组第一个位置的情况 maxRange = max(maxRange,abs(heaters[l]-houses[i])); }else if (r==heaters.size()-1){//这里处理right停在数组最后一个位置的情况 maxRange = max(maxRange,abs(heaters[r]-houses[i])); }else{ //如果l和r都合法，那就取其中最小值，代表离的最近的取暖器，然后全局再维护一个最大值 maxRange = max(maxRange,min(abs(heaters[l]-houses[i]),abs(heaters[r]-houses[i]))); } } return maxRange; } };最后，我们来看第四题：3048. 标记所有下标的最早秒数 I，先看题。看完题目了吗？是不是感觉题意很晦涩难懂？那么先不急着看题解，看看我偷来的别人对题目很形象的改写：你有 n 门课程需要考试，第 i 门课程需要用 nums[i] 天复习。同一天只能复习一门课程。在第 i 天，你可以选择参加第 changeIndices[i] 门课程的考试。考试这一天不能复习。搞定所有课程的复习+考试，至少要多少天？带着这个改写，再去想想。如果还是想不出来，那就看看题解吧。这道题，虽说从框架上来看是经典的二分答案，但是判断这个天数够不够的过程还是非常反常规和难的。我对着这个题解写我自己的代码都费了好大一阵功夫。class Solution { public: bool check(vector<int>& nums, vector<int>& changeIndices,int maxDay){ //找出每个下标的最后位置 vector<int> last(nums.size(),0); for (int i=0;i<maxDay;i++){ last[changeIndices[i]-1]=max(last[changeIndices[i]-1],i+1); } //找出最靠后的下标位置，用于初步判断天数合法性 int maxPos=last[0]; for (auto x:last){ maxPos=max(maxPos,x); if (x==0){ return false; } } if (maxDay<maxPos) return false; //初步判断题目所给数组合法性 int cnt=0; for (int t=1;t<=maxDay;t++){ if (last[changeIndices[t-1]-1]!=t){ //如果不是考试日 cnt++; }else{ //如果是考试日 if (cnt<nums[changeIndices[t-1]-1]){ return false; } cnt-=nums[changeIndices[t-1]-1]; } } return true; } int earliestSecondToMarkIndices(vector<int>& nums, vector<int>& changeIndices) { if (nums.size()>changeIndices.size()) return -1; //1.确定上下界 int l=1,r=changeIndices.size(); //2.开始二分 int ans=-1; while (l<=r){ int mid = l+(r-l)/2; if (check(nums,changeIndices,mid)){ ans = mid; r = mid-1; }else{ l = mid+1; } } return ans; } };4.2 求最大 0828更新4.2.1 简介好久不见。也是14天没更新了，因为最近事情比较多，类似于同学聚餐，亲戚拜访之类的，并且人也不在状态上，加上这一批的题目比上批难了不知道多少，于是做题速度就极其慢。经过14天的磕磕绊绊，我也总算是把我目前知识能解决的题目给做出来了，下面给这些题目分分类。求最大的二分框架，我就不另外介绍了，套路基本一致，不清楚的直接去看上面的4.1.1，把ans=mid下面这行的r=mid-1换成l=mid+1，下面else分支的也相应换过来就行了。我将上面的题目分为以下几类(是我自己做题的主观感受，如果想要客观评价，上方图片的顺序就是由简单到难)：1.基础题(我能较快做出来)2226. 每个小孩最多能分到多少糖果 二分猜答案去直接遍历就行了，比较容易想到2.进阶题(我需要思考一下才能做出来)2576. 求出最多标记下标 这题我其实看提示了 需要想到匹配k个最小的数和k个最大的数之间的对应位置 不然做不出 此题会讲解2982. 找出出现至少三次的最长特殊子字符串 II 联动滑动窗口知识1898. 可移除字符的最大数目 需要手写一个逻辑去一个个匹配字母 以判断是不是子序列1802. 有界数组中指定下标处的最大值 此题卡O(logn)，强制你用等差数列求和公式去求和，找公式里面的首项、末项、项数三个参数非常麻烦，本来如果允许O(nlogn)，直接使用循环求值，边界会比较好找1642. 可以到达的最远建筑 基本逻辑不难：梯子留给最高的落差用，其他落差用砖块堆。但是要注意分类讨论细节3.困难题(我想不出来，看了题解才能做出来)275. H 指数 II 这题属于是看了题解能秒懂的类型：顺着题目的逻辑从小到大列举一下，就知道如何二分了 此题会讲解2861. 最大合金数 当时做的时候定式思维了，没反应过来二分是需要顺着题目的思路去验证是否正确，而是一边二分一边在那里尝试直接求出数量。如果脑子转过来了这题其实属于进阶题里面最难的一题 此题会讲解2071. 你可以安排的最多任务数目 这题是典型的贪心：用最强的k个工人去做最简单的k个任务，最好不嗑药就能做掉最简单的任务，实在不行要嗑药就做嗑药后能做的最难任务。贪心逻辑好理解，代码实际的实现略有难度 此题会讲解4.地狱题(我看了题解还得理解很久，才能彻底弄懂)2141. 同时运行 N 台电脑的最长时间 主要是得理解题解里面把电池电量当成连续的来用的思想 此题会讲解5.78题(题解里面需要用到我目前没掌握的，且难以快速掌握的知识解决题目，所以看了题解也无法做出)3007. 价值和小于等于 K 的最大数字 需要用到数位DP 后面学到了再来补2258. 逃离火灾 需要用到双数组 并且我bfs只是初学 并不是很熟练 陆陆续续尝试了三四个小时没做出来4.2.2 部分题目的讲解第一题：2576. 求出最多标记下标，先看题。先看是否符合二分要求：看到2 * nums[i] <= nums[j]这个式子，我们肯定想让左边的数字尽量小，右边的数字尽量大。这样配对后，剩下的数字会自然而然的越来越接近，也就是更难满足这个式子。所以配对的数量越多，越难达到这个条件，有单调性，可以二分。接着用贪心的思想思考：为了匹配的成功率更高，我们尽量将i指向最小的数字，j指向最大的数字。但是这样会存在浪费：原本我的nums[i]可以和更小的nums[j]匹配，此时如果拿去和最大的nums[j]匹配，这样会使得小的nums[j]更难与其他数字匹配，导致得到的不是最好的结果。那么我们该如何匹配呢？贪心的总思想是对的，左边数字要尽量小，右边数字要尽量大。我们只需解决这个浪费的问题就行：将最小的k个数和最大的k个数里面，内部相对排名相等的数进行匹配。换成代码语言，就是将nums[i]和nums[n−k+i]进行匹配。为啥这样行得通呢？举个反例，假设最小数和最大数全都可以相互匹配，但是如果我拿最小数里面第一小的数去和最大数里面第二小的数匹配，那么最小数里面第二小的数就不一定保证能和最大数里面第一小的数匹配上。从正面比较难解释，但是从反面还是可以解释一下的。基本原理就是避免了“大材小用，结果小材没法大用”所导致的匹配失败。class Solution { public: int maxNumOfMarkedIndices(vector<int>& nums) { //1.先排序 sort(nums.begin(),nums.end()); //2.二分找上下界 int l=0,r=nums.size()/2,ans=0; while (l<=r){ int mid = l+(r-l)/2; bool flag=true; for (int i=0;i<mid;i++){ if (nums[i]*2>nums[nums.size()-mid+i]){ //内部相对排名相等的数进行匹配 flag=false; break; } } if (flag){ ans = mid; l = mid+1; }else{ r = mid-1; } } return ans*2; } };接着进入困难区域。讲一下第二题：275. H 指数 II，先看题。在我的个人理解上，判断一个题目能否二分的标准，除了答案是否和某个变量存在单调性之外，还有就是：题目是否方便直接求出答案。这道题目的定义，至少 有 h 篇论文分别被引用了至少 h 次，是非常抽象的一个定义，我几乎想不到能如何直接求出一个答案。但是，我去验证我猜的答案对不对却十分简单：先讲论文引用次数升序排序，假设我猜h=x，那我只需要验证后x篇论文的第一篇的引用次数是否大于等于x就行了。毕竟引用次数是上升的，如果最大的x篇论文的第一篇的引用次数都>=x，那么后面的一定全都符合，这就说明x是合法的。言归正传，我们来正面推理一下为啥能用二分。先列举一下：如果我至少有4篇论文被引用的次数>=4次，那么我也至少有3篇论文被引用的次数>=3次，也至少有2篇论文被引用的次数>=2次，也至少有1篇论文被引用的次数>=1次，但是却不一定至少有5篇论文被引用的次数>=5次，属于是越小越容易合法的类型，具有单调性，可以二分。知道这一点后，二分写起来就不难了，甚至不需要写什么遍历的逻辑，一个判断即可。class Solution { public: int hIndex(vector<int>& citations) { int l=1,r=citations.size(),ans=0; while (l<=r){ int mid = l+(r-l)/2; if (citations[citations.size()-mid]>=mid){ //验证后`x`篇论文的第一篇的引用次数是否大于等于`x` ans = mid; l = mid+1; }else{ r = mid-1; } } return ans; } };接着来看第三题：2861. 最大合金数，先看题。看完题后，若有不会，看题解。这题和上一题我判断是否可以二分的“野方法”有异曲同工之妙：如果我要算出最多能制造的金属数量，我得考虑一大堆情况(我没看题解的时候就莫名其妙的朝这个方向去写了)，但是如果我猜个答案再去验证其对错，我只需要考虑要用哪台机器做就行了，我此时的花费就可以很简单的正向计算出来，最后看看有没有超出预算就行了。至于到底用哪台机器做，只需要遍历一下就行了，如果全都做不出来就是做不出来，如果有一台能做出来就直接退出，说明这个数量是可行的。至于单调性，这根本不需要推理，肯定是造的合金越多我的消耗越多，所以是一定有单调性的。class Solution { public: int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) { //1.寻找上下界 long long l=0,minStock=stock[0]; for (auto x:stock) minStock = min(minStock,(long long)x); long long r = budget+minStock,ans=0; // 这里的假设价格为1求上界我是真没想到，太妙了 //2.二分答案 while (l<=r){ long long mid = l+(r-l)/2,sum=0; bool flag=false; // 用于其中一台机器满足条件时提前退出，可以帮助循环外的二分框架判断是否符合条件，相当于check函数返回的结果 for (int i=0;i<composition.size();i++){ long long totalCost = 0; for (int j=0;j<composition[i].size();j++){ //先计算对于j种金属的数量需求 long long curDemend = composition[i][j]*mid; if (curDemend>stock[j]){ totalCost+=(curDemend-stock[j])*cost[j]; } } if (totalCost<=budget){ flag=true; break; } } if (flag){ ans = mid; l = mid+1; }else{ r = mid-1; } } return ans; } };来看第四题：2071. 你可以安排的最多任务数目，先看题。如果不会，看题解。正如我上面所说：这题是典型的贪心，用最强的k个工人去做最简单的k个任务，最好不嗑药就能做掉最简单的任务，实在不行要嗑药就做嗑药后能做的最难任务。贪心逻辑好理解，代码实际的实现略有难度。题解在代码的实现中，十分巧妙的运用了双端队列这个数据结构(c++中是deque，python中是collections.deque，go中只能使用切片模拟)。将一个指针独立外置，然后将嗑药能完成的任务从小到大加入这个队列，退出循环时指针自动就停在了下一次可以开始的位置。如果要嗑药就取出队尾，如果正常弄就取出队首。并且队列可以一直循环使用，只需要一直取队首和队尾就行了，十分的巧妙。如果没想到这个结构(我刚看完题解思路准备去写的时候就没想到这个结构)，只能尝试使用遍历等方法，这样不但写起来麻烦，时间复杂度也会上升一个等级。class Solution { public: bool check(int k,vector<int>& tasks, vector<int>& workers, int pills, int strength){ int m=workers.size(),j=0; deque<int> q; for (int i=m-k;i<m;i++){ //将这个工人能做的所有任务（包括嗑药）加入队列 while (j<k && tasks[j]<=workers[i]+strength){ q.push_back(tasks[j]); j++; } if (q.empty()) return false; //在访问队列之前务必检查是否空 如果此处为空 说明这个工人没有能做的任务 if (q.front()<=workers[i]){ //不嗑药能做最简单的任务 q.pop_front(); }else if (pills>0){ //还有剩下的药，那就嗑药 q.pop_back(); //然后做能做的最难的任务 pills--; }else{ return false; } } return true; } int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) { //1.排序 sort(tasks.begin(),tasks.end()); sort(workers.begin(),workers.end()); int l=0,r=min(tasks.size(),workers.size()),ans=0; while (l<=r){ int mid = l+(r-l)/2; if (check(mid,tasks,workers,pills,strength)){ ans = mid; l = mid+1; }else{ r = mid-1; } } return ans; } };最后，我们来到了地狱难度。第五题：2141. 同时运行 N 台电脑的最长时间，先看题。如果不会，看题解。这题的核心在于理解题解中当 n⋅x≤sum 成立时，必然可以让 n 台电脑同时运行 x 分钟。这句话。我的语言表达能力并不是很好，在我表达我的看法之前，先让最新的GPT-5帮我解读一下：这题的核心想法很简单：把“允许换电池”的灵活性，等价成“可以把所有电池的电量像水一样切分并串起来使用”，但注意每块电池在同一时刻只能供给一台电脑。这就引出了一个非常干脆的判定条件。一、把判定条件说清楚如果我们打算让 n 台电脑同时运行 x 分钟，那么任何一块电池最多只能贡献 x 分钟（电量超过 x 的部分在这次目标里用不上，相当于被“截断”）。因此所有电池最多能贡献的总“有效电量”是 sum(min(bi, x))。想要 n 台电脑各跑 x 分钟，总需求是 n·x。必要条件：sum(min(bi, x)) ≥ n·x。没有这么多“有效电量”，肯定不可能。二、为什么这个条件也是充分的（关键点）把电池按是否 ≥ x 分两类来构造一个可行的调度（只需说明存在性，不要求真的输出过程）：1) 大电池（bi ≥ x）每块这样的电池可以独立给一台电脑供满 x 分钟。把它们一一分给不同的电脑，这样“占满”的电脑不再需要其他电池。2) 小电池（bi < x）设大电池用了 k 台电脑，还剩 n' = n − k 台电脑没满。把剩下所有小电池（它们的总和记作 sum'）串起来给这 n' 台电脑：给第 1 台从一堆小电池中接一块用完再换下一块，直到累计到 x 分钟；再给第 2 台如法炮制……依次类推。这种“串电池”的方式不会出现“同一时刻同一电池被两台电脑同时用”的问题，因为每块小电池本身耗尽前持续供电时间 < x，我们可以把任何“一个电池同时贡献给两台电脑”的时间段，向时间轴两端推移为“先贡献给前一台的末尾、再贡献给后一台的开头”，从而避免重叠。数学上，有 sum' = sum(min(bi, x)) − k·x。由 sum(min(bi, x)) ≥ n·x 可得 sum' ≥ n'·x。小电池总量足以把剩下的 n' 台电脑也各补到 x 分钟。这就证明了：只要 sum(min(bi, x)) ≥ n·x，就一定能排出一个不同时共享同一电池的调度，让 n 台电脑同时运行 x 分钟。充分性成立。三、因此可以二分答案单调性：如果能同时跑 x 分钟，那一定能跑更短的时间，所以“可行时间”关于 x 是单调的。二分检查：给定 x，检查 sum(min(bi, x)) ≥ n·x 是否成立即可。边界：左边界 l=0 一定可行。右边界 r=⌊sum(batteries)/n⌋+1 一定不可行（因为即使用上全部电量，平均每台也撑不到 r）。用开区间二分保持不变式：“l 可行，r 不可行”，直到收敛。四、用样例直观验证示例1：n=2, batteries=[3,3,3]试 x=4：sum(min(3,4))*3=9，n·x=8，9≥8 成立，所以 4 可行。试 x=5：sum(min(3,5))*3=9，n·x=10，不成立，所以 5 不可行。最大可行是 4。示例2：n=2, batteries=[1,1,1,1]试 x=2：sum(min(1,2))*4=4，n·x=4，成立。试 x=3：sum=4，n·x=6，不成立。最大可行是 2。五、实现要点与复杂度判定函数就是一次线性遍历：累加 min(bi, x)，检查是否 ≥ n·x。Python 代码里用 sum(batteries)//n+1 做右边界，二分时每步 O(m)，总复杂度 O(m log U)，U≈sum/n。其他语言注意用 64 位整型承载求和与乘法，避免溢出。六、把题解里“难点句子”翻译成直白话“每个电池的使用时间至多为 min(bi, x)”：因为我们只关心是否能撑到 x 分钟，多出来的电量对这次目标无用，直接“截掉”不影响可行性判断。“小电池串起来供电不会冲突”：因为每块小电池自身供电时长 < x，把它对两台电脑的供电安排成先后相接的时间段即可，不会出现同一时刻一电池供两台电脑。“sum' ≥ n'·x 就能补满剩下的电脑”：既然总小电池量足够，就可以按“用完一块换下一块”的方式逐台凑到 x 分钟。这就是这道题的核心逻辑：把“换电池”的灵活性抽象为“截断+串接”的可分配模型，判定式 sum(min(bi, x)) ≥ n·x 既必要也充分，从而用二分搜索到最大 x。它讲的已经非常明白了。我再来一句话概括：这个解法的核心就是，我就用x分钟，那么n台机器需要的总电量就是nx，再将每个电池真正能利用的电量累加起来，如果比它大，那就可以同时运行x分钟。除此之外不管别的。看懂题解后，其实实行起来不难。因为我只需要计算一个式子，我们讲这么多主要是为了理解为啥这个式子是对的。class Solution { public: long long maxRunTime(int n, vector<int>& batteries) { long long l=1,ave=0; for (auto x:batteries) ave+=x; ave/=n; long long r=ave+1,ans=0; while (l<=r){ long long mid = l+(r-l)/2,sum=0; for (auto x:batteries) sum+=min((long long)x,mid); //按照题解的思路来计算有效总电量 if (mid*n<=sum){ //按照题解的式子来判断 ans = mid; l = mid+1; }else{ r = mid-1; } } return ans; } };4.3 求间接值 0908更新这种类型题目的核心就是，不直接二分答案，而是去直接二分和答案有相近关系的值。这次的题目不多，难度都是中等，第二题比第一题略难，我将一一讲解。先看第一题：3143. 正方形中的最多点数。这题看似要求的是点数，实则这个点分布在二维空间中，并不方便量化。我们可以转而去二分正方形的边离中心点(0,0)的距离：这个距离越长，进来的点越多，越容易出现重复的点，并且这个距离和点的数量有不减的关系，并且有单调性，可以二分。至于如何判断是否出现重复，直接使用map映射自动去重，并对比map长度和点的个数即可。class Solution { public: int maxPointsInsideSquare(vector<vector<int>>& points, string s) { int maxXorY=0; //开局找上下界 for (auto x:points){ for (auto y:x) maxXorY=max(maxXorY,abs(y)); } int l=0,r=maxXorY,ans=0; while (l<=r){ int mid = l+(r-l)/2,cnt=0; map<char,int> hash; for (int i=0;i<points.size();i++){ if (abs(points[i][0])<=mid && abs(points[i][1])<=mid){ //在正方形范围内 hash[s[i]]++; cnt++; } } if (hash.size()<cnt){ //如果哈希长度小于点的个数 r = mid-1; //说明重复，我要缩小正方形，才能更容易接近答案 }else{ ans = cnt; //记下答案 l = mid+1; //去扩大正方形 } } return ans; } };接着看第二题：1648. 销售价值减少的颜色球。这题比较有难度，是贪心和二分的结合。如果不会做，可以先看提示，再看题解。题解可能难以理解，下面是经过GPT-5详细解读后的题解的思路：下面我分几个层次来帮你彻底吃透这份题解与算法思想：一、题意再精炼理解有若干颜色的球，每种颜色 i 初始有 inventory[i] 个。顾客买球（总共 orders 个），某种颜色当前还剩 c 个时，再买走 1 个该颜色球的价值 = c。也就是：对某个颜色的库存 a，当我们依次卖出它，会得到的价值序列是 a, a-1, a-2, ..., 1。想要最大化总价值 => 永远优先卖“当前剩余最多的那堆”的球（贪心直觉）。所以本质是在不断从“最高的柱子”削减。但是直接用一个最大堆每次取最高值卖 1 个会超时（orders 可达 1e9）。需要“批量”卖。二、关键贪心结构化：把所有颜色“削平”到某个高度 k设最终我们找到一个阈值 k，满足：所有初始高度 > k 的部分（也就是每堆从高度 x 降到 k）都被完全卖掉。还需要再卖一些价值为 k 的球（来自那些原本 ≥ k 的堆），数量可能是 0 到某个余量。为什么这样的结构一定存在并且是最优？因为如果有一颗价值 > k 的球没卖，却卖了价值 = k 的球，这是不可能是最优的（可交换 argument）。所以最优解中，卖出的球的价值集合形状：从某个最大值一路“密集”下到 k+1 全部卖出，再在 k 这个价位卖出一部分。于是问题转化为：找到一个最小的 k，使得“所有 > k 的层” 的球数总和 ≤ orders，而“所有 > k-1 的层” 的球数总和 > orders。也就是：sum(max(0, x - k)) ≤ orderssum(max(0, x - (k-1))) > orders三、二分 k 的单调性依据定义 f(k) = sum(max(0, x - k))，表示如果把所有高度 > k 的柱子削到 k，需要卖出的球数。显然：k 越大，每个 (x - k) 越小 => f(k) 单调不增。我们想找“最小的 k，使 f(k) ≤ orders”。这就是典型的单调条件二分。代码里：l = 0, r = max(inventory)mid = (l + r)>>1s = f(mid)如果 s > orders，说明削到 mid 仍用掉太多球（比允许卖的多），要“削少一点” => 即提高 k（l = mid + 1）否则 s ≤ orders，说明 k 还可以再小一点（让价值更高） => r = mid - 1循环后 l 即所求最小 k。四、找到了 k 之后如何算答案先把所有 x > k 的柱子从 x 一路卖到 k+1。这一段对单个柱子贡献的价值：x + (x-1) + ... + (k+1)是一个等差数列，项数 = x - k和 = ( (x) + (k+1) ) * (x - k) / 2= (x + k + 1)*(x - k)/2上面这些全部卖出后，卖掉的总数量 sold_high = sum(x - k for x>k)还需要卖 rest = orders - sold_high 个价值 = k 的球（这些来自那些原本 ≥ k 的堆，数量肯定够，因为如果不够，k 就不会是二分得到的最小满足值）。答案 = 高于 k 的那些“梯形块”总和 + rest * k最后取 mod。五、代码里几个容易迷惑的点为什么最终 k = l 而不是 r？因为我们找的是“最小使 f(k) ≤ orders 的 k”，典型的“下界”二分模板，循环结束时 l 指向第一个满足条件的位置。为什么 sum 用的是 x - mid 而不是 (mid - x)？因为只对 x > mid 的堆需要削减，削掉的层数正是 x - mid，每层一个球。为什么计算 rest 时再次用 sum(x - k for x>k)？因为 sold_high 是真正卖掉的“价值 > k”球的数量；不能用 mid 版本的 s（因为 mid 最终不是 k，k 是二分后的 l）。range_sum(k+1, x) 的推导：range_sum(a, b) = (a + b)*(b - a + 1)/2这里 a = k+1, b = x=> (k+1 + x) (x - (k+1) + 1)/2 = (k+1 + x)(x - k)/2 = (x + k + 1)*(x - k)/2与注释一致。为什么要“k 尽可能小”？因为 f(k) ≤ orders 保证能卖足 orders 个球；在满足数量的所有 k 中，k 越小说明我们越多地使用了高价值层（等差数列的起点更高），总价值自然更大。六、用一个具体例子手动演示（inventory = [2,5], orders = 4）inventory = [2,5], 最大 5试 mid：mid=2: f(2) = (5-2)=3 ≤ 4 => r = 1 (想再小一点)mid=0: f(0) = (2-0)+(5-0)=7 > 4 => l = 1mid=1: f(1) = (2-1)+(5-1)=1+4=5 > 4 => l = 2循环结束: l=2 => k=2sold_high = sum(x - 2 for x>2) = (5-2)=3rest = 4 - 3 = 1高层收益：从 5 降到 3 的价值 5+4+3 = 12rest=1 个价值 = k = 2 的球 => 12 + 2 = 14七、复杂度分析二分次数：log(max(inventory[i]))，最大约 log(1e9) ≈ 30每次二分内做一次 O(n) 遍历 => 总 O(n log M)，n ≤ 1e5，可接受。空间 O(1) 额外。八、可能的优化 / 其他思路排序 + 分层批量卖（不需要二分）：将库存排序，从最大往下，与次大之间的“高度差”乘以“有多少堆达到这个高度”就是可批量卖的层数。类似“削峰”法，一层层大块卖，直到 orders 用完。每次处理一段高度区间，利用等差数列一次结算。复杂度 O(n log n) 或 O(n)（如果用计数结构）。最大堆 + 批次：取最大值 c 和次大值 d（若不存在则 d=0），可以一次性卖 min(orders, c - d) 层。但每次需要 log n 调整堆，仍然可行，但实现较繁琐。本题所用“二分 k”法思路清晰，代码简洁，是常见高频写法。九、常见易错点把等差求和上/下限写错（注意是卖到 k+1 停）。rest 计算用错（要用最终 k 重新算）。没有用 long / Python int（在别的语言里可能溢出）。忘记取模或在中间取模导致负面影响（本题可最后统一取模）。十、代码再加详细注释版本class Solution: def maxProfit(self, inventory, orders): mod = 10**9 + 7 # 二分找最小 k 使得 sum(max(0, x - k)) <= orders l, r = 0, max(inventory) while l <= r: mid = (l + r) >> 1 s = 0 # 计算把所有 > mid 的堆削到 mid 需要卖多少球 for x in inventory: if x > mid: s += x - mid if s > orders: # mid 太小，削掉的数量太多，提升 k l = mid + 1 else: # mid 可以满足，尝试更小 r = mid - 1 k = l # 最小可行阈值 # 先统计“价值 > k”的那些球的总数（已经确定全卖掉） sold_high = 0 ans = 0 for x in inventory: if x > k: cnt = x - k # 卖出的数量（层数） sold_high += cnt # 卖出的价值：x + (x-1) + ... + (k+1) # 等差数列和 = (首 + 尾) * 项数 / 2 ans += (x + (k + 1)) * cnt // 2 # 还需要从价值 == k 的层卖 rest 个 rest = orders - sold_high ans += rest * k return ans % mod十一、如何直觉理解“让 k 越小越好”假设存在两个可行阈值 k1 < k2，且都满足 sum(max(0, x - k)) ≤ orders。使用 k2 的方案：你卖掉所有高于 k2 的层 + 一些 k2 层。如果改成 k1：你会多卖掉一些更高价值的层（介于 k1+1 和 k2 之间），而少卖一些价值较低的 k2 层或 k1 层。总价值一定不降。所以要最小的可行 k。十二、与优先队列贪心的等价性优先队列写法等价于“每次取最高的柱子往下砍”，二分法则是把这个过程整体“压缩”，直接找到最终平衡点 k，再一次性结算各段高度贡献。十三、总结一句话通过二分确定“最终统一削到的高度 k”，把所有比 k 高的部分整段算等差数列，剩下不够的再用 k 补齐，数学求和 + 模即可。如果你还想看“分层批量卖”的另一种实现方式，或想让我对比两种写法的具体操作步骤，也可以继续问我。如果上面某一段还有不清晰的地方，告诉我你卡在哪里，我再针对性补充。AI讲的真的很不错。我就不补充了。下面是我的ac代码：class Solution { public: int maxProfit(vector<int>& inventory, int orders) { //1.找上下限 long long l=0,r=0,mod=1000000007,ans=0; for (auto x:inventory) r = max(r,(long long)x); while (l<=r){ long long mid = l+(r-l)/2,cnt=0; __int128_t sum=0; //开int128防止溢出 for (int i=0;i<inventory.size();i++){ if (inventory[i]>=mid){ cnt+=inventory[i]-mid; //我这里的思路和题解略有不同，我是在二分里面直接就算钱了 sum+=(__int128_t)(mid+1+inventory[i])*(__int128_t)(inventory[i]-mid)/2; } } if (cnt>orders){ l = mid+1; }else{ sum += (orders-cnt)*mid; ans = sum; r = mid-1; } } return ans%mod; } };4.4 最小化最大值 0924更新4.4.1 简介经过两个星期的艰难前行，经历各种大大小小的事情，在开学后我刷题的时间比暑假在家减少了一些。前些天刚刚去考了第39次ccf csp认证，也是喜提当次前7%的好成绩（比我上次前60%进步了53%，高于我们实验班大三上结束之前达到前30%的硬性要求），也是终于可以专心准备面试算法了。那么在开始讲解题目之前，我先来讲讲：啥是最小化最大值？你可以理解成，我二分出来的mid是上界，然后我在check的过程中，确保经过某种处理后，所有元素都不超过mid这个上界，如果符合，我就再把mid通过二分压低；如果不符合则反之。这就是最小化最大值。下面的图片讲的也很形象：好比用一个盖子压住最大值，看看能不能压住。为何有些题目我没做呢？像2064这种题目，就是没学习到相关数据结构的知识；3399和3605则是我连题解也无法理解，也是缺乏相关知识的学习。后续如果学习到了相关知识，有机会的话，会回来补的（可能优先去做hot100了也有可能）。下面是我本人对本次题目的主观上的难度排序：1.基础题(我能较快做出来)没有2.进阶题(我需要思考一下才能做出来)410. 分割数组的最大值 最小化最大值题型的入门题，是第一道门槛1631. 最小体力消耗路径 1948 结合BFS考察，需要想到：如果差值大于mid就将其当成无法跨越的障碍，然后BFS寻路看能否到达终点(讲解)1760. 袋子里最少数目的球 1940 需要想到用除法运算来算出分隔操作的次数，并且正确处理能/不能整除的场景2064. 分配给商店的最多商品的最小值 1886 和1760思路类似，使用向上取整的整除来算出这一批商品能分到的店的数量，最后和实际店铺数量对比(讲解)2560. 打家劫舍 IV 2081 考察01-DP，只偷金额小于等于mid的房间，使用dp记录当前偷取的房间数量，最终和k对比得出结论(讲解)778. 水位上升的泳池中游泳 2097 考察BFS，由于可以瞬时无限移动，所以只需要等mid秒后再出发即可，将大于mid的格子作为障碍3.困难题(大体思路正确，但是需要纠正一些细节后才能做对)2439. 最小化数组中的最大值 1965 这题需要想到，加一减一的操作本质上就是将后面的超出mid的数全部向前堆积到下标0的位置，只需要判断下标0位置的元素最终是否<=mid即可(讲一些注意的点)2616. 最小化数对的最大差值 2155 总体思路就是先排序，取前后相邻的下标，然后使用哈希记录使用过的下标，然后判断是否取够了数量(讲解)3419. 图的最大边权的最小值 2243 考察BFS和反图，先构造反图，然后bfs时不经过大于mid的边权，看能否访问到全部节点。这题力扣还会卡我时间4.地狱题(我看了题解还得理解很久，才能彻底弄懂)(一笔带过)2513. 最小化两个数组中的最大值 2302 纯纯的数学题目，需要掌握辗转相除法(讲解)LCP 12. 小张刷题计划 用贪心的思路将当前区间内最耗时间的题目交给小刘解决，然后还得处理天数的边界5.78题(题解里面需要用到我目前没掌握的，且难以快速掌握的知识解决题目，所以看了题解也无法做出)3613. 最小化连通分量的最大成本 约 1900 涉及并查集相关知识点，我尚未学习到3399. 字符相同的最短子字符串 II 2376 题解使用了最大堆/分桶优化，比较难以理解3399. 字符相同的最短子字符串 II 2376 题解使用了LogTrick / 栈，比较难以理解4.4.2 开始讲解！首先来到本次讲解的第一题：1760. 袋子里最少数目的球，先看题。提取题目要素：你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。这是最大化最小值的特征。首先，看到题目的第一想法，肯定是用循环模拟将球一个一个放进去。但是这样时间复杂度会爆炸，所以转而很容易会想到用除法来计算这一种类的球需要分隔几次才能低于mid：cnt += nums[i] / mid;。满怀期待去运行，结果直接答案错误——漏考虑了mid能把nums[i]整除的情况。如果能整除，那么操作的次数就需要-1(例如把6分割成3和3，6/3=2，但是实际只需要分割一次)，也就是：cnt += nums[i] / mid - 1;。至此，题目的具体逻辑就是这样的。class Solution { public: int minimumSize(vector<int> &nums, int maxOperations) { int l = 1, r = nums[0], ans = 0; for (auto x: nums) r = max(r, x); while (l <= r) { int mid = l + (r - l) / 2; //每份球的数量 long long cnt = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] > mid) { if (nums[i] % mid == 0) { //如果能整除 cnt += nums[i] / mid - 1; } else { //如果不能 cnt += nums[i] / mid; } } } if (cnt > maxOperations) { //如果分隔的总次数比允许的最多操作次数多 //说明压的太低了 l = mid + 1; } else { r = mid - 1; ans = mid; } } return ans; } };接下来来到第二题：2560. 打家劫舍 IV，先看题。从这里开始，我就基本不会讲二分了，只讲如何实现check()函数。好好好久不见的DP也是终于返厂了。先看题目要素：小偷 不会窃取相邻的房屋->使用DP，在每一步操作分类讨论偷还是不偷，并将结果一直传递下去；窃取能力是能从单间房屋中窃取的 最大金额，需要返回小偷的 最小 窃取能力 ->最小化最大值。那么该如何使用DP呢？我们建立一个二维数组dp[n][2]来存储小偷偷的房间数量，其中dp[i][0]表示不偷这间房屋，dp[i][1]表示偷这间房屋。根据题意，小偷不能偷相邻的两间房屋，所以如果他偷了上一间房屋，这一间房屋就不能偷。因此，这一间房屋如果要偷，物品价值必须<=mid，确保压住物品金额的上限，并且只能继承上一间房屋没偷的状态，也就是dp[i][1]=dp[i-1][0]+1；如果不偷这间房屋，那么上一间房子偷不偷都行，为了确保小偷偷的房间数量尽量多(需要>=k)，直接选择继承上一个房间的最大值就行，即dp[i][0]=max(dp[i-1][0],dp[i-1][1])。题目基本的逻辑就是这样，见代码：class Solution { public: bool ok(vector<int> nums, int mid, int k) { vector<vector<int> > dp(nums.size(), vector<int>(2, 0)); //初始值必须是0，因为下面如果偷不了某个房间，会直接忽视dp[i][1] if (nums[0] <= mid) dp[0][1] = 1; for (int i = 1; i < nums.size(); i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); //如果本次不偷 if (nums[i] <= mid) dp[i][1] = dp[i - 1][0] + 1; //如果本次偷，物品的价值必须<=mid，确保压住上限 } if (max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]) >= k) return true;//如果最终偷到的房间数量达到了k return false; } int minCapability(vector<int> &nums, int k) { int l = nums[0], r = nums[0], ans = 0; for (auto x: nums) { l = min(l, x); r = max(r, x); } while (l <= r) { int mid = l + (r - l) / 2; if (ok(nums, mid, k)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } return ans; } };接下来来看第三题：778. 水位上升的泳池中游泳，先看题。提取要素：走格子->bfs/dfs；每个格子在特定时间后解锁->时间越往后越容易走通->时间需要能压住路径上的时间的最大值->要求时间最短->最小化最大值。所以这题，如果你是单独刷到，不是这一系列题目的连贯练习，可能想到用最小化最大值去做比较有难度。怪不得我感觉这题目做着不难，却是hard水平。这时候就能体现二分查找的魅力时刻了：正向去做需要用到堆和并查集的知识，而二分查找只需要直接去猜时间是多少，然后用bfs去验证是否可达就行了。题目有一个很关键的条件：假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。这说明，我可以放心去猜时间，放心去bfs，因为只要当前猜测的时间下，路径通了，就能到达。所以思路明了了：猜一个时间，然后将时间大于mid的方块当成障碍，去bfs/dfs判断是否能到达终点即可。这里我用的是bfs，因为不是很喜欢写递归。bfs还不会的可以移步我的另一个算法笔记。class Solution { public: bool canReach(vector<vector<int> > &grid, int time) { vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; int n = grid.size(); queue<pair<int, int> > q; vector<vector<int> > dist(n, vector<int>(n, -1)); q.emplace(0, 0); dist[0][0] = 0; while (!q.empty()) { //取出队首 auto [x,y] = q.front(); q.pop(); if (x == n - 1 && y == n - 1) { return true; } for (int d = 0; d < 4; d++) { int nx = x + dx[d]; int ny = y + dy[d]; //检查合法性 if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; //将大于当前时间的格子当成障碍 if (dist[nx][ny] != -1 || grid[nx][ny] > time) continue; //合法，加入队列接着扩散 q.emplace(nx, ny); dist[nx][ny] = dist[x][y] + 1; } } if (dist[n - 1][n - 1] != -1) return true; return false; } int swimInWater(vector<vector<int> > &grid) { int n = grid.size(), ans = -1; int l = max(grid[n - 1][n - 1], grid[0][0]), r = 0; for (auto x: grid) { for (auto y: x) { r = max(r, y); } } while (l <= r) { int mid = l + (r - l) / 2; if (canReach(grid, mid)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } return ans; } }; 这下真是二分查找魅力时刻了：二分+某基础算法，能创造很多可能。我们接着来第四题：2616. 最小化数对的最大差值，先看题。先讲一讲思路：将数组排序，这样两个相邻的元素一定是差值最少的，然后二分猜值，如果当前相邻元素没取过，并且差值<=mid，则计数器加一，将这两个元素的下标放入哈希表中，用于去重。这个哈希表在cpp中是啥呢？是map吗？不是。map是基于红黑树实现的，查询的时间复杂度需要O(logn)。真正的哈希表是以unordered_开头的容器，详情见下表：容器名类型底层原理插入/删除查找访问最小/最大备注std::set集合红黑树（平衡二叉树）O(log n)O(log n)O(log n)自动排序，唯一std::unordered_set集合哈希表O(1)O(1)不支持无序，唯一std::multiset集合红黑树（平衡二叉树）O(log n)O(log n)O(log n)自动排序，可重复std::unordered_multiset集合哈希表O(1)O(1)不支持无序，可重复std::map映射红黑树（平衡二叉树）O(log n)O(log n)O(log n)自动排序，唯一键std::unordered_map映射哈希表O(1)O(1)不支持无序，唯一键std::multimap映射红黑树（平衡二叉树）O(log n)O(log n)O(log n)自动排序，可重复键std::unordered_multimap映射哈希表O(1)O(1)不支持无序，可重复键所以为啥我会突然提起这个呢？因为这道题，我第一次提交的时候，我使用map来去重，结果超时了。询问ai后，我改成了unordered_set，直接不超时了。最根本的原因是：前者访问元素的时间复杂度为O(logn)，而后者是O(1)。贴一下ac代码：#include <bits/stdc++.h> using namespace std; class Solution { public: bool ok(vector<int> nums, int mid, int p) { unordered_set<int> used; //这里使用无序集合去重，访问的时间复杂度O(1) int cnt = 0; for (int i = 0; i < nums.size() - 1; i++) { if (nums[i + 1] - nums[i] <= mid && used.count(i + 1) == 0 && used.count(i) == 0) { cnt++; used.emplace(i + 1); used.emplace(i); } } return cnt >= p; } int minimizeMax(vector<int> &nums, int p) { int l = 0, r = 0, ans = -1; sort(nums.begin(), nums.end()); r = nums[nums.size() - 1] - nums[0]; while (l <= r) { int mid = l + (r - l) / 2; if (ok(nums, mid, p)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } return ans; } }; 接下来来看第五题：3419. 图的最大边权的最小值，先看题。要素提取：最大边权的最小值->最小化最大值；所有其他节点都可以到达节点 0 ->搜索(bfs/dfs)。刚刚看到题目，我就有个疑问：这个threshold有啥用？我操作是只会删边，不会增边的，限制我这个干啥？直觉告诉我，我不需要管这个，后来在做完题目后，也证实了：确实是个多余的条件。在后面我会分析为什么。好了，接着着手题目本身。它要求最大边权值尽可能小，说明我得二分一个mid，然后把>mid的边都删除了，然后再判断是否所有节点都能到达0节点。结果超时。好的，进行第一波优化：删除边(erase)的操作时间复杂度O(n)，太慢了。于是，我改成直接访问这个图，不走>mid的边。结果还是超时。然后，第二波优化：判断所有点能否到0太慢了，得先做反图(将原图a->b的关系全部改成b->a)，然后从0开始bfs，判断是否经过了所有节点，这样能快一个数量级。结果还是超时。没招了，我问ai，ai说：你这版 TLE 的最大元凶是这个函数签名： bool check(vector<vector<vector > > rev, int mid, int n)这里把 rev 按值传递了！每次二分 check 都会把整张反图深拷贝一遍（外层 vector 拷贝、每个邻接表 vector 拷贝、每条边的小 vector{to,w} 也拷贝）。这直接把每次检查从 O(V+E) 拉到 O(V+E) + O(E) 的大常数，数据大时必超时。行，第三遍优化：我把函数头部加上static const，变量传递也全部都是引用传递，避免拷贝，然后把原本的三维数组改成了更轻量的以pair<int,int>为基的二维数据。终于通过了。sb力扣我漕你冯福经过这么一番折腾，我们可以总结出这道题目的做法：mid猜边的最大值，然后制作反图，从0开始做无目标的bfs，不走>mid的边，看看能否经过所有节点。只有这个反图的优化我认同，其他的我都不认同，纯纯评测系统故意卡的。来看我精装修后的代码：class Solution { public: static bool check(const vector<vector<pair<int, int> > > &rev, const int mid, const int n) { vector<bool> used(n, false); queue<int> q; q.emplace(0); used[0] = true; //记录是否使用过 int seen = 1; while (!q.empty()) { //先取出队首 int cur = q.front(); q.pop(); //由于是无目标bfs，所以这里不需要检验是否到终点 //等全部能访问的节点都访问完之后，队列自然会空，bfs自然会停止 for (auto newNode: rev[cur]) { if (used[newNode.first] || newNode.second > mid) continue; q.emplace(newNode.first); used[newNode.first] = true; seen++; if (seen == n) return true; } } return seen == n; } int minMaxWeight(int n, vector<vector<int> > &edges, int threshold) { //1.先构建反图 vector<vector<pair<int, int> > > rev(n, vector<pair<int, int> >()); for (int i = 0; i < edges.size(); i++) { rev[edges[i][1]].emplace_back(edges[i][0], edges[i][2]); } //2.开始二分 int l = edges[0][2], r = l, ans = -1; for (const auto x: edges) { l = min(l, x[2]); r = max(r, x[2]); } while (l <= r) { int mid = l + (r - l) / 2; if (check(rev, mid, n)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } return ans; } }; 最后来讲讲为啥不需要管threshold。我们这道题对于边权的追求是越小越好，而我们的追求越小，被删除的边就会越多，这样就越能符合threshold的条件。如果我删除到无法联通的情况下，threshold还是不达标，说明这个用例是无赖用例，没有任何意义。所以，最好的办法就是不管这个threshold，这是合理的。接着，我们来讲第六题：LCP 12. 小张刷题计划，先看题。要素提取：每天的做题时间中耗时最多的是T->求最小的T->最小化最大值。并且题目里面有一个机制：每天小张可以挑选任意一道题目找小刘解决，相当于直接减去这道题目的时间。所以，从贪心的角度，我们能很容易想到尽量将每天最耗时间的题目给小刘做，这样才能最大程度压低每天的总时间。这样，我们就形成了代码的雏形：二分猜每天最多的时间mid，然后for循环累加每天的题目同时维护最大值，如果总和+题目耗时最大值已经超过了mid，说明我就算给小刘做最大的题目也无法小于等于mid了，所以这一天必须得结束了，就将天数减一。超出的这个题目只能留给明天做了，所以重置累加器和最大值为当前题目耗时。当然，由于都会有一道题目要留给明天做，所以如果天数为最后一天的时候触发了这个条件（总和+题目耗时最大值超过mid），就说明这个mid压不住了，因为已经是最后一天了，哪来新的“下一天”。这就是我在上面题目列表简介列表旁边所说的边界。代码如下，有详细注释：#include <bits/stdc++.h> using namespace std; class Solution { public: bool ok(int &mid, vector<int> &time, int m) { int sum = 0, maxTime = time[0]; for (int i = 0; i < time.size(); i++) { sum += time[i]; //累加每道题的时间 maxTime = max(maxTime, time[i]); //维护一个做题时间的最大值 if (sum > mid + maxTime) { //如果请小刘来也没达到我们mid的要求 if (m > 1) { //如果还有“明天” m--; //天数减一 sum = time[i]; //重置累加和为当前时间，留到明天做 maxTime = time[i]; //重置最大时间为当前时间 } else { //如果是最后一天 return false; //说明这个mid的要求不得行 } } } return true; } int minTime(vector<int> &time, int m) { int l = 0, r = 0, ans = -1; for (auto x: time) r += x; while (l <= r) { int mid = l + (r - l) / 2; if (ok(mid, time, m)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } return ans; } };4.5 最大化最小值 1020更新4.5.1 简介这次的题目也是非常有难度，再加上国庆节玩了8天，这八天一天都没刷题，导致了我过了好久才软磨硬泡的把这些题目弄完。本次做题情况如下:和4.4一样，有一些我没做的题目是因为涉及到了更高深的知识（依旧是并查集）。只要是我现有知识能解决的题目，我都会去尝试把它做掉。下面来分析一下本次题目的难度，划分一下讲解顺序：1.基础题(我能较快做出来)没有2.进阶题(我需要思考一下才能做出来)3281. 范围内整数的最大得分 1768 思路没啥特别的，看代码能比较容易回想起来，算是最大化最小值的入门题吧（可能略难）2517. 礼盒的最大甜蜜度 2021 也是经典思路：排序价格，然后代入二分的答案去试是否某个糖果的价值-上个糖果的价值>=mid，然后计数器计数，最终比较这样选出来的糖果数量是否达到了要求1552. 两球之间的磁力 同 2517 题 确实，和上面这道题思路一模一样，没啥好说的3.困难题(大体思路正确，但是需要纠正一些细节后才能做对)(讲解)2812. 找出最安全路径 2154 此处学习到了新知识：多源bfs。这题用了2次bfs：一次是多源bfs用于确定每个格子到最近小偷的距离，一次用于判断是否能在给定mid下到达终点(讲解)3449. 最大化游戏分数的最小值 2748 此题极其烦人。可以当成那种现场手撕的题目，因为没啥算法可以套用。具体做法后面讲4.地狱题(我看了题解还得理解很久，才能彻底弄懂)(讲解)2528. 最大化城市的最小电量 2236 这题的难度还是比较地狱的。需要用前缀和来快速计算每个城市所接收到的能量，然后再用差分数据来快速更新一串城市之间的最新电量。后续思路在后面讲解。(讲解)3464. 正方形上的点之间的最大距离 2806 此题也是私募了。有很多种解法，我一开始是做不出来的，看了题解后决定采用二分套二分的做法，然后一直做不出...最后还是借助了ai神力，修正了错误才做出来。5.78题(题解里面需要用到我目前没掌握的，且难以快速掌握的知识解决题目，所以看了题解也无法做出)3620. 恢复网络路径 1998 题解需要用到DAG DP / 拓扑排序 尚未学到，先不做3600. 升级后最大生成树稳定性 2301 需要使用并查集 尚未学习4.5.2 开始讲解首先我们来讲解第一题：2812. 找出最安全路径，先看题。首先，看到题目是矩阵，并且从左上角走到右下角，很难不联想到搜索算法。在搜索算法中，最通用的算是bfs（广度优先搜索）算法了，因为它既能算是否能到达某个点，又能算到达某个点的最短步数，不像dfs算法，只能算能否到达。所以我们想到了使用bfs来解决这道题目。又因为这道题目是在二分题单里面的，带着目的想问题，我们很容易想到去二分猜这个最大安全系数，然后再代入这个安全系数到bfs中，检验是否能在全程不超过这个安全系数的前提下，走到终点。那么现在只剩下最后一个障碍了：如何算出每一格到最近的小偷单元格的曼哈顿距离？你肯定会首先想到去O(n^3)复杂度的遍历：外层循环用来找小偷单元格，然后内层的两个循环来给每个格子标它自己到当前选定的小偷单元格的距离，再引入min函数来取最小值，这样每一格留下的都是最短的距离。这样的方法当然行得通，但是太慢了。我们需要更快的方法——这就是这次我们需要用到的新知识：多源bfs。定义如下：多源 BFS 是指从多个起始点同时开始进行广度优先搜索（BFS）。与单源 BFS 不同的是，多个起点同时进入队列，BFS 会同时向所有方向扩展。其核心思想是将多个源节点的影响同时传播到其他节点，常用于求解多源最短路径、最小距离等问题。步骤：将所有源节点入队。对队列中的每个节点，进行标准的 BFS 扩展，更新相邻节点的距离或状态。常用于计算多个点到所有其他点的最短距离（如多源最短路径问题）。在这道题目中，我们只需要先遍历整个矩阵，然后记录下所有小偷格子的坐标，然后将它们全都丢进bfs的初始队列中，相当于以它们为起点，向四处扩散开来。接着，进行正常的bfs流程（只不过去掉了校验终点的流程，因为多源bfs一般来说是没有目的的随意遍历），再继续引入min函数，这样就能方便快捷的获得每一格到最近的小偷格子的曼哈顿距离。而且很有意思的点是，bfs的dist数组本身记录的步数就是从起点出发到此处的曼哈顿距离，所以甚至都不需要另外计算距离，直接填入步数即可。到这里，题目的基本思路就实现完了。看代码，重点看上面两个函数：#include <bits/stdc++.h> using namespace std; using ll = long long; class Solution { public: //使用bfs判断是否能在当前安全系数下到达终点 bool canReach(vector<vector<int> > &d, int mid, int n) { if (d[0][0] < mid || d[n - 1][n - 1] < mid) return false; queue<pair<int, int> > q; q.emplace(0, 0); vector<vector<int> > dist(n, vector<int>(n, -1)); dist[0][0] = 0; while (!q.empty()) { auto [cx,cy] = q.front(); q.pop(); if (cx == n - 1 && cy == n - 1) { return true; } for (int dir = 0; dir < 4; dir++) { int nx = cx + dx[dir]; int ny = cy + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (dist[nx][ny] != -1 || d[nx][ny] < mid) continue; q.emplace(nx, ny); dist[nx][ny] = dist[cx][cy] + 1; } } return dist[n - 1][n - 1] != -1; } //使用多源bfs计算每个格子到最近小偷格子的曼哈顿距离 vector<vector<int> > getDist(vector<vector<int> > &grid, int n) { vector<vector<int> > d(n, vector<int>(n, -1)); queue<pair<int, int> > q; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { //如果是小偷格子 q.emplace(i, j); //加入多源bfs的起始队列中 d[i][j] = 0; } } } while (!q.empty()) { auto [x,y] = q.front(); q.pop(); //开始无目的多源bfs for (int dir = 0; dir < 4; dir++) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (d[nx][ny] == -1 || d[nx][ny] > d[x][y] + 1) { d[nx][ny] = d[x][y] + 1; q.emplace(nx, ny); } } } return d; } int maximumSafenessFactor(vector<vector<int> > &grid) { //1.计算d int n = grid.size(); auto d = getDist(grid, n); //2.二分计算当前安全值下是否可达 int l = 0, r = 2 * n, ans = -1; while (l <= r) { int mid = l + (r - l) / 2; if (canReach(d, mid, n)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; } private: vector<int> dx = {-1, 1, 0, 0}; vector<int> dy = {0, 0, -1, 1}; };好了，我们接着来看第二题：3449. 最大化游戏分数的最小值 ，先看题。这道题的基本思路很简单，题目的提示里面也有写：We should go from i to (i + 1) back and forth, making the value for each index i (from left to right) no less than x.说白了，就是如果i的分数不够，我们就前后前后的在i和i+1之间来回横跳，直到i的分数足够了，我们才继续往下。看完这个提示，我相信你们肯定能形成一个大概思路了：先用二分猜游戏分数的最小值，然后遍历游戏分数，如果遇到小于这个最小值的points[i]，就来回横跳给它加到mid，然后再往下，记录下操作的次数。最后再比较这个操作次数是否<=m(也可以在中途放一个判断，只要大于了就break，节省时间)。思路归思路，但是实现起来并不是一帆风顺的。首先，你会想到：前后横跳，如果在最后一位怎么办？所以，我们需要分类讨论：如果i在最后一位，那就往前来回横跳。这只是其中一个需要判断的东西，我们还需要思考啥时候这个次数超出m的时候才应该退出？啥时候超出m的时候break？这很难用语言文字来描述，到时候我在代码旁边注释。将上面都安排妥当后，最后还得检查是否所有的point都不小于mid。因为上面有一个次数超出m直接break的式子，触发这个式子并不一定是失败了，也有可能是完成最后一个小于mid的point的填充之后，我多跳了一下，导致次数超出。所以这时候就需要扫描一下points，来二次确认到底合格了没有。不多说了，看代码：using ll = long long; class Solution { public: bool ok(vector<int>& points, int m,ll mid) { vector<ll> gameScore(points.size()); ll curM = 1; //由于开局指针在-1，从-1到0是必须走一步的，所以直接初始化计数器为1 for (int p=0;p<points.size();p++) { if (curM>m) break; //这里是应对完成最后一个i然后多走了一步超出的情况，交由下面的range循环二次检查 gameScore[p]+=points[p]; if (gameScore[p]<mid && p!=points.size()-1) { //处理i不是最后一位的情况 ll diff = mid-gameScore[p]; //计算当前分数和二分的目标分数的差距 ll time = (diff+points[p]-1)/points[p]; //用向上取整算需要加分的次数 if (time*2>m-curM) return false; //上述次数*2就是操作的次数 gameScore[p]+=time*points[p]; //给i加分 gameScore[p+1]+=time*points[p+1]; //给i+1加分(被迫营业，当然从贪心的角度来看，往后加分是最好的，不浪费操作次数) curM+=time*2; //上述次数*2才是操作的次数(因为需要来回横跳) }else if (gameScore[p]<mid && p==points.size()-1) { //处理i是最后一位的情况 //下面的逻辑和上面一样，就是把i+1变成了i-1而已，就不注释了 ll diff = mid-gameScore[p]; ll time = (diff+points[p]-1)/points[p]; if (time*2>m-curM) return false; gameScore[p]+=time*points[p]; gameScore[p-1]+=time*points[p-1]; curM+=time*2; } curM++; //每往后移动一次次数加一 } for (auto x:gameScore) { //这里的遍历主要是处理break出来的情况，用于二次确认 if (x<mid) return false; //因为有可能我已经把最后一个i给加到了mid，不需要再移动了，但是我的程序默认是移动偶数次数，所以就有可能刚好超出一次次数。这种情况应该是被允许的 } return true; } long long maxScore(vector<int>& points, int m) { ll l = 0,r = points[0],ans = -1; for (auto x:points) r = max(r,(ll)x); r*=m; while (l<=r) { ll mid = l+(r-l)/2; if (ok(points,m,mid)) { ans = mid; l = mid+1; }else { r = mid-1; } } return ans; } };好了，我们接着来看第三题：2528. 最大化城市的最小电量，先看题。题目“供电”的定义很简单：供电站给自己r距离范围内的城市供电，被波及到的城市获得1个电量，然后叠加。所以，为了计算出城市i的电量，我们需要获得这个城市[i-r,i+r]范围内的供电站数量，而累加这个操作，相当于计算[i-r,i+r]范围内的区间和，我们能很容易想到前缀和。所以，我们的第一步是用题目提供的stations供电站数量数组，来构建一个供电站数量的前缀和数组。这样，我们在计算每个城市的电量(即[i-r,i+r]的区间和)时，只需要O(1)时间复杂度，十分快速。好了，接着我们需要将这道题目代入二分算法的逻辑。我们选择二分答案，而这个答案就是所有城市电量的最小值，然后我们又能新建供电站k座。以往的做题思路告诉我们，我们需要先二分一个mid，然后再遍历每个城市的power，如果这个power<mid，那就需要新建供电站。那么，这个供电站应该建在哪里呢？和上道题目的反复横跳有些类似，用贪心的思路判断，我们应该建供电站在这个城市的后面，正好使这个城市在供电站所能波及到的边界就行。因为如果建供电站在这个城市的前面，或者新建的供电站能波及到这个城市左边的城市，电力资源就存在了浪费：这个城市左边的城市的电量是很明显>=mid，但是这个城市右边可能会存在城市的电量<mid，如果供电站位置偏左，导致右边那个城市正好在这个新建供电站的波及范围之外，这不是浪费资源了吗。所以，将这个城市处于新建供电站的波及范围的左边界是最优解。当然，注意一下别超出城市数组的右边界了，这里就需要用到一个max。即：将供电站放在max(数组右边界,i+r)的位置。那么在新建供电站之后，我们需要更新所波及到的所有城市的电量，相当于一个一个的更新区间和。那么我们该如何快速更新呢？这时候就需要用到差分数组了。我们构建一个差分数组，然后利用差分数组的当前元素值即为其前序元素之和的特性，一直累加维护一个变量cur，就可以直接获取当前城市的真实电量，然后再进入上面的判断逻辑，若电量<mid就新增供电站，使用差分数组快速更新区间上每一个城市的电量。思路到这里就讲完了，下面看代码，有详细注释：#include <bits/stdc++.h> using namespace std; using ll = long long; class Solution { public: bool ok(vector<ll> &power, int r, ll k, ll mid, int n) { vector<ll> diff(n, 0); //初始化差分数组 ll used = 0, cur = 0; //used是记录新建电站的机会使用次数，cur表示当前城市电量 diff[0] = power[0]; //构建差分数组 for (int i = 1; i < n; i++) { diff[i] = power[i] - power[i - 1]; } for (int i = 0; i < n; i++) { cur += diff[i]; //累加维护当前城市电量 if (cur < mid) { //若当前城市电量没达到mid ll m = mid - cur; //计算出需要新建电站的数量 used += m; //记录下来 if (used > k) return false; //如果使用的机会数量超过了k次，说明失败了，就退出 ll R = min(n - 1, i + 2 * r); //新建供电站的位置 diff[i] += m; //差分数组加左边界，即当前城市，前面遍历过去的可不管 if (R + 1 < n) diff[R + 1] -= m; //差分数组加右边界，此处判断是防止越界用 cur += m; //给当前城市加电 } } return true; } long long maxPower(vector<int> &stations, int r, int k) { ll n = stations.size(), ans = -1; //1.构造前缀和 vector<ll> sum(n + 1, 0), power(n, 0); for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + stations[i - 1]; } //2.算power for (int i = 0; i < n; i++) { power[i] = sum[min((ll)n, (ll)i + r + 1)] - sum[max(0, i - r)]; } ll left = stations[0], right = k; for (auto x: stations) { left = min(left, (ll)x); right += x; } while (left <= right) { ll mid = left + (right - left) / 2; if (ok(power, r, (ll)k, mid, n)) { ans = mid; left = mid + 1; } else { right = mid - 1; } } return ans; } };最后，我们来到了最cs的第四题：3464. 正方形上的点之间的最大距离 ，先看题。题目拿到手我们可能会没啥思路，那就看看提示：Think of the coordinates on a straight line in clockwise order.翻译：把这些坐标按顺时针顺序，想象成排在一条直线上的点。这就是我们这道题的主旋律。让我们跟着这个主旋律，慢慢的拆解这道题目，将其拿下。首先，我们需要将这些坐标转换成排在一条直线上的点。有两条思路，第一条思路是模拟一个光标，以顺时针方向沿着正方形转一圈，然后采集点；第二条思路是直接去遍历点，然后判断点所在的边，直接转换成沿着正方形顺时针走的距离，最后将获得的一个个距离排序。这里我们选择第二条思路，因为模拟光标比较费时费力，虽然说也不难。我们使用如下转换方式：if (x == 0) t = y; // 左边：从 (0,0) 向上 else if (y == side) t = side + x; // 上边：向右 else if (x == side) t = 3LL * side - y; // 右边：向下 else t = 4LL * side - x; // 下边：向左最后再排个序，我们的点与点直接的距离就生成完毕了。好了，将这些点摊开分布在数轴上后，第二步就是想出判断mid行不行的算法了。再去理解一下题意：我们需要让任意两个点之间的最小曼哈顿距离最大化。那么啥时候两个点之间的曼哈顿距离最小呢？那就是两个挨在一起的点。换句话说，我们只需要考虑，我们选取的k个点按顺序排列后，两两之间的距离全都>=mid即可。那么如何选点呢？这时候，我们的二分查找就要限时返厂了。我们可以开一个k次的循环，每次都用二分找最接近当前距离+mid的点，然后将当前距离更新成找到的新点，这样匍匐着往后移动。如果能找满k次，说明可以，否则不行。就像这样：for (auto start: ps) { ll end = start + side * 4LL - mid; ll cur = start; for (int i = 0; i < k - 1; i++) { auto it = lower_bound(ps.begin(), ps.end(), cur + mid); //这里偷个懒，用stl库里面的lowerbound if (it == ps.end() || *it > end) { // cur = -1; break; } cur = *it; } }那么问题来了，为啥我的外面还套着一层循环？上面二分找点看起来好像已经很完美了。这其实是为了找最佳起点。因为从第一个起点开始不一定是最好的方案，我们得一个个试，只要从某一个点开始能跑通mid，就说明mid行；如果从所有点开始都跑不通mid，那说明mid是真不行。这就有点像01dp了，这个点可能选可能不选，最后放在最后一个点获得最佳结果。当然这道题也能用dp，但是不划算，以下是GPT5原文：可以做成 DP—but 不划算。更具体地说：结论先讲若你还是采用“二分最小距离 D + 可行性判断”的框架，那么可行性判断既可以用贪心，也可以用一种0/1 风格的 DP。但在这道题里，贪心更简单也更快；DP 做可行性判断通常会更慢、更麻烦，难以优于你现在的做法。如果硬要用 DP，怎么设？把点按周长坐标排序并扩一倍：ext[i+n] = ext[i] + P，其中 P = 4*side。固定一个候选最小距离 D（来自二分），预处理nxt[i] = 最小的 j >= i 且 ext[j] >= ext[i] + D然后在一个线性区间上做“选/不选”的 DP：取某个起点 s（把圆在 s 处“切开”），允许的最远下标为lim = upper_bound(ext, ext[s] + P - D) - 1（保证最后选的点与起点的环向距离也 ≥ D）定义f[i] = 在区间 [i..lim] 内能选择的最多点数 转移：f[i] = max( f[i+1], 1 + f[nxt[i]] ) // 选 or 不选 i 边界：f[lim+1] = 0若 f[s] >= k 则 D 可行。这样看起来是标准的“01 选择跳转”DP。复杂度问题关键在于这是环，切口位置 s 不同，lim 不同，DP 的有效区间也不同。如果你对每个 s 都跑一遍上述 DP，复杂度接近 (O(n^2))（尽管每次是 (O(\text{区间长度}))）。在 (n) 可到 1.5 万的条件下，这会吃不消。贪心那边则是：你现在的检查是：对每个起点 s，循环选择 (k-1) 次，每次 lower_bound 一次。复杂度大致 (O(n \cdot k \cdot \log n))，而 (k \le 25)，所以非常可行。有没有“只做两次”的圆环 DP（像打家劫舍那样“选首/不选首”）？遗憾的是不太行。打家劫舍模型只与相邻元素互斥；而这里互斥半径取决于距离 (D)，一个点会与若干个后继冲突（直到距离达到 (D) 的第一个点）。所以简单的“两种情况（选首/不选首）各做一次线性 DP”不能覆盖所有冲突关系。什么时候 DP 有价值？如果题目 不要求固定选 k 个，而是“最多选多少”，DP 在一次判定里就能给出最大可选数；不过这题我们本来就只需判定“是否 ≥ k”，贪心同样能办到；或者 (n) 很小（比如几百）时，用 DP 书写上更直观也无妨。小结（给你可用的建议）能做：二分 (D) → 用 “扩一倍 + nxt + 0/1 DP” 判定可行。不推荐：总体会比你现在的“二分 + 贪心（lower_bound 跳）”更慢、更复杂。继续用现在的方案就好；若想更快，可把每次 lower_bound 的起点限制在上一次命中位置之后，或改成“扩一倍 + 双指针前扫”，把每步的 log n 也省掉。好了，回到正题。那么上面的end的取值式子是怎么来的呢？这是为了防止我选的点离起点过近，即和起点的距离小于mid，而且我检查不到，导致误判此mid正确。有了这个上界限制，它就取不到离起点过近的元素。这样分析下来，基本思路已经讲完了。下面是完整代码：#include <bits/stdc++.h> using namespace std; using ll = long long; class Solution { public: bool ok(vector<ll> ps, int k, ll mid, int side) { for (auto start: ps) { ll end = start + side * 4LL - mid; ll cur = start; for (int i = 0; i < k - 1; i++) { auto it = lower_bound(ps.begin(), ps.end(), cur + mid); if (it == ps.end() || *it > end) { //如果取到了ps的外面，或者取到了离起点过近的点 cur = -1; break; } cur = *it; } if (cur >= 0) return true; } return false; } int maxDistance(int side, vector<vector<int> > &points, int k) { // 1. 直接映射到周长坐标 a ∈ [0, 4*side)，再排序 vector<ll> arr; arr.reserve(points.size()); for (auto &p: points) { ll x = p[0], y = p[1], t = 0; if (x == 0) t = y; // 左边：从 (0,0) 向上 else if (y == side) t = side + x; // 上边：向右 else if (x == side) t = 3LL * side - y; // 右边：向下 else t = 4LL * side - x; // 下边：向左 arr.push_back(t); } sort(arr.begin(), arr.end()); //2.开始二分 ll l = 0, r = side * 4LL / k, ans = -1; while (l <= r) { ll mid = l + (r - l) / 2; if (ok(arr, k, mid, side)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans; } };4.6 第k小/大 1031更新4.6.1 简介站在10月的尾巴，我又来更新了。先看看本次的做题情况：后面的题目没做完，是因为我觉得除了前几道题，后面的题目对我进修二分并没法起到很大的作用。况且就业的刷题是主推hot100的，我现在还没开始刷，已经略有些晚了。接下来，我准备再解决贪心题单，然后直接转战hot100。所以下面的其他类型题目我就不做了。老样子，给题目分个类：1.基础题(我能较快做出来)没有，实则从第一题开始就看题解了，还是比较有难度2.进阶题(我需要思考一下才能做出来)(讲解)668. 乘法表中第 K 小的数 这题属于是第k小/大类型二分题目的示例题目了378. 有序矩阵中第 K 小的元素 这题同上，也是示例题目(讲解)719. 找出第 K 小的数对距离 这题有点像滑动窗口的寻找最长合法子序列，和第k大第k小关系不大我觉得3.困难题(大体思路正确，但是需要纠正一些细节后才能做对)(讲解)878. 第 N 个神奇数字 1897 利用容斥原理算出有多少个a的倍数以及b的倍数比自己小，从而二分猜答案1201. 丑数 III 2039 更高级的容斥原理，不讲，讲了也没啥用786. 第 K 个最小的质数分数 2169 纯纯枚举法，n方复杂度也能解决，但是nlogn应该比较难4.地狱题(我看了题解还得理解很久，才能彻底弄懂)793. 阶乘函数后 K 个零 2100 纯纯公式题，我不好说，能推导出阶乘后面0的个数与5的因子的相关性的人能直接秒，其他人死活做不出3116. 单面值组合的第 K 小金额 2387 纯纯78题啊，容斥原理+dfs枚举最小集合+二分，不讲，感兴趣的可以自己点力扣去看链接5.78题(题解里面需要用到我目前没掌握的，且难以快速掌握的知识解决题目，所以看了题解也无法做出)剩下没做的题目，默认78题6.非二分查找题目(讲解)373. 查找和最小的 K 对数字 用最小堆可以解决，作为题外话可以讲讲1439. 有序矩阵中的第 k 个最小数组和 2134 同上，也是最小堆，不过条件比上面的苛刻上面的题目，如果你想牢牢掌握这方面知识点，我个人认为，把668、378、878这三题搞懂就差不多了，其他题目能否做出纯纯看其他知识的造化。4.6.2 开始讲解！首先我们来看第一题：668. 乘法表中第 K 小的数，先看题。首先，既然是二分猜答案，那我们的主要任务就是在猜一个答案后，判断一下这个答案到底是第几小/大。这道题是乘法表，所以每一行的每个数都是第一个数的倍数。所以，我们只需要将这个数整除第一个数，就知道有几个数比它小了。然后我们再一行一行处理，就能得到每一行有几个数比当前这个数要小，最后再一累加就能得到这个数到底比乘法表里面多少个数大了。好了，这样我们就知道了当前猜的答案是第几小的数了。然后，再配合二分算法，如果我是>k小的数，说明我猜大了，下一次猜小一点；反之，我下一次猜大一点。这样就能把答案猜出来了。#include <bits/stdc++.h> using namespace std; using ll = long long; class Solution { public: bool ok(int mid,int m,int n,int k) { int cnt=0; for (int i=1;i<=m;i++) { cnt+=min(n,mid/i); } return cnt>=k; } int findKthNumber(int m, int n, int k) { ll l=1,r=(ll)m*n+1,ans=-1; while (l<=r) { ll mid = l+(r-l)/2; if (ok(mid,m,n,k)) { //如果cnt>=k-1，说明猜的数大了或者猜中了 ans = mid; r = mid-1; }else { l = mid+1; } } return ans; } }; 接着我们来讲第二题：719. 找出第 K 小的数对距离，先看题。这题的核心思路是和滑动窗口的满足条件的最短子串题型非常相似的。我引用一下我滑动窗口笔记里面的一段话：初始化左边界left，计数器cnt。开一个循环遍历右边界right，使其一直往右推，直到不符合条件，然后进入子循环，将左边界left一直往右推，直到符合条件。此时，[left,right]这个区间已经是符合条件的了(这一点和2.3.1的方法不一样)，由于是越短越合法，所以[left+1,right],[left+2,right]...[right,right]都是合法的子数组。所以我们直接在计数器cnt上累加上right-left+1，就是我们这次得到的子数组个数。然后主循环继续将右边界向右推，直到再次不符合条件，如此往复，直到到达边界。这样我们就能在一次次的左右边界的接力前进中得到所有符合条件的子数组个数，时间复杂度O(n)。这道题也是非常类似，但是还是有一些区别，先看一下代码片段：bool ok(int mid,vector<int>& nums,int k) { int cnt=0; for (int j=1;j<nums.size();j++) { int i=0; while (abs(nums[j]-nums[i])>mid && i<j) { i++; } cnt+=j-i; } return cnt>=k; }这里用了一个while条件循环，将i指针一直往后推，直到i和j之间的数的差距<=mid才停下。因为nums[j]-nums[i]符合条件，所以nums[j-1]-nums[i]....nums[i+1]-nums[i]肯定全都符合条件。是不是对味了？哈哈。核心的代码逻辑解决后，其他地方就简单了，就是常规的二分。记得得先给nums升序排序。class Solution { public: bool ok(int mid,vector<int>& nums,int k) { int cnt=0; for (int j=1;j<nums.size();j++) { int i=0; while (abs(nums[j]-nums[i])>mid && i<j) { i++; } cnt+=j-i; } return cnt>=k; } int smallestDistancePair(vector<int>& nums, int k) { //1.先给nums排序 sort(nums.begin(), nums.end()); //2.开始二分 int n = nums.size(),l=0,r=nums[n-1]-nums[0],ans=-1; while (l<=r) { int mid = l+(r-l)/2; if (ok(mid,nums,k)) { //是答案或者偏大 ans = mid; r = mid-1; }else { l = mid+1; } } return ans; } };我们接着来看第三题：878. 第 N 个神奇数字，先看题。我们知道要二分猜答案，所以我们现在的任务就是编写算法来算出我猜的这个数字在所有“神奇”数中是第几小的。如果神奇数是a一个数的倍数，那我们天然的知道，这个数num是第num/a小的数。但是神奇数的定义是：一个正整数如果能被 a 或 b 整除，那么它是神奇的。它必须同时是a和b的倍数。这时候你直接num/a+num/b也不行，因为会有重复的部分。那么我们如何去掉重复的部分呢？这时候就需要请出我们的容斥原理了。先让ai讲解一下，啥是容斥原理：🌟 一、基本思想容斥原理（Principle of Inclusion-Exclusion）用于计算多个集合并集的元素个数。它的思路是：先把每个集合的元素都算上，然后减去重复计算的部分，再加回多次被减的部分。🧩 二、两个集合的情况对于两个集合 $A$ 和 $B$，有：$$ |A \cup B| = |A| + |B| - |A \cap B| $$解释：$|A| + |B|$ 把交集算了两次；所以要减去一次 $|A \cap B|$。🔢 三、三个集合的情况对于三个集合 $A, B, C$，有：$$ |A \cup B \cup C| = |A| + |B| + |C| * |A \cap B| - |A \cap C| - |B \cap C| - |A \cap B \cap C| $$规律：加上单个集合；减去两两交集；再加上三者交集。💡 四、一般形式对于 $n$ 个集合 $A_1, A_2, \dots, A_n$，有：$$ \Big|\bigcup_{i=1}^{n} A_i\Big| = \sum_{i} |A_i| * \sum_{i<j} |A_i \cap A_j| - \sum_{i<j<k} |A_i \cap A_j \cap A_k| * \cdots - (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n| $$🎯 五、应用举例求 $1 \sim 100$ 中能被 2 或 3 整除 的数的个数。设$A$：能被 2 整除的数，$|A| = 50$$B$：能被 3 整除的数，$|B| = 33$$A \cap B$：能被 6 整除的数，$|A \cap B| = 16$根据容斥原理：$$ |A \cup B| = 50 + 33 - 16 = 67 $$因此共有 67 个数 能被 2 或 3 整除这道题所涉及到的容斥原理，是上面讲解的两个集合的情况，所以我们只需要减去一次$|A \cap B|$即可。那么我们该如何计算这个$|A \cap B|$呢？这时候就需要用到最小公倍数的知识了。举个例子，在同时是3和4倍数的所有数里面，比20小的有几个呢？可得3和4的最小公倍数为12，所以只有1个，也就是20/12=1。好了，到这里，这道题目就做完了。#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000000+7; class Solution { public: bool ok(ll mid,int n,int a,int b) { ll cnt = mid/a+mid/b-mid/lcm(a,b); //利用两个数的容斥原理计算比mid小的数的个数 return cnt>=n; } int nthMagicalNumber(int n, int a, int b) { ll l = min(a,b)+n-1,r = 1LL*min(a,b)*n,ans=-1; while (l<=r) { ll mid = l+(r-l)/2; if (ok(mid,n,a,b)) { //猜大了或者就等于答案 ans = mid%MOD; r = mid-1; }else { l = mid+1; } } return ans; } };最后，我们来讲第四题：373. 查找和最小的 K 对数字 ，这就不是二分的知识点了。这道题虽然也可以用二分做，但是我看了做法感觉过于牵强，所以还是转战最小堆了。那么啥是最小堆呢？不管它的内部原理，它的作用就是：你加数进去，自动把最小的放在堆顶(top)供你取用。即使你弹数出去，它也一直保持最小的数在堆顶。但是要澄清一点，c++的priority_queue(优先队列)默认是最大堆，也就是默认堆顶是最大的数。所以我们要么在后面加参数，要么就简单粗暴，直接把我们要对比的key设为负数，直接搞定。好了，知道了最小堆这个概念，对做这个题目又有什么用呢？题目要求找前k个和最小的数对，你的第一反应肯定是用双层循环一一配对两层数组中的每个数，但是这样太慢了，时间不允许。首先，我们知道，(0,0)一定是第一小的数对，因为两个数组是升序排的。那么第二小的会是谁呢？无法确定，可能是(1,0)也可能是(0,1)，因为两个数组从第一个数到第二个数的增长幅度不一定一样。然后假设是(1,0)第二小吧，那(0,1)就是第三小，那么第四小呢？可能是(2,0),(1,1),(0,2)，这样就有三种可能了。这样还是过于麻烦了，即使配合最小堆使用，也不太方便。那么我们是否可以开局直接将(0,0),(1,0),(2,0)...(i,0)全部入堆呢？这样，我们就只需要管第二个数组了，因为第一个数组已经被我们枚举完了。用刚刚同样的方法来分类讨论：(x,y)如果是第k小，那么第k+1小就有可能是(x+1,y)或者(x,y+1)。由于我们已经把(i,0)全入堆了，所以x就不需要动了，因为我们每个x都有，只需要用(x,y+1)往后推y就已经能包含(x+1,y)的情况了！所以，我们此时只需要入堆(x,y+1)即可，记得判断一下是否越界。按照上面的过程，我们一直取堆顶，直到取够k个，就能找到第k小的数对了。看代码：#include <bits/stdc++.h> using namespace std; using ll = long long; class Solution { public: vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { //1.先将(i,0)全部入堆 priority_queue<tuple<int,int,int>> q; for (int i=0;i<nums1.size();i++) { q.emplace(-nums1[i]-nums2[0],i,0); //堆顶记得用负数 } //2.再开始取满k个值 vector<vector<int>> ans; for (int i=0;i<k;i++) { auto [_,x,y] = q.top(); q.pop(); ans.emplace_back(vector<int>{nums1[x],nums2[y]}); if (y+1<nums2.size()) { q.emplace(-nums1[x]-nums2[y+1],x,y+1); } } return ans; } };结语二分查找的部分就讲解到这里了，接下来我将进军dp题单。如果觉得我讲的不错，欢迎继续关注我的博客！
[偏自用]算法笔记系列——滑动窗口 已完结
专栏简介上一个专栏，《竞赛算法速成日记》是我为了应对大一下所到来的蓝桥杯国赛和CSP认证所临时准备所学习的算法思想，只能说是提高了广度，并没有学到精髓，在竞赛中发挥的作用并不大（蓝桥杯PyB组喜提国三，CSP认证喜提前60%）。所以，我认为确实有必要系统的，多投入一些时间去学习算法的一整套体系，来应对后面更重要的工作面试。总体学习路线，我是参照灵茶山艾府大神的这篇文章：分享｜如何科学刷题？我从文章中扒了一张图，大体就是这样：算法的知识面是非常广的，我也不奢求完美完成每一个模块，力求在1年内把所有基础的题目都做完，并且每做完一个板块，就来这里更新我自认为这一块知识点的精髓内容(如果我半个月没有更新，欢迎催更~)。当然这最主要的是为了加深我自己的理解，如果能顺带帮到你，那就更好了。所以，总结一下，这个专栏，《算法笔记》，就是我为了总结消化我所学习到的算法知识，顺带还能帮助到你一点的一个专栏。下面开始正文内容。PS:由于算法笔记的内容比较多，所以我打算每个大模块都发一篇文章，各自之间分开，不然一篇文章肯定装不下。1.定长滑动窗口最初的样子滑动窗口这个算法，算是我第一次打开leetcode刷题时就有接触到的算法了，当时也是把我狠狠震撼到了。我之前学习到的滑动窗口是这样的：给定一个字符串和一个子串，求该子串在该字符串中出现的次数(重叠也算)，如果不存在请输出-1。当时反正是拿双指针折腾了半天，结果最后还超时了，整了个O(n^2)的复杂度。其实正确的做法是，只需要一个指针，然后不断的按照该子串的长度，在字符串中从前到后切片，不断对比这个切片和给定子串，如果相等，则次数加一。这就像我在字符串中画了一片固定大小的区域，把它慢慢往后移动，就像滑动的窗户一样。这样就能以O(n)的时间复杂度完成这道题目。这是它最初的样子，让人看到恍然大悟，且一秒钟就能理解。但是现在，它又不一样了。现在的版本先看题：定长子串中元音的最大数目我的第一版本的做法就和上面一致：直接滑窗，然后傻傻的又开了一个循环数里面元音的个数。毫无意外，O(n^2)的复杂度，超时了。百思不得其解，我去看题解，发现我已经落后于时代。现在的做法是这样的：将滑动的窗户看成一个队列，当窗户向后滑一格时，把出去的那一格元素认为是出队；相反，滑进来的那一格元素认为是入队。如果出队的那一格元素是元音，那就将窗户当前的元音数量减一；如果进来的那一格元素是元音，那就把窗户当前的元音数量加一。因为窗户在滑动的过程中，除了出去的元素和进来的元素，其他元素都待在窗户里面，和上一次一样，都属于这个窗户，所以不需要去管它们的状态。当然，第一次进入循环的时候，还是得老老实实数元音的个数，不过就这一次，窗户向后滑之后，就只需要用上面的方法，管进来的和出去的就行了。最后时间复杂度O(n)，轻松解决。这个做法是非常通用的，如果具备一定的应变能力(到底啥是应变能力，你下面就知道了)，它能解决90%的定长滑窗题目(计数或者求和等)。奉上我的AC代码(最近在重温go语言，所以用go写的，当C语言看就行了，一样的)：func isYuan(b byte) bool {//判断是否是元音的函数 return b == 'a' || b == 'e' || b == 'i' || b == 'o' || b == 'u' } func maxVowels(s string, k int) int { maxCnt := 0//维护一个最大元音个数的计数器 cnt := 0//维护一个当前元音个数的计数器 for i := 0; i <= len(s)-k; i++ { ns := s[i : i+k]//切片，切出窗户 if i == 0 { //计算第一个窗口的元音个数 cnt = 0 for j := 0; j < k; j++ { if isYuan(ns[j]) { cnt++ } } } else { if isYuan(s[i-1]) { //如果出去的是元音 cnt-- //当前元音个数减一 } if isYuan(s[i+k-1]) { //如果进来的是元音 cnt++ //当前元音个数加一 } } maxCnt = max(maxCnt, cnt)//维护一个最大元音个数 } return maxCnt }还能配合哈希使用先看题：几乎唯一子数组的最大和我先说人话翻译一下这个题目：滑窗，如果这个窗户内的元素种类>=m，那就求它的和，然后找所有满足这个条件的窗户内的和的最大值。有什么东西能够自动去重，并且能够快速查询想要的元素？那就是哈希。在各类编程语言中，都有相对应的使用了哈希的容器。Python是字典(dict)和集合(set)，cpp和go中是映射(map)。将数据以哈希的形式存放，查询它是否存在、查询它对应键值对的值、删除它等操作的时间复杂度平均下来都是O(1)，非常快。在这道题目中，我们继续套用上面的滑窗逻辑，将它和map相结合：map容器的长度就是元素种类的个数，因为是键值对，还能顺带统计每个种类元素的数量。对于出窗户的元素，将它在map中的值减一，如果已经是1，那就将它从map中删除；对于入窗户的元素，如果已经存在于map中，那就将它在map中的值加一，如果不存在，就用该元素创建一个键，指向1。这样我们就完成了在滑窗时，哈希的处理。题目还要求我们求和，那只需要我们用上面的老方法一直维护一个和就行了。当map的长度达到要求，说明这个窗户的和有资格参加最大和的竞争，此时才去拿他和一个一直在维护的最大和去比较。这样跑下来，时间复杂度O(n)，完美过所有数据。Talk is cheap, show you my code:func maxSum(nums []int, m int, k int) int64 { hash := make(map[int]int)//用于统计元素种类和各种类元素数量的哈希容器，并且具备自动去重功能 var maxxSum, curSum int64//初始化最大和、当前和 for i := 0; i <= len(nums)-k; i++ { if i == 0 { //第一次进入，做好初始化工作 for j := 0; j < i+k; j++ {//正常初始化当前和，以及哈希容器 _, ok := hash[nums[j]]//检查该元素是否存在于map容器中 if ok { hash[nums[j]]++ //如果存在，直接次数加一就行 } else { hash[nums[j]] = 1 //如果不存在，就创建 } } for j := 0; j < i+k; j++ { curSum += int64(nums[j])//此处正常累加求和 } } else { curSum -= int64(nums[i-1])//出窗口，减去出去元素的值 if hash[nums[i-1]] == 1 { //如果该元素次数已经只有一次了 delete(hash, nums[i-1])//直接删掉 } else {//否则次数减一即可 hash[nums[i-1]]-- } _, ok := hash[nums[i+k-1]] //检查新加入窗口的元素是否在hash内 if ok {//如果在，次数加一 hash[nums[i+k-1]]++ } else {//否则创建 hash[nums[i+k-1]] = 1 } curSum += int64(nums[i+k-1])//进窗口，加上进来元素的值 } if len(hash) >= m {//如果map容器的长度，即元素种类的数量达到了m个的要求 maxxSum = max(maxxSum, curSum)//说明该窗户内的元素有资格参与最大和的竞争，维护一个最大和 } } return maxxSum }随机应变这一块先看题：可获得的最大点数一看到这个题，我第一反应是用双指针去做(差不多就是在两端放指针，哪边大就取那边)，但是我很快发现了问题，怎么也想不出来。一看题解，我傻了：这不就是反过来的滑动窗口吗？？？做法是这样的：我们要让只能两端取牌的总点数最大，而且能取牌的个数固定，那就是相当于找一个(总长度-取牌个数)长度的滑窗，使这个滑窗的和最小，再用总和减去这个最小的和，相当于剩下的就是最大的。所以第一步，遍历整套牌，算出总点数。第二步，用(总长度-取牌个数)长度的窗户正常滑窗，维护出一个最小和。第三步，用总点数减去这个最小和，得到答案。代码是这样的，我说的已经很清楚了，就不注释了：func maxScore(cardPoints []int, k int) int { minWindowSum := int(10e9) curSum := 0 //1.先计算出总点数 totalPoints := 0 for i := 0; i < len(cardPoints); i++ { totalPoints += cardPoints[i] } //2.开始滑窗 l := len(cardPoints) - k for i := 0; i <= k; i++ { if i == 0 { //初次进入 for j := 0; j < l; j++ { curSum += cardPoints[j] } } else { curSum -= cardPoints[i-1] curSum += cardPoints[i+l-1] } minWindowSum = min(minWindowSum, curSum) } return totalPoints - minWindowSum }还有一些很阴的题目看题，我就简单讲讲：爱生气的书店老板这道题还是有一些弯弯绕的，当然本质逻辑还是那一套滑动窗口。我想了挺久，最后才想出来去同时维护快乐时和生气时的顾客快乐总数，最后也是没看题解做出来了。这里我就直接贴代码了，注释详细一点，就不放文字版的做法了：func maxSatisfied(customers []int, grumpy []int, minutes int) int { var maxSum, happySum, normalSum, total, curSum int //1.先求正常情况下感到满意的顾客人数 for i := 0; i < len(customers); i++ { if grumpy[i] == 0 { //只有老板不生气时，才加上该时段的顾客人数 total += customers[i] } } //2.然后开始滑窗 for i := 0; i <= len(customers)-minutes; i++ { if i == 0 { //初次进入 for j := 0; j < minutes; j++ { happySum += customers[j] //维护一个快乐的和，一直正常累加就行了 if grumpy[j] == 0 { normalSum += customers[j] //维护正常的和，只有老板不生气时才累加 } } } else { happySum -= customers[i-1] //用正常滑窗方法维护这个和就行了 happySum += customers[i+minutes-1] if grumpy[i-1] == 0 { //如果出窗户时，老板没生气 normalSum -= customers[i-1] //那么说明我正常的和是加了这个时段的顾客数量的，得把它减去 } if grumpy[i+minutes-1] == 0 { //同理 normalSum += customers[i+minutes-1] } } curSum = total - normalSum + happySum //正常总和-现在的正常和+把魔法用在此处的顾客和=在当前位置使用魔法的不生气顾客和 maxSum = max(maxSum, curSum) //维护一个最大不生气顾客和 } return maxSum }还有一道题，先看题：拆炸弹这题的弯弯绕稍微少一些，如果一定要说哪里比较阴，那就是循环取元素和边界的判断。前者倒是还好，我一开始就想到将这个密码*2，后者找边界是真的恶心，花了我不少时间，好在只要能过用例，说明边界就找对了。看代码：func decrypt(code []int, k int) []int { doubleCode := append(code, code...)//将密码*2 if k == 0 {//处理k为0的情况 var ret []int for i := 0; i < len(code); i++ { ret = append(ret, 0) } return ret } var st, curSum int var pwd []int if k < 0 {//处理k<0的情况 st = len(code) - 1 k = -k for i := st; i < len(doubleCode)-1; i++ {//找边界后正常滑窗就行了 if i == st { //第一次进入 for j := i - k + 1; j <= i; j++ { curSum += doubleCode[j] } } else { curSum -= doubleCode[i-k] curSum += doubleCode[i] } pwd = append(pwd, curSum) } } else {//处理k>0的情况 st = 1 for i := st; i <= len(code); i++ {//找边界后正常滑窗就行了 if i == st { //第一次进入 for j := i; j < i+k; j++ { curSum += doubleCode[j] } } else { curSum -= doubleCode[i-1] curSum += doubleCode[i+k-1] } pwd = append(pwd, curSum) } } return pwd }2.不定长滑动窗口2.1.求最长/最大顾名思义，这一部分的题目就是求最长的满足某个要求的子串或者最大/最小的某个值。滑窗的做法大体有3种，题型也有好几种，放在下面说。先说滑窗的做法：第一种 直接型 时间复杂度O(n^2)基本原理是这样的：使用双重循环。第一层（最顶上）的主循环负责管理滑窗的左边界，内侧的子循环负责管理滑窗的右边界。右边界的指针从左边界开始，一直到最右侧结束，即每次的主循环的窗户，都是左边界不变，右边界在一直往右。下一次主循环再将左边界往右推一格，如此往复。这样就相当于枚举到了窗户的每种情况，时间复杂度O(n^2)。看代码：s:="slidingwindowisgreatlol"//这是你要滑的窗户，也可以是数组 for i := 0; i < len(s); i++ { for j := i; j < len(s); j++ { //在这里处理逻辑，i是滑窗的左边界，j是右边界 } }这种方法几乎所有题目都能用，因为这就是不定长滑窗的暴力枚举法，除非题目对时间复杂度要求比较高，那就只能搬出下面的办法了。能用该方法解决的几道题目：3. 无重复字符的最长子串3090. 每个字符最多出现两次的最长子字符串1493. 删掉一个元素以后全为 1 的最长子数组1208. 尽可能使字符串相等我挑第一道题目讲讲。先读题：3. 无重复字符的最长子串解题思路如下：首先看到不含有重复字符，就想到利用哈希表；最长子串，就想到不定长滑动窗口。我们直接用上面的方法枚举每一个窗口，当右指针往右移动时不断往map里面加元素，并时刻检查map的长度是否等于窗口的长度，如果等于，就将此次窗口长度和最大值比较，并继续往后；如果不等于，说明已经有缺口了，往后也补不上，直接break右移左边界，如此往复。最后维护出来的最大值就是答案。顺带一提，这道题目也可以用第二种方法做，只是它用例给了放水的空间，那不得不放。看代码：func lengthOfLongestSubstring(s string) int { maxLength := 0 //初始化最大长度 for i := 0; i < len(s); i++ { //遍历左边界 hash := make(map[byte]int) //初始化哈希表（每次更新左边界时都要作废） for j := i; j < len(s); j++ { //遍历右边界 hash[s[j]]++ //直接统计数量（go的map，如果传入不存在的key，默认返回对应类型的0值） if len(hash) < j-i+1 { //如果种类小于长度，直接退出 break } else { maxLength = max(maxLength, j-i+1) //否则维护最长长度 } } } return maxLength }直接O(n^2)极限过测（我这个break但凡删除，就过不了测）。第二种 条件移动左边界型 时间复杂度O(n)基本原理是这样的：只遍历滑窗的右边界。向右扩大滑窗，左边界一直不动，同时一直做符合题目要求的某种统计（计数等）。如果这个滑窗满足条件，就一直更新它的最大长度；如果不满足条件了，那就把左边界一直往右推，缩小滑窗，直到满足条件，如此往复。看代码：maxLength := 0 l := 0 //左边界 for r := 0; r < len(nums); r++ { //遍历右边界 //在这里处理逻辑 for hash[nums[r]] > k { //一直移动左边界，直到符合条件为止 //处理逻辑 l++ } }这种方法的好处就是很快，时间复杂度O(n)，坏处就是不一定所有题目都能用。能用该方法解决的几道题目（也可以说是必须要用该方法解决的题目）：2958. 最多 K 个重复元素的最长子数组1004. 最大连续 1 的个数 III1658. 将 x 减到 0 的最小操作数我挑第二题讲讲，先看题：1004. 最大连续 1 的个数 III思路如下：看到题目中说最多可以把k个0变成1，还要求连续1子串的最大长度，说明我们滑的窗户需要符合：窗户中0的个数必须<=k。这样就好办了。我们直接起一个map或者数组或者两个变量都行，来统计0和1的个数，不断往右推右边界扩大窗户；一旦0的个数超过了k，此时无论右边界怎么往右推都无法挽回了（0的个数只会多或者不变，不会少），那就开始向右推左边界，缩小窗户，直到0的个数符合条件，统计下此时的长度，和最大值比较。最后输出最大值即可。看代码：func longestOnes(nums []int, k int) int { cnt := []int{0, 0} //计数数组 maxLength := 0 //维护最大长度 l := 0 //左边界 for r, v := range nums { //向右推右边界 cnt[v]++ //计数 for cnt[0] > k { //不符合条件了 cnt[nums[l]]-- //右推左边界时维护计数，用于判断个数是否符合条件 l++ //右推左边界 } maxLength = max(maxLength, r-l+1) //记录最长长度 } return maxLength //返回最大长度的答案 }时间复杂度O(n)，轻松过测。第三种 二分查找+定长滑窗型 时间复杂度O(nlogn)基本原理是这样的：将二分查找和定长滑窗相结合。用二分查找去找到一个合适的长度，再去用定长滑窗验证这个长度是否符合某个条件。再通过验证的结果去调整长度的大小。只有在“长度越长或者越短，越难以达成条件”的题目上可以使用，一般只会用前两种方法。看代码：ans := 1 //初始化存储答案的变量 answerKey := "slidewindowonme" l, r := 0, len(answerKey) //初始化长度的左右边界 for l <= r { curLength := (l + r) / 2 //二分当前去尝试的长度 for i := 0; i <= len(answerKey)-curLength; i++ { //定长滑窗去尝试 if i == 0 { for j := 0; j < curLength; j++ { //在这里处理初次进入时的逻辑 } } else { //处理后续进入时的逻辑（出窗咋整、进窗咋整） } if 符合条件 { break //因为我们只需要验证这个长度可行就可以了，不需要继续遍历后面，节约时间 } } if 符合条件 { //从定长滑窗的循环中退出来后，判断的语句应该是和上面一模一样的，此时就可以按照需求调整长度的大小了 ans = curLength //记录下答案 l = curLength + 1 //去尝试更长的长度 } else { r = curLength - 1 //尝试更短的长度 } } fmt.println(ans) //输出的就是答案由于符合上述条件的题目不多，我目前只找到一道题目可以用这个方法极限过测（速度超过5%的人），甚至我还写了一个题解，感兴趣的可以去看看，就不在这里展开这道题目了。这道题目是：2024. 考试的最大困扰度2.2.求最短/最小 250730好久不见，连着20天没更新是因为我出去玩了，现在回家了，有时间刷题了，接着补上。求最短/最小类型的滑动窗口的题目，和上面一样，我大致分成3种方法。第一种 暴力型 时间复杂度O(n^2)这个方法和2.1的直接型有些不同，2.1是暴力枚举左右边界，而这里是暴力枚举滑窗的长度，然后在内层循环进行定长滑窗。当然时间复杂度都是一样的。我直接对着这道题来讲讲这个方法，先看题：2904. 最短且字典序最小的美丽子字符串提取要素：子串+计数，一眼滑窗。因为长度越短越好，所以外层循环从小到大，一旦找到了直接break退出就行。func shortestBeautifulSubstring(s string, k int) string { ans := "" flag := false for curLength := 1; curLength <= len(s); curLength++ { //外层循环遍历长度，从小到大 cnt := 0 //“1”的计数器 for i := 0; i <= len(s)-curLength; i++ { //内层循环是经典的定长滑窗，不会的看上面的1.1，此处不再赘述 if i == 0 { for j := 0; j < curLength; j++ { if s[j] == '1' { cnt++ } } } else { if s[i-1] == '1' { cnt-- } if s[i+curLength-1] == '1' { cnt++ } } if cnt == k && (ans == "" || s[i:i+curLength] < ans || curLength < len(ans)) { //这个取结果的条件比较复杂：只有1的数量达到题目要求，并且符合以下的条件之一(初次进入、字典序更小、长度更短)，才能取出作为结果 //PS：这里其实长度更短的条件可以不写，因为滑窗本身就是定长的，找到了就退出了，不会去找后面更长的子串 ans = s[i : i+curLength] //切片取出结果 flag = true //flag作为标识符，用于提前退出循环 } } if flag { break //在此处使用flag判断是否已经找到了结果 } } return ans }这道题的用例比较水，即使用暴力枚举左右边界的方法应该也是能通过的，感兴趣的同学可以自己试试。第二种 主流法 时间复杂度O(n)简单讲讲这个方法：初始化左边界为l，开一个for循环枚举右边界r，并一直检查这个窗口是否满足某个条件，一旦检测到满足条件，就进入子循环，将左边界l一直往右推，以此来缩小窗口，并一直检查该窗口是否还是符合某个条件，一旦不符合就退出循环，停止左边界的前推。这里有一个很重要的点，就是在大多数循环结构中，只有当左边界l已经把窗户缩小到不符合条件的状态下，才会触发退出循环的条件来退出循环。所以在取最短的、符合条件的区间时，需要将左边界l左推一格，这样才是完整的区间。此时不需要真的去动这个左边界l，我们只需要在取出这个边界时，用[l-1:r+1]这个区间即可，否则如果你将左边界推回去了，破坏了这个恰好的错位状态，下一次外层循环回来，进行是否满足条件的判断时，又会判断满足条件，从而陷入死循环。所以这样正好。叽里咕噜说了这么多，我在说啥你估计也没看懂，那就看看代码吧：func slidingWindow(s string) string { l := 0 ans := "" //初始化存储答案的变量 for r := 0; r < len(s); r++ { //在这里进行你的计数等等的算法逻辑 if 符合条件 { for 符合条件 && l <= r { //并且左边界要小于等于右边界，否则会越界 //在这里进行你的计数等等的算法逻辑 l++ //右移左边界，缩小窗口 } if 符合条件 { ans = s[l-1 : r+1] //如上面所说，左边界取的时候需要左撤一格 ansLen = r - l + 2 } } } return ans }这个方法其实和上面2.1的第二种方法很像，但是有本质区别：2.1的第二种方法是在我计数或者干啥时，已经开始不符合某个条件了，并且此时只有缩小窗户才能使其回到正轨，右移右边界扩大窗户只会让它变得更糟。所以我右移左边界来缩小窗户是为了亡羊补牢。但是这个方法就不一样了，我是想找到最短的、并且符合条件的子串，我一开始先右移右边界扩大窗口，直到满足条件，然后此时我右移左边界是为了在满足条件的前提下找到更短的子串。这就是这两个用在不同题型下的不同方法的本质区别。下面来几道题目讲讲，难度逐级递增(1个中等2个hard)，没有一题是直接套用这个算法就完事的。方法本身是不难，但是在套用这个方法之前，对于题目条件和要求的转化还是比较有难度的。第一题：2875. 无限数组的最短子数组(中等难度)，先看题。看完题了吧？第一次看完这道题的时候，我也是一头雾水。我猜到你一定会有以下难点：1.这个“无限”数组的长度，我该如何确定？总不可能每个用例都顶着给出的用例数据量范围来给这个数组拼接个10的好多次方个吧？这样早就爆内存了。2.数据量这么大，就算我找到了确定这个数组长度的方法，那我即使用这个时间复杂度O(n)的滑窗方法对着拼接出来的无限数组滑，也会超时吧？现在让我们来逐一解决这两个问题。当然，我当时也是没想出来要咋整，去看了题解，理解了之后自己做出来的。首先，我们不需要确定这个无限数组的长度。能问出这两个问题，说明你的思考方向不对。数据量非常大，单个数组的长度就有可能达到10^5，而target更是可能达到10^9，直接拼接肯定是不行的。既然这个窗口有可能跨越很多个一模一样的数组，说明它有周期性，那我们是不是可以用乘法来代替无用的重复拼接？将target整除数组的和，就能得到它结果的窗户所需要用到的数组的数量；更进一步，我们将target对数组的和取余，是否就得到了真正变幻莫测，需要我们去滑窗的，在周期之外的剩下的东西？并且这个leftover的值一定是比数组的和要小的。但是这是否代表着我们直接对单个数组滑窗就行了？不行。因为这样会忽略首尾相接的情况。所以直接把原数组double一下，对着这个新的doubleNums滑窗就行了，能覆盖到全部情况。思路讲完了，看代码：func minSizeSubarray(nums []int, target int) int { //1.计算单个nums的和 sum := 0 for _, v := range nums { sum += v } //2.计算目标相对于和的余数 left := target % sum //这是周期外剩下的东西 extra := target / sum //这是组成结果所需要用到的数组的数量 if left == 0 { //如果能被整除，说明没有剩下的东西 return len(nums) * extra //有几个数组，长度就是数量*每个数组的长度 } //3.滑窗寻找和是left的最短子串 l := 0 //初始化滑窗的左边界 total := 0 //初始化累加变量 doubleNums := append(nums, nums...) //将数组复制一份，拼接到自己的后面，实现double minLength := len(doubleNums) //用于记录最小长度 for r := 0; r < len(doubleNums); r++ { //不定长滑窗，套用上面的方法 total += doubleNums[r] //累加求和 for total >= left && l <= r { //触发条件了，开始缩小窗户 if total == left { //满足条件了，记录下最短长度 minLength = min(minLength, r-l+1) } total -= doubleNums[l] //缩小窗户 l++ } } if minLength == len(doubleNums) { //如果最小长度依然处于初始值，说明没更新过这个变量 return -1 //那就是没找到，返回-1 } //3.计算结果 return extra*len(nums) + minLength //数组个数*每个数组的长度+算出来的滑窗长度(余数所对应的滑窗长度)，得到答案 }第二题：76. 最小覆盖子串(hard难度)，先看题。翻译一下题目，就是：先统计t字符串中每个元素的个数，然后你需要在s中找到一个子串，这个子串中必须包含t字符串中的所有元素，并且对应元素的个数必须大于等于它在t字符串中的个数。这个你看用例也能比较清楚的理解。要素察觉：统计种类和个数，哈希和数组二选一；最短子串，不定长滑窗。那么我们就有了一个基本流程：先用map映射统计t字符串中每个元素的个数，然后再开不定长滑窗：不断右移右边界，直到涵盖了全部元素，再右移左边界直到不涵盖全部元素，然后在切片取结果时左撤一步左边界，记录下长度，再根据长度是否更短来决定后续是否要更新结果。那么我们该如何判断是否涵盖呢？我是采用了开一个for循环来逐一对比的方法：遍历统计t字符串元素数量的cnt1字典的键和值，再将键代入动态统计当前窗户元素数量的映射cnt2中，判断其数量是否大于等于cnt1中当前值的数量，一旦发现小于，直接return false，只有全部遍历过去都是>=，最后退出循环后才会return true。方法就是这样，直接看代码。滑窗的部分我就不注释了，和上面的逻辑一模一样。func isCovered(c1 map[byte]int, c2 map[byte]int) bool { //判断是否涵盖的函数 for k, v := range c1 { //遍历统计s元素数量的映射 if c2[k] < v { //一旦当前窗口内该元素的数量小于s中该元素的数量 return false //直接返回false } } return true //全部通过才返回true，说明涵盖了 } func minWindow(s string, t string) string { //1.先统计目标的种类数量 cnt := make(map[byte]int) for _, v := range t { cnt[byte(v)]++ //顺带一提，go的映射，没涉及到的键，默认值都是对应数据类型的零值，所以可以直接加，不需要判断键是否存在 } //2.再滑窗 l := 0 cnt2 := make(map[byte]int) //记录当前窗口内元素的种类用 ans := "" ansLen := len(s) + 1 for r := 0; r < len(s); r++ { cnt2[s[r]]++ if isCovered(cnt, cnt2) { for isCovered(cnt, cnt2) && l <= r { cnt2[s[l]]-- l++ } if r-l+2 < ansLen { ans = s[l-1 : r+1] ansLen = r - l + 2 } } } return ans }第三题：632. 最小区间(hard难度)，先看题。这题的方法有很多种，我的方法貌似又是标新立异那一个，在题解里没看到熟悉的影子。受前面几道题的启发，我想的是把这个nums给拆了，拼在一起，然后再起一个新数组newNumsIndex来存放每个数字所属的组别(类似[1,1,1,2,2,2,3,3,3..]这样的)，然后将拼在一起的newNums升序排序，让这个newNumsIndex和它联动排序。最后在这个newNumsIndex中进行不定长滑窗：用映射map统计当前窗户里面的元素种类，不断右移右边界，直到种类数量(len(map))和组数(len(nums))相等，就尝试缩小左边界，直到二者不相等后停下，记录下当前的左边界和右边界，以及两个边界之间的跨度，后续只有跨度更小或者跨度相等但是左边界更小的值才能替换掉当前的左右边界。type numIndexSorter struct { nums []int indices []int } func (s numIndexSorter) Len() int { return len(s.nums) } func (s numIndexSorter) Less(i, j int) bool { return s.nums[i] < s.nums[j] } func (s numIndexSorter) Swap(i, j int) { s.nums[i], s.nums[j] = s.nums[j], s.nums[i] s.indices[i], s.indices[j] = s.indices[j], s.indices[i] } //上面都是go语言特性，需要实现Len(),Less(),Swap()三个方法，并且构建结构体，才能用内建库sort进行两个数组的自定义联动排序 //如果仅仅是关注算法可以不用看上面的内容 func smallestRange(nums [][]int) []int { var newNums, newNumsIndex []int //1.先把数组拆了，排序 for idx, v := range nums { newNums = append(newNums, v...) //将数组内部的元素拆开并在一起 for i := 0; i < len(nums[idx]); i++ { newNumsIndex = append(newNumsIndex, idx+1) //生成每个元素的组号 } } sorter := numIndexSorter{nums: newNums, indices: newNumsIndex} //升序联动排序 sort.Sort(sorter) //升序联动排序 //2.开始滑窗 cnt := make(map[int]int) //初始化计数器 l := 0 //初始化左边界 ans := []int{0, 0} //存放左右边界的变量 ansLength := newNums[len(newNums)-1] - newNums[0] + 1 //初始化长度 for r := 0; r < len(newNums); r++ { //滑窗，此处就不讲解了，逻辑和上一道题一模一样 cnt[newNumsIndex[r]]++ if len(cnt) == len(nums) { for len(cnt) == len(nums) { cnt[newNumsIndex[l]]-- if cnt[newNumsIndex[l]] == 0 { //由于我们要统计种类，所以如果该键数量归零了就要删除，否则还是会被计入len delete(cnt, newNumsIndex[l]) } l++ } if newNums[r]-newNums[l-1] < ansLength || (newNums[r]-newNums[l-1] == ansLength && newNums[l-1] < ans[0]) { //这里是完全按照题目的定义来写的判断 ans = []int{newNums[l-1], newNums[r]} ansLength = ans[1] - ans[0] } } } return ans }第三种 二分查找+定长滑窗型 时间复杂度O(nlogn)这里的二分+定长滑窗就和2.1的逻辑基本一样了，只不过这里是遇到困难了去尝试更长的长度，2.1是遇到困难了去尝试更短的长度。基本框架：ans := 1 //初始化存储答案的变量 answerKey := "slidewindowonme" l, r := 0, len(answerKey) //初始化长度的左右边界 for l <= r { curLength := (l + r) / 2 //二分当前去尝试的长度 for i := 0; i <= len(answerKey)-curLength; i++ { //定长滑窗去尝试 if i == 0 { for j := 0; j < curLength; j++ { //在这里处理初次进入时的逻辑 } } else { //处理后续进入时的逻辑（出窗咋整、进窗咋整） } if 符合条件 { break //因为我们只需要验证这个长度可行就可以了，不需要继续遍历后面，节约时间 } } if 符合条件 { //从定长滑窗的循环中退出来后，判断的语句应该是和上面一模一样的，此时就可以按照需求调整长度的大小了 ans = curLength //记录下答案 r = curLength - 1 //去尝试更短的长度 } else { l = curLength + 1 //尝试更长的长度 } } fmt.println(ans) //输出的就是答案能用这个方法解决的两道题目：1.1234. 替换子串得到平衡字符串。这题和1423. 可获得的最大点数特别像，都是反过来的滑窗，只不过后者是定长滑窗，这个是不定长滑窗而已。直接看代码：func conv(b byte) int { //由于我是用数组当映射来计数，所以需要这个函数来把字母转换成其对应的下标 if b == 'Q' { return 0 } if b == 'W' { return 1 } if b == 'E' { return 2 } if b == 'R' { return 3 } return 0 } func balancedString(s string) int { n := len(s) / 4 cnt := []int{0, 0, 0, 0} //1.先统计整体的个数 for i := 0; i < len(s); i++ { cnt[conv(s[i])]++ } //这一块代码是为了判断是否已经平衡，这样就不用进行后面的逻辑了 flag := true for i := 0; i < 4; i++ { if cnt[i] != n { flag = false break } } if flag { return 0 } //2.开始滑窗尝试 ans := 0 l := 1 r := len(s) for l <= r { //二分查找找长度 length := (l + r) / 2 cnt2 := []int{0, 0, 0, 0} for i := 0; i <= len(s)-length; i++ { //经典定长滑窗 if i == 0 { for j := 0; j < length; j++ { cnt2[conv(s[j])]++ } } else { cnt2[conv(s[i-1])]-- cnt2[conv(s[i+length-1])]++ } flag := true for idx, v := range cnt2 { if cnt[idx]-v > n { flag = false break } } if flag { //符合条件 ans = length break } } if ans == length { //符合条件 r = length - 1 //尝试更短的 } else { l = length + 1 } } return ans }2.209. 长度最小的子数组。这题的用例特别水，看官方题解，暴力法也能过(Python不行哈哈哈)。和上面一模一样的二分+定长滑窗，我就不注释了。func minSubArrayLen(target int, nums []int) int { l := 1 r := len(nums) ans := 0 for l <= r { curLength := (l + r) / 2 curSum := 0 for i := 0; i <= len(nums)-curLength; i++ { if i == 0 { for j := 0; j < curLength; j++ { //首次进入 curSum += nums[j] } } else { curSum -= nums[i-1] curSum += nums[i+curLength-1] } if curSum >= target { ans = curLength r = curLength - 1 break } } if curSum < target { l = curLength + 1 } } return ans }2.3.求子数组个数2.3.1.越长越合法 250731像这个系列，我也是刷了5道题目，其中前3道纯纯的公式化，后2道比较有难度(一道中等，一道hard)，也就是我得经过一些弯弯绕才能运用这个方法来解决问题，或者换个说法，和这个方法结合的其他做法比较难以想到。先来讲讲解决这一系列题目最基本的方法，有且只有一种，和上面2.2的主流法基本一致，是这个方法的延伸：和2.2的主流法一样，先准备一个left作为左边界，然后开个循环遍历right右边界，正常处理算法逻辑，然后在循环内开一个子循环，时刻检测窗口是否符合题目条件，一旦突然符合了，就进入这个子循环开始右推左边界，直到不符合后停下。此时，[left,right]这个区间已经是不符合条件的了，但是[left-1,right],[left-2,right]...[0,right]全都是符合条件的，这些都是子串，这就是“越长越合法”这个说法的来源。所以，我们可以计算出，此时符合条件的子串一共有0->left-1，一共left个。在退出当前子循环后，我们直接将计数器cnt+=left，右边界right继续右推，然后又进子循环，如此往复...这样，我们就很精妙的，在O(n)的复杂度内，算出了符合要求的子串的个数。看一下基本代码模板(直接复制粘贴无法运行，主要看代码结构)：func 求子数组个数(s string) int { counter := 0 //初始化子数组个数的计数器 l := 0 //初始化窗口的左边界 for r := 0; r < len(s); r++ { //遍历右边界 //在这里处理算法逻辑，例如映射的累加 for 符合条件 { //在这里处理算法逻辑，例如映射的累减等 l++ //右推左边界 } counter += l //计数器累加子串个数 } return counter }这个模板贯穿这五道题，或直接套用，或有些弯弯绕，但是最终都是要用到它。下面开始讲题。由于前三题就是简单的直接套用，所以我挑其中一道题简单讲讲：3325. 字符至少出现 K 次的子字符串 I，先看题。我翻译一下题意：给你字符串s和整数k，你需要统计当前子串中有没有元素的出现次数是大于等于k的，如果有就符合条件，计数记下来。要素察觉：子串->不定长滑窗，统计种类->哈希表。我们可以写一个函数判断传入的子串(将统计子串的映射计为cnt)是否满足至少有一个字符至少出现 k 次这个条件，然后把这个函数套在这个框架里面就行了。至于这个函数怎么写，倒也不难，就是遍历cnt的值，比较这个值是否大于等于k，只要有一个满足，就可以直接返回true，全都不满足才返回false。思路讲完了，上代码：func timesOk(cnt map[byte]int, k int) bool { //检查是否符合题目条件的函数 for _, v := range cnt { //遍历映射的值 if v >= k { //只要有一个达标就行了 return true } } return false } func numberOfSubstrings(s string, k int) int { //主函数 cnt := make(map[byte]int) //统计子串的映射(哈希表) l := 0 //左边界 counter:=0 //计数器 for r := 0; r < len(s); r++ { //向右推右边界 cnt[s[r]]++ //统计各元素的数量 for timesOk(cnt,k){ //子循环判断元素出现次数是否达标 cnt[s[l]]-- //减去出窗口元素的个数 l++ //右推左边界 } counter+=l //加上从0->l-1一共l个子串 } return counter }另外两道题比这道题略简单一些，可以直接秒：1.1358. 包含所有三种字符的子字符串数目2.2799. 统计完全子数组的数目接着我们来过一下比较难的两道题，首先是第一题：3298. 统计重新排列后包含另一个字符串的子字符串数目 II ，先看题。主要难点：用例卡哈希，用映射map过不了，用数组却能险过。遇到这种情况，可能大多数人都以为是自己的方法不对，然后去换方法，最后弄的焦头烂额想不出来。其实力扣真的挺恶心的，有时候就是会卡你一些莫名其妙的东西。思路就不在这里重复了，想看详细思路去上面2.2看76题的做法，再回来看这里的代码就会了。这题其实就是76. 最小覆盖子串的做法加上这次的子数组个数框架，然后把哈希换成数组来计数就能过。func isCovered2(word2C []int, subC []int) bool { //和76题一样，判断是否“涵盖” for k, v := range word2C { //遍历统计word2元素种类及其个数的映射 if subC[k] < v { //比较子串的所有元素的个数是否全都大于等于word2中的元素 return false //有一个小于直接全盘否定，返回false } } return true //全部通过才能返回true } func validSubstringCount(word1 string, word2 string) int64 { //1.先统计word2 word2Cnt := make([]int, 26) //初始化26格的数组，用于统计word2中小写字母数量 for _, v := range word2 { //统计word2的元素种类和数量 word2Cnt[byte(v)-'a']++ } //2.开始滑窗 subCnt := make([]int, 26) //初始化26格的数组，用于统计子串中小写字母数量 l := 0 //初始化左边界 var count int64 //为了防止爆int，特意将计数器初始化为int64 for r := 0; r < len(word1); r++ { //求子数组个数滑窗模板 subCnt[word1[r]-'a']++ for isCovered2(word2Cnt, subCnt) { subCnt[word1[l]-'a']-- l++ } count += int64(l) } return count }接着是第二题：2537. 统计好子数组的数目，先看题。这道题还是比较有难度。一开始我想了一阵子，想到了用组合数：C<相同数的个数>取2，不就是题目所要求的pair的数量吗？这样我就只需要用hash统计每个元素的数量，然后各自取组合数然后累加不就行了？我立刻行动，写下了第一版代码，然后直接粘贴进力扣试用例：居然全过了，难道说...于是我直接提交，等力扣测评，结果也是不出意外的超时了，时间复杂度O(n^2)。没招了，我直接去看题解，题解的方法又是我从来没见过的一种：核心思路：如果窗口中有 c 个元素 x，再进来一个 x，会新增 c 个相等数对。如果窗口中有 c 个元素 x，再去掉一个 x，会减少 c−1 个相等数对。用一个哈希表 cnt 维护子数组（窗口）中的每个元素的出现次数，以及相同数对的个数 pairs。外层循环：从小到大枚举子数组右端点 right。现在准备把 x=nums[right] 移入窗口，那么窗口中有 cnt[x] 个数和 x 相同，所以 pairs 会增加 cnt[x]。然后把 cnt[x] 加一。内层循环：如果发现 pairs≥k，说明子数组符合要求，右移左端点 left，先把 cnt[nums[left]] 减少一，然后把 pairs 减少 cnt[nums[left]]。内层循环结束后，[left,right] 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，[left−1,right] 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 [left−1,right]，还有 [left−2,right],[left−3,right],…,[0,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 0,1,2,…,left−1 的所有子数组都是满足要求的，这一共有 left 个。最上面的核心思路是解决本题目的关键，它并不打算一次性算出数对的数量，而是尝试从窗口进出元素的变化中动态计算数对的数量。这是它打破O(n^2)时间复杂度的壁垒，将复杂度直接压到O(n)的关键。这个核心思路相当于：将新进来的x和里面的c个x连线，会组成c个数对；将退出的那个x和剩下的c-1个x连线，会组成c-1个数对。解决了这个核心思路，这道题目其实就和前面的公式化题目没啥区别了，直接拿下：func countGood(nums []int, k int) int64 { l := 0 var counter, pair int64 //前者记录子串数量，后者记录当前子串内的组数 cnt := make(map[int]int) //记录每个元素的数量 for r := 0; r < len(nums); r++ { //这就是上面的滑窗模板 pair += int64(cnt[nums[r]]) //如果窗口中有 c 个元素 x，再进来一个 x，会新增 c 个相等数对 cnt[nums[r]]++ //累加元素数量 for pair >= int64(k) { cnt[nums[l]]-- //将出窗口的元素数量减去 pair -= int64(cnt[nums[l]]) //如果窗口中有 c 个元素 x，再去掉一个 x，会减少 c−1 个相等数对 l++ //右移左边界 } counter += int64(l) //累加子串个数 } return counter }2.3.2.越短越合法 250801这个越短越合法的求子数组个数的题目，我也是刷了5道题，大致是这样的情况：前3题直接无脑套模板，第4题稍微加点弯弯绕但不多，第5题稍微难一点。和2.3.1一样，这个“越短越合法”也是有贯穿题目始终的算法模板的，大致描述起来是这样，和2.3.1的模板及其类似：初始化左边界left，计数器cnt。开一个循环遍历右边界right，使其一直往右推，直到不符合条件，然后进入子循环，将左边界left一直往右推，直到符合条件。此时，[left,right]这个区间已经是符合条件的了(这一点和2.3.1的方法不一样)，由于是越短越合法，所以[left+1,right],[left+2,right]...[right,right]都是合法的子数组。所以我们直接在计数器cnt上累加上right-left+1，就是我们这次得到的子数组个数。然后主循环继续将右边界向右推，直到再次不符合条件，如此往复，直到到达边界。这样我们就能在一次次的左右边界的接力前进中得到所有符合条件的子数组个数，时间复杂度O(n)。代码框架是这样的：func 越短越合法的求子数组个数框架(nums []int, 题目用到的其他变量 int) int { l:=0 //初始化左边界 count:=0 //初始化计数器 for r:=0;r<len(nums);r++{ //向右推右边界 //在这里处理你题目所需的算法逻辑，例如映射累加等 for 不符合条件{ //给不懂go语言的同学们科普一下，go是没有while循环的，go的for循环后面写条件就相当于其他语言的while //在这里处理你题目所需的算法逻辑，例如映射累减等 l++ //向右推左边界 } count+=r-l+1 //将right-left+1累加到计数器中，获得本次循环的子数组个数 } return count //最终获得全部子数组个数 }由于前三题过于简单，属于是直接套用就能解决，所以我挑其中最难的一道题来讲：2302. 统计得分小于 K 的子数组数目，先看题。看完题意，你应该能马上把这个方法和这道题目关联起来。这题唯一的一个难点就是(如果一定要揪出来一个难点)：子串的长度是动态变化的，分数又和长度有关系。如果你每次都要整体把分数算出来，你还得获得这个子串上一次的长度，然后对这个整体的分数又乘又除。。。这样肯定不行。这题，我的做法是，正常累加窗户内元素的值，正常减去出窗户元素的值，只有判断条件是否符合时才会将这个累加的值乘上当前长度(r-l+1)，实时计算出分数，去和目标值比较。这就是一个简单的乘法运算，对计算机来说，算不上任何负担，也就是对我O(n)的时间复杂度没有任何影响。我认为这还是比较巧妙的。下面是我的AC代码：func countSubarrays2(nums []int, k int64) int64 { l := 0 //初始化左边界 var sum, count int64 //由于数据量较大，所以另外用int64定义累加变量和计数器 for r := 0; r < len(nums); r++ { //右推右边界 sum += int64(nums[r]) //累加上进窗口的值 for sum*(int64(r-l+1)) >= k { //累加值*长度，实时计算分数并判断是否符合条件 sum -= int64(nums[l]) //减去出窗口的值 l++ //右推左边界 } count += int64(r - l + 1) //计数器累加上本次循环算出的子数组个数 } return count }另外两道题目，你只需要学会这个算法模板，就能直接秒，感兴趣的同学可以去试试：713. 乘积小于 K 的子数组3258. 统计满足 K 约束的子字符串数量 I接着来讲稍微有些弯弯绕的第4题：LCP 68. 美观的花束，先看题。这道题，其实和前面的3325. 字符至少出现 K 次的子字符串 I特别像，这两道题目的本质都是要不断去检查映射map里面的值是否全都/存在某个值 大于/小于 某个值。你要么再开个子循环检查，要么更加简单易懂，新开个函数给这个循环封装进去，这样不会破坏框架的结构，使代码的可读性更强。所以回到这道题，其实就是需要你去用映射或者数组统计每个品种的花的数量，然后不断遍历检查其值是否全都小于题目要求的cnt值，再套进这个模板，就能秒解决。代码如下：func isBeautiful(hash map[int]int, cnt int) bool { //检查花束是否美观的函数 for _, v := range hash { //遍历映射 if v > cnt { //只要有一个花的数量比要求值大 return false //直接否定 } } return true //全部都不超过要求值才能通过 } func beautifulBouquet(flowers []int, cnt int) int { //解题主函数 l := 0 //左边界 hash := make(map[int]int) //计数的映射 count := 0 //计数器 MOD := 1000000007 //题目要求的取余的数 for r := 0; r < len(flowers); r++ { //正常公式化循环 hash[flowers[r]]++ for !isBeautiful(hash, cnt) { hash[flowers[l]]-- l++ } count = (count + r - l + 1) % MOD //一边累加一边取余 } return count }接着来讲上难度的第5题：2762. 不间断子数组，先看题。这道题目主要的难点是：我该如何确保我的子串中任意两个数相减的绝对值都会小于等于2？直接暴力枚举吗？很明显不现实。这个还真的给我卡住了，于是我看了一下题目的提示：Use a set or map to keep track of the maximum and minimum of subarrays.翻译：用集合或者映射来追踪子串的最大值和最小值。对哦！我直接保持更新子串的最大值和最小值不就行了！只要最大值减去最小值小于等于2，那其他任意两个数相减肯定小于等于2。此时我还不知道集合在这里的作用是啥，就按照这个提示改进了我的代码，也是直接AC了：func notGood(hash map[int]int) bool { //维护最大值最小值，并直接判断是否符合条件的函数 max2 := 0 min2 := 1000000001 for k, _ := range hash { min2 = min(min2, k) max2 = max(max2, k) } return abs(max2-min2) > 2 //这里有个小插曲，本地的go环境有abs这个容器，但是力扣没有，直接给我报错了，没绷住。不过直接拿掉倒也没啥事 } func continuousSubarrays(nums []int) int64 { //主程序函数 l := 0 //左边界 hash := make(map[int]int) //映射，用于计数 var count int64 //初始化计数器 for r := 0; r < len(nums); r++ { //公式化循环 hash[nums[r]]++ for notGood(hash) { hash[nums[l]]-- if hash[nums[l]] == 0 { //由于需要看键的值来确定最大值最小值，所以出窗了需要删掉 delete(hash, nums[l]) } l++ } count += int64(r - l + 1) //累加 } return count }即使代码通过了，我还是没搞懂集合在此处的作用，还以为：直接扫描子串来确定最大值最小值不是一样的吗，数字多起来后不是集合也照样会变得很长吗。直到我去求助了o4-mini，它的回答让我醍醐灌顶：维护一个哈希表，核心目的是让「每次滑动窗口左右边界」时都能以常数时间（或接近常数）知道当前窗口里的最小值和最大值，以及它们的计数。 如果你每次都去遍历子数组本身来找 min/max，那么：子数组长度可能很大，最坏情况下遍历整个窗口每次要 O(n)；在双指针滑动过程中，一共会做 O(n) 次这样的遍历，整体就退化到 O(n²)，对于 n 高达 10⁵ 的情况下肯定跑不动。用哈希表的好处在于：我们只在插入／删除元素时更新计数；当前窗口由于「max−min≤2」的约束，哈希表中最多只有 3、4 个不同的 key，遍历它去算 min/max 本质上是 O(1) 操作；删除时若计数变为 0，就直接从 map 里删掉，不用扫描整个窗口去确认某个值是不是已经不在窗口里了。这样每次右指针 r 向右扩、左指针 l 向右收缩都只是对 map 做 ++/--/delete，然后扫描常数级别大小的 map 来判断是否 “notGood”，整体就是 O(n) 了。当然，也可以用双端队列维护窗口的单调队列来分别做 min/max，和哈希表的思路一样，都是为了把查找最新 min/max 的成本摊平到 O(1)／次。总结起来就是：这个子串可能会很长，但是受题目条件限制，里面数字的种类最多就3种。毕竟如果大于3种，这个子串的最大值-最小值肯定就大于2了，它就不符合条件了。所以，利用map的自动去重+计数特性，我们可以将原本是O(n)复杂度的扫描简化到O(1)复杂度，让题目不至于变成O(n^2)直接超时。这样看来，滑动窗口和哈希表的关系真是紧密。从定长到不定长滑窗，哈希表从未缺席。那么今天就讲到这里。有一说一Go语言的容器是真的挺低能的，并且用Go刷这么久题目我也刷腻了，之后我要改用cpp或者python继续刷题了。。。2.3.3 恰好型滑动窗口 250803先来讲讲什么是“恰好型”。前面的2.3.1和2.3.2都是子串内的某某东西越多/少越好，而这次的“恰好”就是：求某某东西的数量正好等于某个值的子串的个数。虽然条件看起来变化很大，第一时间你可能找不到头绪。但其实我们只需要继续沿用上面2.3.1和2.3.2的方法就行了，并且怎么沿用，也有两种选择。所以，如果你有些忘记了，请先看完上面2.3.1-2两个章节，再继续阅读下面的内容。第一种选择：利用"越长越合法"题型的方法先复习一下“越长越合法”的解题方法：在符合条件后不断缩小区间直到不符合条件，然后就能求出>=某个值的子数组的个数。既然要求等于某个值的子数组个数，那我们直接求出>=某个值的子串个数，再求出>=某个值+1的子串个数，不就能直接求出等于某个值的子数组个数了吗。用编程的说法来转述一下，就是我把求越长越合法题型的代码封装成一个函数f()，然后题目传入的数组和目标值分别为nums和target，那么我们直接return f(nums,target)-f(nums,target+1)就是答案。这次我一共刷了4道题目，3道是用这个选择做的，还有1道是用“越短越合法”的选择做的。在这3道题目中，前2道就是公式化直接代入，第3道可能稍微有那么一点弯弯绕，所以我挑第三道讲一讲：3306. 元音辅音字符串计数 II，先看题。要素察觉：元素出现次数->哈希表计数；子数组个数->公式化滑窗。那么基本思路就出来了：公式化滑窗遍历字符串，如果是元音，就计数存入哈希表；如果不是，就让辅音计数器累加。最后在写子循环判断条件时，按照题目要求写条件就行了，也是十分的公式化。看代码，今天开始用c++写：class Solution{ public: bool isYuan(char a){ //判断当前元素是否是元音的函数 return a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u'; } long long atLeast(string word, int k){ //滑窗的主程序 long long l = 0, fuCnt = 0, count = 0; //初始化：左边界，辅音的计数器，子数组数量的计数器 map<char, int> hash; //初始化：元音的计数器 for (int r = 0; r < word.size(); r++){ //公式化滑窗 if (isYuan(word[r])){ //如果当前元素是元音 hash[word[r]]++; //计数 }else{ //如果不是元音，那就是辅音 fuCnt++; } while (hash.size() >= 5 && fuCnt >= k){ //hash长度就是当前窗口内的元音种类 if (isYuan(word[l])){ //公式化出窗口累减 hash[word[l]]--; //这里注意：cpp和go一样，某个键的值归零后如果不删除，还是会被计入长度，从而影响种类数量的判断 if (hash[word[l]] == 0){ hash.erase(word[l]); //所以要在归零后及时删除 } }else{ fuCnt--; } l++; //越长越合法，加上l } count += l; } return count; } long long countOfSubstrings(string word, int k){ //解决题目的主程序 return atLeast(word, k) - atLeast(word, k + 1); //(>=k)-(>=k+1) } };第二种选择：利用"越短越合法"题型的方法同样，先复习一下“越短越合法”题型的解题方法：一直右推右边界直到不符合条件，然后一直右推左边界直到符合条件，这样就能求出<=某个值的子数组的个数了。那么我们直接f(nums,target) - f(nums,target-1)就行了。我只有1道题目用了这个方法：992. K 个不同整数的子数组，先看题。要素察觉：不同整数的个数->哈希表计数；子数组个数->公式化滑窗。解题思路和上面这道题没啥区别，我就不讲了，直接看代码：class Solution{ public: int atMost(vector<int> &nums, int k){ //滑窗主程序 int l = 0, count = 0; //初始化：左边界，子串计数器 map<int, int> cnt; //数字种类的计数器 for (int r = 0; r < nums.size(); r++){ //公式化滑窗 cnt[nums[r]]++; //计数 while (cnt.size() > k && l <= r){ //cnt的长度就是 cnt[nums[l]]--; if (cnt[nums[l]] == 0){ //这里和上一题一样，归零必须删除 cnt.erase(nums[l]); } l++; } count += (r - l + 1); //越短越合法，加上r-l+1。此处括号不加也行，加上是为了可读性更好 } return count; } int subarraysWithKDistinct(vector<int> &nums, int k){ //解题主程序 return atMost(nums, k) - atMost(nums, k - 1); //返回(<=k个数)-(<=k-1的个数)，就是==k的个数 } };结语到这里，我们滑动窗口最最基础的部分也是圆满结束了！大约使用了15天时间(纯刷题时间)，我们也只不过是完成了力扣滑窗题库题目的25%。接下来，二分查找篇再见！PS:在写这一部分的时候，我已经开始接触二分查找了，难度也是更上一个台阶。加油吧！
前言此博文用于记录我学习到的一些算法思想，语言是c++或者python。cpp竞赛模板第一行的万能头大部分情况下是能用的，如果不能用，那就手动导入iostream等等的库。#include <bits/stdc++.h> using namespace std; int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); // code here }py和cpp时间复杂度对比复杂度C++ 每秒数据量估算Python 每秒数据量估算O(1)无限无限O(log n)~1e8~1e7O(n)~1e8~1e7O(n log n)~2e7~1e6O(n^2)~1e4~1e3O(n^3)~300~50这是单机、单核、主流在线评测平台（如LeetCode、Codeforces、牛客、洛谷等）上1秒内大致能承受的数据规模。C++ 由于编译型、无解释器开销，所以通常比 Python 快 5~10 倍，甚至更高。复杂度上升一档，数据规模要大幅缩小！c++一些需要注意的地方1.快速输入输出c++默认的cin cout在数据量很大时输入输出很慢，可以在main函数的开头加上如下两行（此时输入输出只能是cin cout，不能再用scanf和printf了）：ios::sync_with_stdio(false); cin.tie(nullptr);尤其是在处理矩阵时，差两行这个可能会让你从ac到超时。2.unsigned数据类型的溢出反倒可以自动取模举个例子，unsigned long long正好到2^64-1的大小，所以如果此时输入2^64或者更大的数，相当于自动对2的64次方取模(mod)，实现了啥都不干自动就取模了。c++主要数据类型的范围和取模的关系：数据类型位数有符号/无符号自动对 2^k 取模最大可自动取模的 k备注unsigned char8无符号是82^8=256unsigned short16无符号是162^16=65536unsigned int32无符号是322^32unsigned long32/64无符号是32/64（平台相关） unsigned long long64无符号是642^643.set的使用用途在需要不断维护一个有序列表，并且需要经常插入、寻找、删除、修改的，用set这个数据结构是十分高效且合适的。时间复杂度平均为O(logn)使用方法操作说明示例代码定义声明一个 setset<int> s;插入元素插入元素，自动排序s.insert(5);删除元素删除指定元素s.erase(5);查找元素查找元素是否存在auto it = s.find(5);大小返回元素个数s.size();清空清空所有元素s.clear();遍历从小到大遍历所有元素for(auto x : s) ...lower_bound找到第一个不小于某值的元素迭代器s.lower_bound(5);upper_bound找到第一个大于某值的元素迭代器s.upper_bound(5);相关题目https://www.luogu.com.cn/problem/P5250Python一些需要注意的地方1.浅拷贝问题——如何正确创建矩阵在Python中，创建一维列表有两种创建方式：list1=[0]*length list2=[0 for _ in range(length)]随意选择即可。但是创建二维列表就不一样了，虽然也有两种方式：matrix1=[[0 for _ in range(length1)] for _ in range(length2)] matrix2=[[0]*length1 for _ in range(length2)]我知道你肯定想写这种：matrix3=[[0]*length1]*length2那你猜会发生什么？正如标题所言，浅拷贝：假设你使得matrix[0][2]=1，那么matrix[1][2] matrix[2][2] matrix[3][2]...全都会等于1。也就是相当于你这样生成矩阵，python相当于复制了一堆引用，也算是一个特性吧，所以不要这么写。2.append中暴露的引用问题看下面的代码：def a(lis,cnt): global result if cnt>=5: return lis.append(1) result.append(lis) a(lis,cnt+1) result=[] a([],1) print(result)你肯定会认为，最后的结果是这样：[[1], [1, 1], [1, 1, 1], [1, 1, 1, 1]]实际是这样的：[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]为什么呢？因为在函数中，append进result中的lis其实是一个引用，所以result实际上是这样的：[lis,lis,lis,lis]，所以最后lis是啥值，就会有四个一样的值。要解决这个问题，直接在lis后面加.copy即可：def a(lis,cnt): global result if cnt>=5: return lis.append(1) result.append(lis.copy()) a(lis,cnt+1) result=[] a([],1) print(result)这样输出就正常了。这个问题常常在递归函数访问外部变量时出现，如果想彻底避免这个问题，每次多写个copy就行了，反正又不会影响运行。3.递归深度问题在做一些一眼递归的题目时，如果发现数据量很大，需要递归很多次，还是能转循环的转循环吧，尽量不要用递归，不然会爆栈，反而弹出c语言的错误。能否到达：DFS递归写法经典走迷宫写法题目见：https://www.luogu.com.cn/problem/B3625#include <bits/stdc++.h> using namespace std; int n, m; // 迷宫地图：'#' 表示墙，'.' 表示空地 vector<string> grid; // 访问标记 vector<vector<bool>> vis; // 四个方向：下、上、右、左 int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; // 递归 DFS： // 返回值：从 (x,y) 出发，能否到达终点 (n-1, m-1) bool dfs(int x, int y) { // 1）越界或遇墙或已访问 → 剪枝 if (x < 0 || x >= n || y < 0 || y >= m) return false; if (grid[x][y] == '#' || vis[x][y]) return false; // 2）标记当前格已访问 vis[x][y] = true; // 3）到达终点，直接返回 true if (x == n-1 && y == m-1) { return true; } // 4）依次尝试四个方向，只要有一条路返回 true 就可 for (int dir = 0; dir < 4; dir++) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (dfs(nx, ny)) { return true; // 子调用找到路了，直接向上层返回 } } // 5）如果四个方向全部失败，可选地「回溯」时撤销标记： // vis[x][y] = false; // 这里只问能否到达，不需要路径，所以不撤销也行。 //提示：时间复杂度爆炸，如果只想知道是否能到达，不要撤销，不然会超时。 return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 读入 cin >> n >> m; grid.resize(n); for (int i = 0; i < n; i++) { cin >> grid[i]; } vis.assign(n, vector<bool>(m, false)); // 从 (0,0) 开始 DFS bool canReach = dfs(0, 0); cout << (canReach ? "Yes\n" : "No\n"); return 0; }大概就是利用了递归天然自动回溯的特性，可以减少一些代码量，而且速度也不会太慢。当遇到递归边界时，它就会自动返回到刚刚的路口，选择另外的路。在递归中，差不多就是四步走：判断是否无法行走，然后剪枝给当前方块标记已访问判断是否在终点，然后返回true继续尝试其他可用的方向需要记住的要素：访问标记二维数组递归退出条件：到达终点或者剪枝时遍历树的写法相关题目：https://www.luogu.com.cn/problem/P5318bool dfs(int node){ //1.如果当前点已访问，直接走 if (visited[node-1]){ return false; } //2.标记当前点已访问 visited[node-1]=true; //3.输出当前点 cout << node << " "; //4.如果接下来没点了，直接走 if (tree[node-1].empty()){ return false; } //5.遍历不同方向 for (int i=0;i<tree[node-1].size();++i){ if (dfs(tree[node-1][i])){ return true; } } return false; }枚举这个东西选不选的写法相关题目：https://www.luogu.com.cn/problem/P2036def generate(pos,lis): global results global n if pos==n: results.append(lis.copy())#这里一定要copy，不然存入的是引用，后续lis的值变了就导致results里面的lis一直变 return #下个东西取或不取 lis.append(1)#取 generate(pos+1,lis) lis.pop()#撤销 lis.append(0)#不取 generate(pos+1,lis) lis.pop()#撤销 results=[] #开始举出所有情况 generate(0,[]) print(results)全排列写法相关题目：https://www.luogu.com.cn/problem/P1706def dfs(n,used,path): if not 0 in used:#全都用过了 for j in path: print("{:5d}".format(j),end="") print() return for i in range(1,n+1): if used[i-1]==0: path.append(i) used[i-1]=1 dfs(n,used,path) used[i-1]=0#复原 path.pop()#复原 N = int(input()) dfs(N,[0 for i in range(N)],[])最短路径：BFS队列写法走迷宫写法相关题目：https://www.luogu.com.cn/problem/P1443#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 1）读入 n 行 m 列的迷宫尺寸 int n, m; cin >> n >> m; // 2）读入迷宫地图：'.' 为空地，'#' 为墙 vector<string> grid(n); for (int i = 0; i < n; i++) { cin >> grid[i]; } // 3）方向数组，表示四个相邻的偏移：下、上、右、左 int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; // 4）距离数组 dist[x][y]：从起点 (0,0) 到 (x,y) 的最短步数 // 初始化为 -1，表示未访问过 vector<vector<int>> dist(n, vector<int>(m, -1)); // 5）队列，用来按“层”来遍历所有可达节点 queue<pair<int,int>> q; // 6）BFS 起点初始化 dist[0][0] = 0; // 起点自身距离为 0 q.emplace(0, 0); // 将起点入队，开始 “波纹” 扩散 // 7）开始标准的 BFS 循环 while (!q.empty()) { // 7.1）取出当前队首节点 (x,y) auto [x, y] = q.front(); q.pop(); // 7.2）如果已经到达终点 (n-1,m-1)，可以提前终止循环 if (x == n-1 && y == m-1) { break; } // 7.3）尝试向四个方向扩散 for (int dir = 0; dir < 4; dir++) { int nx = x + dx[dir]; // 下一个点的横坐标 int ny = y + dy[dir]; // 下一个点的纵坐标 // 7.3.a）边界检查：必须在 [0,n) 和 [0,m) 范围内 if (nx < 0 || nx >= n || ny < 0 || ny >= m) { continue; } // 7.3.b）障碍物或已访问：墙 '#' 或 dist 已被设置过 if (grid[nx][ny] == '#' || dist[nx][ny] != -1) { continue; } // 7.3.c）合法的新格子： // ① 标记最短距离 = 当前距离 + 1 dist[nx][ny] = dist[x][y] + 1; // ② 把它加入队列，后续再扩散它的邻居 q.emplace(nx, ny); } } // 8）循环结束后，检查终点是否被访问 if (dist[n-1][m-1] == -1) { // dist 仍是 -1，代表终点不可达 cout << "No\n"; } else { // 否则输出最短路径长度 cout << "Yes\n"; cout << dist[n-1][m-1] << "\n"; } return 0; }利用队列“先进先出”的特性，保证在遍历迷宫时是一层一层往下遍历的——每一轮遍历的点到起点的最短距离均相等。这样就可以保证，在遍历到终点时，这个路径一定是最短的。因为如果还有更短的路径，它在上一轮遍历时就应该出现。BFS要素：记录距离的二维数组记录某点是否访问过的二维数组保证处理次序的队列遍历树的写法相关题目：https://www.luogu.com.cn/problem/P5318int main(){ int n,m; cin >> n >> m; tree.assign(n,vector<int>()); visited.assign(n,false); visited2.assign(n,false); //构建树 for (int i=0;i<m;++i){ int pos,re; cin >> pos >> re; tree[pos-1].emplace_back(re); } //给re排序 for (int i=0;i<n;++i){ sort(tree[i].begin(),tree[i].end()); } //开始bfs queue <int> q; visited2[0]=true; q.emplace(1); while (!q.empty()){ //取出队首节点 int cNode = q.front(); q.pop(); cout << cNode << " "; //尝试不同方向 for (int i=0;i<tree[cNode-1].size();++i){ int nNode=tree[cNode-1][i]; //检查是否访问过 if (visited2[nNode-1]){ continue; } //未访问过即为合法，加入队列等待后续扩散 q.emplace(nNode); visited2[nNode-1]=true; } } return 0; }DP(动态规划)0-1背包问题相关题目：https://www.luogu.com.cn/problem/P1048#include <bits/stdc++.h> using namespace std; /* * 0-1 背包示例（二维数组 DP） * 问题描述： * 给定 N 件物品和一个容量为 W 的背包。 * 第 i 件物品的重量为 w[i]，价值为 v[i]。 * 每件物品只能选 0 次或 1 次，求在不超过背包容量的前提下，能够获得的最大总价值。 * * DP 状态定义： * dp[i][j] 表示：在只考虑前 i 件物品（1..i），背包容量恰好为 j 时能取得的最大价值。 * * 转移方程： * 不选第 i 件物品：dp[i][j] = dp[i-1][j] * 选第 i 件物品：dp[i][j] = dp[i-1][j - w[i]] + v[i] （前提 j >= w[i]） * 取两者最大值即可。 * * 边界 & 初始条件： * dp[0][*] = 0，表示不考虑任何物品时，价值为 0。 * dp[*][0] = 0，表示容量为 0 时，价值为 0。 * * 最终答案： * dp[N][W]，即考虑完 N 件物品后，容量为 W 的最大价值。 */ int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, W; // 输入物品数量 N 和背包容量 W cin >> N >> W; vector<int> w(N + 1), v(N + 1); // 读入每件物品的重量 w[i] 和价值 v[i]，下标从 1 开始 for (int i = 1; i <= N; i++) { cin >> w[i] >> v[i]; } // 构造 N+1 行，W+1 列的 dp 数组，初始值均为 0 vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0)); // 进行状态转移 for (int i = 1; i <= N; i++) { for (int j = 0; j <= W; j++) { // 1. 不选第 i 件物品 dp[i][j] = dp[i - 1][j]; // 2. 选第 i 件物品（前提：背包剩余容量 j >= w[i]） if (j >= w[i]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); } // （可选）打印中间 dp 值以便调试 // cerr << "dp[" << i << "][" << j << "] = " << dp[i][j] << "\n"; } } // 输出最终结果：考虑完所有 N 件物品、容量恰为 W 时的最大价值 cout << dp[N][W] << "\n"; return 0; }dp的本质其实就是：有限背包空间，需要创造最大的价值，方法其实藏在每次的选择之中。每次都有拿和不拿这个物品，我们无法一下子就判断拿不拿，就只能通过二维数组将所有可能存储起来，又保证了不会超出背包空间。然后最后构建完成dp后，就可以取最后一个物品，用满背包空间的值，则为最大的价值。完全背包问题给定：n种物品，每种物品有一个重量 wi 和一个价值 vi。背包容量为 W。每种物品的数量不限。目标：选择若干个物品放入背包，使总重量不超过 W，且总价值最大。n, W = 3, 7 w = [0, 2, 3, 4] # 下标从1开始 v = [0, 3, 4, 5] dp = [0] * (W + 1) for i in range(1, n+1): for j in range(w[i], W+1): dp[j] = max(dp[j], dp[j-w[i]] + v[i]) print(dp[W]) # 输出最大价值有点不一样：最长上升子序列相关题目：https://www.luogu.com.cn/problem/B3637#输入数据 n=int(input()) nums=list(map(int,input().split())) #初始化存储尾巴的数组 tail=[] for i in range(n): if (not tail) or nums[i]>max(tail):#如果尾巴数组为空或者数字比尾巴数组里面的全部数都大 tail.append(nums[i])#将数字放到尾巴数组尾部 else:#否则寻找第一个比该数字大的位置 for j in range(len(tail)): if nums[i]<=tail[j]: tail[j]=nums[i]#将其替换 break#然后就退出寻找，因为是只找第一个 print(len(tail))#然后尾巴数组的长度就是最长上升子序列为何最后尾巴数组的长度就是最长上升子序列的长度？这个我也不清楚。只要记住就行了。有一个基本思想就是：我们在不断优化尾部的数字。假如我给4加到了尾部，结果遍历到后面发现存在3，那就把4换成3，保证尾部的数字尽量小，这样才能最有可能接下去。记忆化搜索用途在进行比较多的递归运算时，将算好的值存入缓存(Python中用dict，C++中用map)，下次遇到同样的值直接从缓存中拿取就行，查询缓存的时间复杂度O(1)。Python代码模板mem={}#用字典存放缓存 def w(a,b,c): global mem#记得全局化变量，因为要读写 key=(a,b,c) if key in mem:#如果在缓存中，直接返回 return mem[key] #否则继续递归 #在这里写递归逻辑... #然后将值存入缓存中 mem[key] = value return value print(w(1111,2222,3333))使用Dict存放函数参数->函数值的键值对，因为有哈希，查询飞速。相关题目https://www.luogu.com.cn/problem/P1464贪心本质在每一步都做出一个局部最优的选择，然后把结果累积下去。1.Kadane 算法算法用途一般用于解决最大连续子段和的问题。算法框架n=int(input()) a=list(map(int,input().split())) #直接开始贪心累加 maxPart=a[0] maxSum=float('-inf') for i in range(1,n): maxPart=max(maxPart+a[i],a[i])#前者是继续取这个，后者是舍弃掉前面的，从这个重新开始 maxSum=max(maxSum,maxPart)#维护一个最大段 print(maxSum)算法原理/如何体现贪心在上方的代码中，维护了一个maxPart变量，比较加上当前数(继续连着)和在当前数重新开一个子序列的大小，取最大。因为如果我加上当前数字还不如我直接取当前数字大，那还不如新开一个子序列，没必要继续延续之前的。由于我会这样一直线性处理到最后，无法判断哪一段子序列是最大的，因此只能再起一个变量来维护子序列的最大值。相关题目https://www.luogu.com.cn/problem/P1115变种一般最大连续子段和必须得求一个答案出来，也就是我们必须至少选择一个数，所以maxPart就只能在拿这个值加上之前的值和只拿当前值来选择。但是我遇到了一道题：https://www.luogu.com.cn/problem/P11642它可以选择不操作。我一开始看到还一头雾水，怎么a[i]还能改成0了，后来理解了。所以此时，只需要把maxPart=max(maxPart+a[i],a[i])改成maxPart=max(maxPart+a[i],0)，也就是只允许正提升。还是需要灵活一些，随机应变。二分查找用途相当于枚举的优化版本，本质还是枚举，只是想明白这个枚举能不能通过某次试验的结果来决定将值变大还是变小，否则不能用二分。就举一个最简单的二分猜数字吧，很多人编程的入门代码，其实就是一种二分查找。当我猜一个数，如果你说“小了”，那我就知道我要给数加大；如果你说“大了”，那我就知道给数减小。这就是每次试验的结果的一种很直接的反馈了。Python代码l=minValue r=maxValue#左指针右指针初始存放题目中合理的枚举范围，减少不必要的枚举 ans=Value#答案初始化为不进入二分的情况下应该输出的结果，防止题目产生hack数据恶心你 while l<=r: mid=(l+r)//2 result=0#用于比较大小的值 #此处插入处理逻辑 if result>certainValue:#如果比特定的值更大，需要减小 r=mid-1 else:#比特定值小或者等于，还能变大 ans=mid#存储下当前的可能答案，万一下次二分不行了就可以直接输出这个 l=mid+1 print(ans)#输出答案相关题目https://www.luogu.com.cn/problem/P2678前缀和一维前缀和用途：告诉你一个数组，需要多次求区间和。代码模板：n = int(input()) a = [0] + list(map(int, input().split())) # a[1]~a[n] s = [0] * (n + 1) for i in range(1, n + 1): s[i] = s[i-1] + a[i] # 区间和 [l, r]: def query(l, r): return s[r] - s[l-1]在构造时需要o(n)，但是在构造完成后，求区间和只需要o(1)。二维前缀和用途：告诉你一个矩阵，需要多次求左上角某个点到右下角某个点区间内值的总和。代码模板：n, m = map(int, input().split()) a = [[0] * (m + 1)] for _ in range(n): a.append([0] + list(map(int, input().split()))) # 下标从1开始 # 计算前缀和 s = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j] # 查询子矩阵 def query(x1, y1, x2, y2): return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]注意：里面的坐标都是1based。时间复杂度：构造时是O(n*m)，求和时O(1)。后缀和# 输入：长度为 n 的数组 a n = len(a) suffix_sum = [0] * (n + 1) # 多开一位，suffix_sum[n]=0 方便处理 # 从后往前累加 for i in range(n - 1, -1, -1): suffix_sum[i] = suffix_sum[i + 1] + a[i] # 现在 suffix_sum[i] 表示从 a[i] 到 a[n-1] 的和 # 例如：区间 [l, r] 的和 = suffix_sum[l] - suffix_sum[r + 1]差分用途差分数组是对原数组的“变化量”进行编码，能让区间加法操作的复杂度从 O(n) 优化到 O(1)。它常出现在算法竞赛和工程开发中，特别是在需要多次区间加减时，可以极大提升效率。如何构建给定一个原数组 A，构建差分数组 D：D[1] = A[1]D[i] = A[i] - A[i-1] （i > 1）如何操作区间加法假设你要将区间 [l, r] 内每个元素加上一个数 x，普通做法需要 O(r-l+1) 的复杂度遍历每个元素。用差分数组，只需两步：D[l] += xD[r+1] -= x（如果 r+1 在范围内）如何还原回原数组最后只需对差分数组做前缀和即可还原出最终结果：A[1] = D[1]A[2] = D[1] + D[2]A[3] = D[1] + D[2] + D[3]...也就是 A[i] = D[1] + D[2] + ... + D[i]代码模板def apply_operations(n, operations): """ n: 原数组长度 operations: 每个元素是 [l, r, x]，表示将区间 [l, r] 加 x 返回：操作后的数组 """ diff = [0] * (n+2) # n+2 是因为要防止越界 for l, r, x in operations: diff[l] += x diff[r+1] -= x # 还原原数组 res = [0] * (n+1) for i in range(1, n+1): res[i] = res[i-1] + diff[i] return res[1:]相关题目https://www.luogu.com.cn/problem/P1083数学基础1.组合数定义$$ \binom{n}{k} = \frac{n!}{k! \, (n-k)!} $$计算方法阶乘公式$$ \binom{n}{k} = \frac{n!}{k! \, (n-k)!} $$递推公式$$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $$乘积形式$$ \binom{n}{k} = \prod_{i=1}^k \frac{n - k + i}{i} = \frac{n(n-1)\cdots(n-k+1)}{k!} $$示例$$ \binom{5}{2} = \frac{5!}{2! \cdot 3!} = \frac{5 \times 4}{2 \times 1} = 10 $$适用于求不同长度的区间和种类时比较好用，别的暂时没发现。见题目：https://www.luogu.com.cn/problem/P86492.质数筛用途需要一次性判断大量数是否为质数。原理/方法如果一个数是质数，那么从它的平方开始，它的倍数一定不是质数。通过这个原理，我们只需要先找到这群数中最大的数，然后以这个为范围，生成质数表。在生成表时，遇到一个质数，可以立马排除后面的一些非质数。生成表的时间复杂度为O(n^2)，查询的时间复杂度为O(1)。代码def get_primes(N): is_prime = [True] * (N + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(N**0.5) + 1):#从2遍历到它的平方根+1 if is_prime[i]:#如果是质数 for j in range(i*i, N+1, i):#将从它本身平方开始的所有倍数都排除 is_prime[j] = False return is_prime # 用法：is_prime[17] 就是 17 是否为质数相关题目https://www.luogu.com.cn/problem/P1036字符串处理位运算在 Python 中，常用的位运算符如下：运算符名称示例说明&按位与a & b两个位都为1时，结果才为1``按位或`a^按位异或a ^ b两个位不同，结果为1，相同为0~按位取反~a每个位取反（0变1，1变0）<<左移a << n各二进制位左移n位，右边补0>>右移a >> n各二进制位右移n位，左边补符号位（补0或补1）示例a = 5 # 二进制 0101 b = 3 # 二进制 0011 print(a & b) # 结果: 1 (0001) print(a | b) # 结果: 7 (0111) print(a ^ b) # 结果: 6 (0110) print(~a) # 结果: -6 (补码表示) print(a << 1) # 结果: 10 (1010) print(a >> 1) # 结果: 2 (0010)有用的技巧检查第k位是否为1：(a >> k) & 1只保留低k位：a & ((1 << k) - 1)交换a,b：a, b = b, a