贪心算法

• (455)分发饼干

如果 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;
    }
};

• (392)判断子序列

给定字符串 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();
    }
};

• (435)无重叠区间

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

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;
    }
};

---

• 分类： leetcode
• 标签： 计算机