贪心算法 part04

文章参考来源代码随想录

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

局部最优：用一支箭尽可能多的射重叠的气球

全局最优：用最少数量的箭射气球

这里先排序，因为给定的数组必定有一个气球。所以箭总数初始化为1

判断两个气球是否重叠：

points[i][0]>points[i-1][1]（不重叠）

两个气球重叠之后判断第三个气球是否重叠：

这里可以使用更新第二个气球右边界处理

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

435. 无重叠区间

本题使用右边界排序

从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

 这里我们初始化非重叠区间数量为1

再定义一个区间分割点，当当前区间分割点小于下一个区间左边界时更新为下一个区间的右边界，此时说明两区间没有重叠，所以计数器往上加一。

class Solution {
public:
    static bool cmp(vector<int>&a,vector<int>&b){
        return a[1]<b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int count=1;// 记录非交叉区间的个数
        int end=intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            if(end<=intervals[i][0]){
                end=intervals[i][1];
                count++;
            }
        }
        return intervals.size()-count;
    }
};

 763.划分字母区间

用一个计数数组记录每一个字母最后出现的位置。

从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

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