贪心算法专题（Part2）
目录
1. 最优除法
2. 加油站
3. 坏了的计算器
4. 可被三整除的最大和
5. 单调递增的数字
6. 合并区间
7. 无重叠区间
8. 用最少数量的箭引爆气球
1. 最优除法
题目链接：553. 最优除法 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:string optimalDivision(vector<int>& nums) {int n=nums.size();if(n==1) return to_string(nums[0]);if(n==2) return to_string(nums[0])+"/"+to_string(nums[1]);string ret=to_string(nums[0])+"/("+to_string(nums[1]);for(int i=2;i<n;i++){ret+="/"+to_string(nums[i]);}ret+=")";return ret;}
};2. 加油站
题目链接：134. 加油站 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n=gas.size();for(int i=0;i<n;i++)//依次枚举所有起点{int rest=0;//标记净收益int step=0;for(;step<n;step++){int index=(i+step)%n;rest=rest+gas[index]-cost[index];if(rest<0) break;}if(rest>=0) return i;i=i+step;}return -1;}
};3. 坏了的计算器
题目链接：991. 坏了的计算器 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:int brokenCalc(int startValue, int target) {int ret=0;while(target>startValue){if(target%2==0) target/=2;else target+=1;ret++;}return ret+startValue-target;}
};4. 可被三整除的最大和
题目链接：1262. 可被三整除的最大和 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:int maxSumDivThree(vector<int>& nums){const int INF=0x3f3f3f3f;int sum=0,x1=INF,x2=INF,y1=INF,y2=INF;for(auto x:nums){sum+=x;if(x%3==1){if(x<x1) x2=x1,x1=x;else if(x<x2) x2=x;}else if(x%3==2){if(x<y1) y2=y1,y1=x;else if(x<y2) y2=x;}} //分类讨论if(sum%3==0) return sum;else if(sum%3==1) return max(sum-x1,sum-y1-y2);else return max(sum-y1,sum-x1-x2);}
};5. 单调递增的数字
题目链接：738. 单调递增的数字 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:int monotoneIncreasingDigits(int n) {string s=to_string(n);//转化为字符串 int i=0;int m=s.size();//找到第一个递减的位置while(i+1<m&&s[i]<=s[i+1]) i++;if(i+1==m) return n;while(i-1>=0&&s[i]==s[i-1]) i--;s[i]--;for(int j=i+1;j<m;j++) s[j]='9';return stoi(s);}
};6. 合并区间
题目链接：56. 合并区间 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
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;}
};7. 无重叠区间
题目链接：435. 无重叠区间 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end());int left=intervals[0][0];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(a<right){ret++;right=min(b,right);}else{right=b;}}return ret;}
};8. 用最少数量的箭引爆气球
题目链接：452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
题目展示：
题目分析：
代码实现：
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{ret++;right=b;}}return ret;}
};