第三十天 第八章 贪心算法 part04 452. 用最少数量的箭引爆气球 435. 无重叠区间 763.划分字母区间

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

主要理解范围区间划分。

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}int findMinArrowShots(vector<vector<int>>& points) {int res=1;sort(points.begin(),points.end(),cmp);for(int i=1;i<points.size();i++){if(points[i][0]>points[i-1][1]){res++;}else{points[i][1]=min(points[i-1][1],points[i][1]);}}return res;}
};

435. 无重叠区间  

同上

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);int res=0;for(int i=1;i<intervals.size();i++){if(intervals[i][0]<intervals[i-1][1]){res++;intervals[i][1]=min(intervals[i-1][1],intervals[i][1]);}      }return res;}
};

763.划分字母区间 

思路：找到最远出现该字母的位置。

class Solution {
public:vector<int> partitionLabels(string s) {int hash[27];for(int i=0;i<s.size();i++){hash[s[i]-'a']=i;}int left=0;int right=0;vector<int> res;for(int i=0;i<s.size();i++){right=max(hash[s[i]-'a'],right);if(i==right){res.push_back(right-left+1);left=right+1;}}return res;}
};