贪心算法

由 笔尖 发布

如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。使用贪心算法,将最大的饼干优先分配给最贪心的孩子。

class Solution {
public:
    int findContentChildren(vector<int> &g, vector<int> &s) {
        int res = 0;
        int gi=0, si=0;
        sort(g.begin(), g.end(), greater<int>());
        sort(s.begin(), s.end(), greater<int>());
        while (gi < g.size() && si < s.size()) {
            if (g[gi] <= s[si]) {
                res++;
                gi++;
                si++;
            } else
                gi++;
        }
        return res;
    }
};

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int ti = 0, si = 0;
        while (ti < t.size() && si < s.size()) {
            if (s[si] == t[ti])
                si++;
            ti++;
        }
        return si==s.size();
    }
};

给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。按照区间右边界值从小到大排序,优先从前选择,这是因为区间结尾的越早,留下给剩余数组的空间就越大,重叠可能性越低。

class Solution {
private:
    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[1]<b[1];
    }

public:
    int eraseOverlapIntervals(vector<vector<int>> &intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int n = intervals.size();
        if(n==0)
            return 0;
        int pre=0,res=1;
        for(int i=1;i<n;i++){
            if(intervals[i][0]>=intervals[pre][1]){
                res++;
                pre=i;
            }
        }
        return n-res;
    }
};

暂无评论

发表评论