贪心算法总结

1. 单调递增的数字

先来看第一种思路：

这种会超时，我们想想一下贪心的策略

直接上代码：

class Solution {
public:int monotoneIncreasingDigits(int n) {string str = to_string(n); // 把数组转化为字符串int pos = 0;while(pos + 1 < str.size() && str[pos] <= str[pos + 1]){pos++;}// 走到这里两种情况// 1.一直走到尾都是递增的if(pos + 1 == str.size()) return n;// 2.走到中途停下来while(pos - 1 >= 0 && str[pos - 1] == str[pos]){pos--;}str[pos]--;for(int i = pos + 1; i < str.size(); i++){str[i] = '9';}return stoi(str);}
};

2. 坏了的计算器

直接上思路：

直接上代码：

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

3. 合并区间

直接上思路：

上代码：

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {// 先对照左端点排序sort(intervals.begin(), intervals.end());// 合并区间int left = intervals[0][0];int right = intervals[0][1];vector<vector<int>> ret;for(int i = 1; i < intervals.size(); i++){int a = intervals[i][0];int 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;}
};

4. 无重叠区间

直接上思路：

直接来写代码：

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end()); // 左端点排序int right = intervals[0][1];int ret = 0;// 移除区间for(int i = 1; i < intervals.size(); i++){int a = intervals[i][0];int b = intervals[i][1];if(right > a) // 重叠{right = min(right, b); // 贪心:删除右端点最大的区间ret++;}else{right = b;}}return ret;}
};

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

我们会发现这个题目依然是一个区间问题，所以做法依然是先对左端点排序，然后再想出一个贪心策略即可，我们只需要最少的弓箭数，那么一支箭应该引爆更多的气球，将两两互相重叠的所有区间都拿出来引爆。

直接上代码：

class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {// 按照左端点进行排序sort(points.begin(), points.end());int right = points[0][1];int ret = 1;// 求互相重叠区间的数量for(int i = 1; i < points.size(); i++){int a = points[i][0];int b = points[i][1];if(a <= right) // 有重叠部分{right = min(right, b);}else{right = b;ret++; // 此时无重复区间,需要再来一支箭 }}return ret;}
};