算法面试8-贪心算法

算法面试

C++

发布日期: 2021-05-15

更新日期: 2021-05-15

文章字数: 514

阅读时长: 2 分

阅读次数:

贪心算法

例题455

class Solution{
public:
    int findContentChildren(vector<int> &g,vector<int> &s){
        // 从大到小的排序
        sort(g.begin(),g.end(),greater<int>());
        sort(s.begin(),s.end(),greater<int>());
        int si = 0,gi = 0;
        int res = 0;
        while(gi <g.size() && si <s.size())
        {
            if(s[si] >= g[gi]){
                res ++;
                si++;
                gi++;
            }
            else
                gi++;
            //满足不了最贪心的，寻找下一个次贪心的
        }
        return res;
    }
};

例题 392
给定两个字符串s，t,问s是不是t的子序列

例题435
给定一组区间，问最少删除多少个区间，可以让这些区间互相不重叠
给定区间的七十点永远小于终止点
[1,2],[2,3]不算重叠

动态规划


class Solution{

public:
    int eraseOverlapIntervals(vector<vector<int>> & intervals){
        if(intervals.size() == 0)
            return 0;
        sort(intervals.begin(),intervals.end(),[](const vector &a, const vector<int> &b){
            return a[1] < b[1];
            });
        // memo[i] 表示使用intervals[0..i]的区间能构成的最长不重叠区间序列
        vector<int> memo(intervals.size(),1);
        for(int i =1;i<intervals.size();i++)   
            for(int j = 0;j<i;j++)
                if(intervals[i].start >= intervals[j].end)
                    memo[i] = max(memo[i],1+memo[j]);
                    //以索引[i]结尾的最长序列
        int res = 0;
        for(int i =0;i<memo.size();i++)
            res = max(res,memo[i]);
        return intervals.size() -res;
    }
};

贪心算法：

按照区间的结尾排序，每次选择结尾最早的，且和前一个区间不重叠的区间


class Solution{

public:
    int eraseOverlapIntervals(vector<vector<int>> & intervals){
        if(intervals.size() == 0)
            return 0;
        sort(intervals.begin(),intervals.end(),[](const vector<int> &a ,const vector<int> &b) 
        { 
            return a[1] < b[1];

        });
        // 按照end 升序排序
        int res =1;
        int pre = 0;
        for(int i =1;i<intervals.size();i++)
                if(intervals[i].start >= intervals[pre].end){
                    res ++;
                    pre = i;
                }
        return intervals.size() - res;
    }
};