引入二分的思想二分的思想在学习语言基础和数据结构的时候多少都有接触但是实际实现起来就会发现很多的问题最重要的问题就是边界的判断和左右开间的问题不过这些总的来说还是有套路的。二分启动二分查找34.在排序数组中查找元素的第一个和最后一个位置34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode本题是引入二分思想的一道经典题目在这一题主要先了解二分的实现方法。主要先看上面二分函数的写法。闭区间写法class Solution { int lower_bound(vectorint nums, int target) { int left 0, right (int) nums.size() - 1; //由于数组起始为0,right length - 1,所以nums闭区间 [left, right] //左边界 右边界说明此时的二分区间还有未分到底的部分即未将范围缩小到目标数据 // 的情况属于特殊一点的情况 //由于闭区间的写法当左右边界位置相同时还要进行修改边界值否则进入死循环 while (left right) { //由于闭区间的条件所以 //nums[left - 1] target,即左边界左边都比target小 //nums[right 1] target,即右边界右边都比target大 //为了防止产生加法溢出的情况 int mid left (right - left) / 2; //当前数据大于目标值说明我们的数据太小更靠左所以减小右边的边界 if (nums[mid] target) { //由于是闭区间所以不把 right 更新为 mid right mid - 1; // 范围缩小到 [left, mid-1] } else { //由于是闭区间所以不把 left 更新为 mid left mid 1; // 范围缩小到 [mid1, right] } } //由于循环的条件所以结束后得到的left right 1 //这时nums[left - 1] target //nums[left] nums[right 1] target,所以left就是第一个等于target的下标值 return left; } public: vectorint searchRange(vectorint nums, int target) { int start lower_bound(nums, target); if (start nums.size() || nums[start] ! target) { return {-1, -1}; // nums 中没有 target } int end lower_bound(nums, target 1) - 1; return {start, end}; } };左闭右开区间写法class Solution { int lower_bound(vectorint nums, int target) { int left 0, right nums.size(); // 左闭右开区间 [left, right) while (left right) { //区间为左闭右开所以循环条件中不用写 时的情况 int mid left (right - left) / 2; if (nums[mid] target) { //范围缩小到 [left, mid) right mid; } else { //范围缩小到 [mid1, right) left mid 1; } } //因为右边是开区间所以推出循环时 left right //此时nums[left] nums[right] target //所以 left 就是第一个 target 的元素下标 return left; } public: vectorint searchRange(vectorint nums, int target) { int start lower_bound(nums, target); if (start nums.size() || nums[start] ! target) { return {-1, -1}; // nums 中没有 target } // 如果 start 存在那么 end 必定存在 int end lower_bound(nums, target 1) - 1; return {start, end}; } };开区间写法class Solution { int lower_bound(vectorint nums, int target) { //left如果为0那么就成闭区间了所以将left设为-1就成了开区间 int left -1, right nums.size(); //因为 left 为 -1 所以循环的判断条件就需要变成 left 1 while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) { //范围缩小到 (left, mid) right mid; } else { //范围缩小到 (mid, right) left mid; } } //现在循环结束后 left 1 right //此时 nums[left] target 而 nums[right] target //所以 right 就是第一个 target 的元素下标 return right; } public: vectorint searchRange(vectorint nums, int target) { int start lower_bound(nums, target); if (start nums.size() || nums[start] ! target) { return {-1, -1}; // nums 中没有 target } // 如果 start 存在那么 end 必定存在 int end lower_bound(nums, target 1) - 1; return {start, end}; } };我们实现的lower_bound的功能类似STL中的lower_bound查找有序序列中第一个满足 value的元素位置唯一的区别就是我们实现的返回值是 int 类型而STL中返回的是迭代器。所以下面的写法都是一样的找出另一个相同的数的位置我们找比目标值大 1 的数得到了比目标值大 1 的第一个数那么将位置减 1 就找到了最末尾的 target 值。接下来看看库函数的写法class Solution { public: vectorint searchRange(vectorint nums, int target) { int start ranges::lower_bound(nums, target) - nums.begin(); if (start nums.size() || nums[start] ! target) { return {-1, -1}; } int end ranges::upper_bound(nums, target) - nums.begin() - 1; return {start, end}; } };因为用库函数返回的是迭代器所以我们如果要获得下标值的话就要像指针那样减去开头位置。经过本题的思考下一题是一道可以检验你是否理解本题的内容的试着做一下吧。35.搜索插入位置35. 搜索插入位置 - 力扣LeetCode本题只需要挑选一个你喜欢的二分的写法直接用或者用库函数的写法。704.二分查找704. 二分查找 - 力扣LeetCode这一题也很简单还是复现上面的代码然后直接用最后对下标值进行一个条件判断这一题建议也自己写。public: int search(vectorint nums, int target) { int i lower_bound(nums, target); return i nums.size() nums[i] target ? i : -1; } };744.寻找比目标字母大的最小字母744. 寻找比目标字母大的最小字母 - 力扣LeetCode本题与之前的题目有点不太一样之前的都是找比边界小的第一个值而本题则是找比边界大的第一个值所以我们用的就不是 lower_bound 了我们仍然可以手写 upper_bound 或者直接用库函数。class Solution { public: char nextGreatestLetter(vectorchar letters, char target) { auto it ranges::upper_bound(letters,target); return it letters.end() ? *it : letters[0]; } };唯一注意的还是上面说过的引用的库函数的返回类型不一样导致的迭代器的问题。2529.正整数和负整数的最大计数2529. 正整数和负整数的最大计数 - 力扣LeetCode从这一题开始就不只是简单的用库函数再判断了需要对题目的要求进一步思考不过本质还是用二分的思想解决。这一题第一眼看起来的解法就是进行遍历并统计正数和负数的数量最后再返回最大值但是二分也可以有人可能会问。“二分不是一半一半分割容器中数据然后查找一个目标值吗这怎么用”只能说这样想看问题还是太片面了本题中正负数是有 “分割线” 的那就是 “0”所以我们可以找0的位置然后再统计前后两个部分的数据的数量这样就能省下部分的时间。class Solution { public: int maximumCount(vectorint nums) { int pos nums.end() - ranges::upper_bound(nums,0); int neg ranges::lower_bound(nums,0) - nums.begin(); return max(pos,neg); } };总的来说我们一开始认为的暴力遍历实际上是一种查找而二分也是一种查找在有边界线的时候二分的效率是更高的。1385.两个数组间的距离值1385. 两个数组间的距离值 - 力扣LeetCode本题的判定条件是|arr1[i]-arr2[j]| d如果直接用这个条件写肯定很麻烦所以我们需要先转换一下变成对其中一个数组的判定就会简单很多。直接设arr1[ i ]为x所以去掉绝对值再移项就成了x - d arr2[ j ] x d也就是判定arr2中是否有存在于[x - d,x d]的元素若没有就将答案加 1。那要结合二分的思想又该如何设计我们以上一题的思考来说二分也是一种边界问题同时为了判定arr2[ j ]中的元素是否有存在于[x - d,x d]区间的。也就是说arr2中的最大值小于x - d或者arr2中的最小值大于x d所以我们可以根据此边界来通过二分的方法判定。同时使用二分的前提是目标数组是排好顺序的所以我们先将 arr2 进行排序之后用二分判定就可以了。class Solution { public: int findTheDistanceValue(vectorint arr1, vectorint arr2, int d) { ranges::sort(arr2); int ans 0; for(int x : arr1) { //查找 arr2 中是否存在 x - d 的最小的数 auto it ranges::lower_bound(arr2,x-d); //如果存在的数在 arr2 的末尾(指向已经不在 arr2 中了也就是不存在) //或者当前的为了寻找最小的大于 x - d 的值都大于 x //(也就是说想找的最小值都已经大于区间的最大值了) if(it arr2.end() || *itxd) ans; } return ans; } };1170.比较字符串最小字母出现频次1170. 比较字符串最小字母出现频次 - 力扣LeetCode本题由题意得出的直接想法就是分别用 f() 函数统计 queries 和 words 中最小字母的个数然后进行比较题目中说“对于每次查询queries[i]需统计words中满足f(queries[i])f(W)的 词的数目”。也就是说在查询 queries 的过程中我们比较 words 中的最小字母的个数那么不妨先往这个思路靠过去因为如果同时进行 queries 和 words 的查询操作再进行比较是比较麻烦的吗而这样只单独查询 queries 是比较方便的所以先往这个方向去想。怎么才能只查询 queries 的时候就比较 words 呢那就是先用 f() 函数将 words 中的数据给处理好了将 words 中的每个字符串中的最小字母个数存放在一个数组中。然后再遍历 queries 遍历的过程中比较 words 中的数据。怎么比较又是个问题题目中我们比较的都是通过 f() 函数得来的字母个数也就是说最后的比较操作是 queries 中得到的一个数小于哪些已经处理好的 words 数组中的数也就是一种边界。class Solution { public://根据题意直接实现二分的代码 int lower_bound(vectorint nums, int target) { //二分 int left -1; int right nums.size(); while (left1 right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; } else { right mid; } } return right; } vectorint numSmallerByFrequency(vectorstring queries, vectorstring words) { auto f [](string s) { //模拟题目要求用lambda实现 f() 函数 int cnt[26] {0}; for (char c : s) cnt[c - a]; for (int x : cnt) { if (x) return x; } return 0; }; vectorint nums; for(string c : words) nums.push_back(f(c)); //遍历words用f()函数返回每个字符串中最小的字母的个数 sort(nums.begin(),nums.end()); vectorint ans; for(string s : queries) { //先通过 f() 函数统计在 queries 中的字符串中的最小的字母的个数 //然后在 nums 中查找最小的大于 queries 中的最小的字母的个数的下标 //通过nums的大小减去当前的下标值就剩下了后面比当前值大的数量了 //由于我们编写的 lower_bound 的返回值是下标所以在 f() 函数后还需要加 1 int n nums.size() - lower_bound(nums,f(s)1); ans.push_back(n); } return ans; } };2300.咒语和药水的成功对数2300. 咒语和药水的成功对数 - 力扣LeetCode由本题的题意返回值是 spells 中的每个数值分别与 potions 中的每个数值分别相乘得到的结果再进行与 success 进行判断。假如是用循环的方法一个一个算那么 potions 中的数将被遍历多次所以为了减少 potions 被遍历的次数可以转变为对 spells 进行一定的操作之后再进行对 potions 的操作。返回的是统计spells[ i ] * potions[ j ] success 的数量既然直接遍历不方便根据正难则反变成对 spells 或者 potions 其中一个的二分检测。也就是检测 potions[ j ] success / spells[ i ]这样就完成了上面所说的先操作 spells 再操作 potions。另外由于我们本章是二分的思想那么现在再对 potions 设置二分就可以解决该题了。class Solution { public: vectorint successfulPairs(vectorint spells, vectorint potions, long long success) { ranges::sort(potions); //由于spells中的每个数据仅用一次所以可以进行原地修改 for(int x : spells)//这种写法是一种简便的写即“语法糖” x potions.end() - ranges::lower_bound(potions,1.0*success/x); return spells; } };语法糖解释在本题中该语法糖的展开形式如下简单的说就是设定 x 指向spells 的第一个数据在每一次的遍历中 x 仅为该次遍历到的数据。auto it spells.begin(); auto end spells.end(); for(; it ! end; it) { int x *it; //loop code... }2389.和有限的最长子序列2389. 和有限的最长子序列 - 力扣LeetCode本题要求 nums 的元素和小于某个数的最大长度那么也就是说在 nums 中尽可能的构成的元素和的数越多也就是尽可能将较小的数加进元素和之中越满足题意。也就是贪心的思想那么我们在进行计算元素和之前就需要先将 nums 进行排序这样越靠前的数就越小方便进行元素和的求值。将 nums 排序后元素和其实就变成了 nums 的前缀和那么将前缀和分段计算并放入一个数组里面越长的元素和就越靠后并且位置也是一一对应的。同时遍历前缀和数组也方便我们比对查找满足小于 queries 的元素。class Solution { public: vectorint answerQueries(vectorint nums, vectorint queries) { ranges::sort(nums); partial_sum(nums.begin(),nums.end(),nums.begin());//原地计算前缀和 for(int x : queries) x ranges::upper_bound(nums,x) - nums.begin(); return queries; } };通过 partial_sum 可以原地计算 nums 的前缀和因为通过前缀和就可以得出结果而前缀和的后一个元素又是通过前面的前缀和加上当前元素计算得来所以可以将 nums 原地计算得到前缀和数组。然后遍历 queries 找第一个比 queries 中该数大的前缀和的位置再减去 nums 的起始位置就可以得到长度。当然本题可能会有一些例子上产生的小问题。Q示例一中的4、5、1怎么解释A我认为示例给的太恰巧了因为本题本来就是越长越合法而为了满足越长肯定是将数组中较小的数都加起来是更好的解法。就拿示例1来说排序后的 1、2、4也是满足条件的如果说去掉一个 2 来换 5 的话那么如果前面还有别的比 5 小的数的话那肯定就不满足题意了。