贪心系列专题篇三

目录

单调递增的数字

坏了的计算器

合并区间

无重叠区间

用最少数量的箭

---

声明：接下来主要使用贪心法来解决问题！！！

单调递增的数字

题目

思路

如果我们遍历整个数组，然后对每个数k从[k,0]依次遍历寻找“单调递增”的数字，对于本题数据量最大为10^9,显然是会超时的,下面将介绍一种贪心解法。

把数字转换成字符串，然后从头到尾遍历整个字符串，当遇到后一个字符小于当前一个字符时，把当前字符-1，之后的字符全都修改正字符'9'。如下：

但是这种方法还是有缺陷的，比如下面的这种情况，

因此，我们需要对上面的贪心策略进行修改，修改后的贪心策略如下：

贪心策略

把数字转换成字符串，然后从头到尾遍历整个字符串，当遇到后一个字符小于当前一个字符时，向前寻找和当前字符相等的字符，把与当前字符相等的字符的最左段字符字符-1，之后的字符全都修改正字符'9'。如下：

代码

class Solution {
public:int monotoneIncreasingDigits(int n) {string s=to_string(n);int m=s.size();int i=0;while(i+1<m && s[i]<=s[i+1])i++;if(i+1==m) return n;else{while(i-1>=0 && s[i-1]==s[i])i--;s[i]=s[i]-1;for(i=i+1;i<m;i++)s[i]='9';}return stoi(s);}
};

坏了的计算器

题目

思路

因为可对startValue进行乘2和减1操作，但是要想由startValue变换成target，毫无确定的头绪可言.

贪心策略

采用“正难则反”的思想，我们可以想想如何将target变换成startValue，此时有两种操作，分别为除2和加1，而此时可以分两种情况进行讨论，分别是：

当target<startValue,当target为奇数时，由于startValue为整数，此时只能进行+1操作；

                            当target为偶数时，要想变换成startValue，此时只能进行+1操作，

即当target<startValue时,变换操作次数为startValue-target.

当target>startValue,当target为奇数时，由于startValue为整数，此时只能进行+1操作；

                            当target为偶数时，要想变换成startValue，可进行除2和+1操作混合进行，但是如果混合操作进行的话，要想让target变换成startValue，此时的操作次数是大于只进行除2操作的，因此此时只进行除2操作，

即当target>startValue时,先判断target的奇偶性，进行对应操作，直到target=startValue，或者target<startValue，然后进行target<startValue对应的规则。

代码

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

合并区间

题目

思路

首先我们先对集合按区间左端点进行排序，因为如果不排序的话，比较两个区间左端点的大小是需要不断遍历集合的，对集合按区间左端点进行排序后的情况如下：

基准参考区间的左端点记为left，右端点记为right，后一段区间的左端点记为a，右端点记为b。

贪心策略

对于a<=right的区间，需要进行合并，此时需要进行right=max(right,b)的操作即可；

对于a>right的区间, 不需要进行合并, 此时需要进行left=a，right=b和记录已合并区间的操作即可。

但是最后还需要记录最后一个区间。

代码

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {int n=intervals.size();sort(intervals.begin(),intervals.end());vector<vector<int>> ret;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(right>=a)right=max(right,b);else{ret.push_back({left,right});left=a,right=b;}}ret.push_back({left,right});return ret;}
};

无重叠区间

题目

思路

首先我们先对集合按区间左端点进行排序，因为如果不排序的话，比较两个区间左端点的大小是需要不断遍历集合的，对集合按区间左端点进行排序后的情况如下：

基准参考区间的左端点记为left，右端点记为right，后一段区间的左端点记为a，右端点记为b。

贪心策略

题目要求保证无重复区间需要删除区间的最少数量，等价于尽可能保留更过数量的区间，使用一个变量ret统计删除区间的数量。

对于a<=right的区间，需要进行删除一个右端点较大的那个区间，此时需要进行right=min(right,b)和ret++的操作即可；

对于a>right的区间, 只需要进行right=b的操作即可。

代码

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int n=intervals.size();sort(intervals.begin(),intervals.end());int ret=0;int 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);}elseright=b;}return ret;}
};

用最少数量的箭引爆气球

题目

思路

首先我们先对集合按区间左端点进行排序，因为如果不排序的话，比较两个区间左端点的大小是需要不断遍历集合的，对集合按区间左端点进行排序后的情况如下：

基准参考区间的左端点记为left，右端点记为right，后一段区间的左端点记为a，右端点记为b。

这道题不同于前两道题的明显之处是前两道题求的是并集，而本道题求的是交集。

即求的是下面第二张图的交集个数，而非第一张图。

使用变量ret记录重叠区间个数。

贪心策略

当a<=right时，进行操作right=min(right,b)即可；

当a>right时，进行操作right=b,ret++即可。

代码

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