【算法学习计划】贪心算法（下）

leetcode 991.坏了的计算器

leetcode 56.合并区间

leetcode 435.无重叠区间

leetcode 452.用最少数量的箭引爆气球

leetcode 397.整数替换

leetcode 354.俄罗斯套娃信封问题

leetcode 1262.可被三整除的最大和

leetcode 1054.距离相等的条形码

leetcode 767.重构字符串

结语

这篇将是这个系列的最后一篇文章

本篇文章将会用 9 道题目结束掉这个专题，如果你是不清楚贪心究竟是什么的同学的话，那么可以从这一篇文章开始看：【算法学习计划】贪心算法（上）

（下文中的标题都是leedcode对应题目的链接）

leetcode 991.坏了的计算器

题意是：给你一个数，然后再给你一个target，问你，我们只能用减一和乘二的操作，怎么用最少的步骤从该数字到达target

其实这一道题正着想很麻烦的，因为我们并不知道在某个位置时我们应该乘还是减

但是这道题时典型的正难则反，因为当我们把问题变成从target变成start_val的时候，问题就简单多了

首先，我们这题是没有小数的，这就意味着我们的除法只能被用在偶数上，也就是：

偶数情况只能用除法

另外就是奇数，那么这时奇数只能选择加一了

代码如下：

class Solution {
public:int brokenCalc(int startValue, int target) {int count = 0;if(target <= startValue) return startValue - target;while(target > startValue){if(target % 2 == 1)target++, count++;else target /= 2, count++;}    return count + startValue - target;}
};

leetcode 56.合并区间

这种问题是贪心中很重要的一个part，区间问题

这道题目算是一道纯区间问题，而我们区间问题最主流的还分为两类，一类是求并集，一类是求交集

这道题目就是求并集

面对这类问题，我们首先要做的就是排序

对于C++来说，我们可以直接排序，因为sort默认会对左端点进行排序

当我们排完序之后，我们将前面固定的数组左右端点定义为left、right

而目前比较到的端点的左右我们叫做a、b

我们会面临以下两种情况，一种是有交集，一种是没有，也就是 a <= right 和 a > right 两种

当有交集的时候，其实我们并不着急将结果加进数组里面，因为说不定后面也有数组和这个大集合有交集，所以我们直接让 b = right 即可

而如果我们面临的是没交集的情况，我们只需要将我们之前的 left、right 放入数组中即可，然后将 left、right 变成当前遍历到的这个数组，以这个数组为起点继续向后遍历即可

代码如下：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());int n = intervals.size();int left = intervals[0][0], right = intervals[0][1];vector<vector<int>> ret;for(int i = 1; i < n; i++){int a = intervals[i][0], b = intervals[i][1];if(a <= right) right = max(right, b);else{ret.push_back({left, right});left = a, right = b;}}    ret.push_back({left, right});return ret;}
};

leetcode 435.无重叠区间

这道题目也是一道区间问题，其中，我们要的是删最少的数组使他们所有数组不重叠

那么我们可以贪的一个点就是，我们只需要删那些区间大的，因为区间大的会和更多区间有交集

left---------------------right

a--------------------b

以这两个区间为例子，left、right 代表我们固定一个数组的区间来进行比较

下面的 a、b 代表的就是我们固定完数组之后我们遍历接下来的数组

所以我们会面临以下的情况：

以下的情况，删上面的，也就是让 right = b

left---------------------right

a---------b

以下的情况，不用管

left---------------------right

a---------------------b

以下的情况，删下面的，还是不用管

left---------------------right

a---------------------------------b

以下的三种情况，删下面的，第一个right=b，剩下两个不管

left---------------------right

a---------b

left---------------------right

a-----------b

left---------------------right

a-----------------------b

最后一种情况，其实还是right=b

left---------------------right

a-------------b

不同于 a > right 的情况，上面所有的 right = b 的情况，其实都是 right = min(right, b)，因为我们是不断选择小的区间，这样子才有更小的概率有交集

代码如下：

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end());int ret = 0, n = intervals.size();int left = intervals[0][0], right = intervals[0][1];for(int i = 1; i < n; i++){int a = intervals[i][0], b = intervals[i][1];if(a < right) // 有重叠{ret++;right = min(right, b);}else right = b;}    return ret;}
};

leetcode 452.用最少数量的箭引爆气球

简单解释以下题意，就是给你很多数组，然后只要两个数组之间有交集的，我们就可以用一支箭将这里面的气球打爆

简单来说，就是求这些数组里面，有几个交集

其实经过了前面两道区间问题之后，这一道题目最多就算是一个小变形了

因为，我们的做法其实还是和前面的一样

首先固定一个数组，然后以这个数组为起点，每遍历到一个新的数组的时候，我们就去看这两个数组之间的交集即可，当遍历到一个新的数组和我们之前遍历的交集没有交集的话，那么就证明这个数组是不能和前面的数组一起被一支箭打爆的，所以我们需要重新更新固定的 left、right 下标

代码如下：

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(), points.end());int ret = 0, n = points.size();int left = points[0][0], right = points[0][1];for(int i = 1; i < n; i++){int a = points[i][0], b = points[i][1];if(a <= right) left = max(left, a), right = min(right, b);else{ret++;left = a, right = b;} }    ret++;return ret;}
};

leetcode 397.整数替换

这里我们需要分两种情况，分别是(以下两种都是二进制的形式)：

.............01

.............11

一种是01的情况，那么这种 +1 就变成10，而我们减一之后直接变为00，两种都是偶数，但是显然 -1 的情况更好

还有一种就是11，+1 就是00（前面如果全是 1 的话，那么就都会变成 0，比如100111111，就会变成 101000000），另一种 -1 就是 10，显然 +1 的情况更好

但是有一种情况，也就是刚好为 3 的时候，也就是只为 11（二进制），这时候我们减一除二即可，加一要多一步

另外，我们如何知道最后面是01还是11，模4即可，也就是%4，如果结果为1，那就是01，为3就是11

代码如下：

class Solution {
public:int integerReplacement(int n) {long n1 = (long)n;int ret = 0;while(n1 > 1){if(n1 % 2 == 0)n1 /= 2;else{if(n1 == 3 || n1 % 4 == 1)n1 -= 1;else if(n1 % 4 == 3)n1 += 1;}ret++;}    return ret;}
};

leetcode 354.俄罗斯套娃信封问题

首先，你要做明白这道题目是有门槛的，也就是将leetcode中的最长递增子序列的贪心做法整明白

而要学会最长递增子序列的贪心做法，又需要你掌握动态规划和二分查找

如果想看看相关解法的，可以看以下两个链接，一个是最长递增子序列的dp解法，一个是贪心解法

【算法学习计划】动态规划 -- 子序列问题、第一题

【算法学习计划】贪心算法（上）、第五题

然后就是这道题目了，首先，先假设一种情况，也就是我们所有的左端点都不相等

那么我们就对他们进行一个排序之后，左端点一定是严格递增的，那么换个角度想，此时我们是不是就不需要考虑左端点了，因为左端点一定可以装得进后面的信封中，那么需要比较的就只有右端点了，也就将问题转换成了，在所有右端点中求一个最长递增子序列

但是可惜的是，这道题目是有重复左端点的情况的

那么我们的解决方法就是，重写sort里面的排序方法

如果左端点相同的话，我们就从大到小排序，否则就是从小到大

因为如果左端点相等，那么我们从大到小排序的话，那么这个左端点里面，我们一定只会选一个，试想一下，假如左端点为 2，右端点为 6、5、4、3、2、1，那么此时屏蔽左端点之后，我们求最长递增子序列是否就一定只能选得到一个

然后接下来的就是递增子序列的逻辑了

由于不用考虑子序列中的前面具体怎么排序，我们只需要考虑最后一个端点即可，所以我们就创建一个数组，接着我们就不断更新这个数组，数组里面的每一个数都代表以这个数为结尾时候的最长递增子序列，而这个数字在数组中对应的位置就是这个子序列的长度

如果当前数比数组中的数小，那就替换，比他大，那就和下一个进行比较如果比所有的都大，那么就push_back在数组最后面

最后返回这个新数组的size即可

代码如下：

class Solution {
public:int maxEnvelopes(vector<vector<int>>& envelopes) {sort(envelopes.begin(), envelopes.end(), [&](const vector<int>& a, const vector<int>& b){return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];});vector<int> ret;ret.push_back(envelopes[0][1]);for(int i = 1; i < envelopes.size(); i++)    {int b = envelopes[i][1];if(b > ret.back())ret.push_back(b);else{int left = 0, right = ret.size() - 1;while(left < right){int mid = (left + right) >> 1;if(ret[mid] < b)left = mid + 1;else right = mid;}ret[left] = b;}}return ret.size();}
};

leetcode 1262.可被三整除的最大和

这道题也是需要分情况讨论

首先我们要求怎么加才能最大

那如果要贪心一点的话，我们就直接就将所有数字全部加起来，然后再想我们需要删除什么数字然后使他能被三整出即可

那么全部加完之后，我们就有三种可能

第一种是sum 刚好能被 3 整除，这种直接返回即可

第二种是sum%3 == 1，这种我们就需要找出所有数中，被三%后为 1 的最小的数字，减去这个数字即可，当然并不只有这一种，因为%3之后还可能等于 2，如果有两个%3 == 2 的数，我们可以减去这两个数（前提是存在），之后再和%3 == 1 的结果进行一个比较，最后求一个最大值即可

第三种是sum%3 == 2，这种和上面%3==1 的情况一样，我们只需要求出%3==1 的最小和次小的数，还有%3==2 的最小的数，最后减完比较即可

代码如下：

class Solution {
public:int maxSumDivThree(vector<int>& nums) {int sum = 0;int one_1 = INT_MAX, one_2 = INT_MAX, two_1 = INT_MAX, two_2 = INT_MAX;for(int i = 0; i < nums.size(); i++){int a = nums[i];sum += a;if(a % 3 == 1){if(a <= one_1){one_2 = one_1;one_1 = a;  }else if(a > one_1 && a <= one_2) one_2 = a;}else if(a % 3 == 2){if(a <= two_1){two_2 = two_1;two_1 = a;  }else if(a > two_1 && a <= two_2) two_2 = a;}}if(sum % 3 == 0) return sum;else if(sum % 3 == 1){int ret1 = 0, ret2 = 0;if(one_1 != INT_MAX) ret1 = sum - one_1;if(two_1 != INT_MAX && two_2 != INT_MAX) ret2 = sum - two_1 - two_2;return max(ret1, ret2);}else{int ret1 = 0, ret2 = 0;if(two_1 != INT_MAX) ret1 = sum - two_1;if(one_1 != INT_MAX && one_2 != INT_MAX) ret2 = sum - one_1 - one_2;return max(ret1, ret2);}return 0;}
};

leetcode 1054.距离相等的条形码

首先这道题说了，必定是有答案的，所以出现次数最多的那个数字长度必然在（n+1）/ 2 之内

我们简单运用鸽巢原理或者抽屉原理想一想就知道了，如果大于（n+1）/ 2 的话，那么必然有两个数会被放到一个巢里面，那么就不是题目说的分开放的情况

所以我们可以先遍历一遍，然后将所有的数字放进哈希表里面，在遍历的同时我们找出出现次数最多的数字和出现的次数，这样我们就先将这个数字处理了

具体的处理方式是，将这个数单独拿出来，然后从 0 位置开始，隔一个位置放一个，这样后面的数就只能是分开放的

至于后面的数字，随便放即可，因为都不影响，没有一个数出现的次数超过（n+1）/ 2，那就随便放

代码如下：

class Solution {
public:vector<int> rearrangeBarcodes(vector<int>& b) {unordered_map<int, int> hash;int max_val = 0, max_time = 0;for(auto e : b){if(max_time < ++hash[e]){max_time = hash[e];max_val = e;}}     int n = b.size();int index = 0;vector<int> ret(n);for(int i = 0; i < max_time; i++){ret[index] = max_val;index += 2;}hash.erase(max_val);for(auto [a, b] : hash){for(int i = 0; i < b; i++){if(index >= n) index = 1;ret[index] = a;index += 2;}}return ret;}
};

leetcode 767.重构字符串

这道题目和上一道几乎一摸一样，只不过就是答案不一定是确定的

那么我们直接在找完出现次数最多的那个数字以及其出现的次数之后，我们看一下这个数字有没有超过（n+1）/ 2 就可以了，只要超过了，那就肯定是不正确的，如果没有超过那就是有答案的

代码如下：

class Solution {
public:string reorganizeString(string s) {unordered_map<char, int> hash;char max_val;int max_time = 0;for(auto e : s){if(max_time < ++hash[e]){max_time = hash[e];max_val = e;}}     int n = s.size();if(max_time > (n + 1) / 2) return "";int index = 0;string ret(n, '#');for(int i = 0; i < max_time; i++){ret[index] = max_val;index += 2;}hash.erase(max_val);for(auto [a, b] : hash){for(int i = 0; i < b; i++){if(index >= n) index = 1;ret[index] = a;index += 2;}}return ret;   }
};