贪心算法

题目：

思路：贪心，分别对饼干和胃口升序排序，从小的饼干开始逐一分配。
代码：

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(s.begin(), s.end());
        sort(g.begin(), g.end());
        int i, j;
        for(i = 0, j = 0; i < g.size() && j < s.size(); i++, j++){
            while(j < s.size() && g[i] > s[j])j++;
            if(j == s.size())break;
        }
        return i;
    }
};

135. 分发糖果

思路：比两侧的高，可以选择一次比一边的，跑两遍就行了。我记得之前做过，当时想不明白比两侧的高为什么可以弄成跑两遍，每次各一侧，这很容易理解，两侧满足要求，其中一侧必定满足要求，取大的那个就行。
代码实现：

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> ans(ratings.size(), 1);
        for(int i = 1; i < ratings.size(); i++){
            if(ratings[i] > ratings[i - 1])
                max(ans[i], ans[i] = ans[i-1] + 1);
        }
        for(int i = ratings.size() - 2; i >= 0; i--){
            if(ratings[i] > ratings[i + 1]){
                ans[i] = max(ans[i], ans[i + 1] + 1);
            }
        }
        int res = 0;
        for(int i = 0; i < ans.size(); i++)res += ans[i];
        return res;
    }
};

思路：一开始没想出来，还是看了题解才想到的。
最初考虑的是对左端点进行排序，然后逐一检查可以放置哪些区间，但这样就有个问题，对于[1,2],[1,3]这两个区间该怎么选择，并不好确定。
考虑按左区间进行放置，一开始最小区间是确定的，可以确定已经选择的区间的右端点，然后根据右端点去选择下一个区间。比如：
[ [1,2], [2,3], [3,4], [1,3] ]，
排序后：
[ [1,2], [2,3], [1,3], [3,4]]，
开始时右区间端点right为2，区间[1,2]为右端点最小的它的左侧除了本身没有可以继续放置的区间，
这个时候选择了[[1,2]]，
接着到[2,3]，2等于右端点，可以放置，这个时候右端点更新为3，
到[1,3]，1小于3，放进去会出现重叠，
最后的[3,4]，3等于3，可以放，右端点right更新为4.

这个算法的正确性，对右端点进行排序后，每次放置一个区间进入后，可以确保右端点左侧的区间都是不重叠的。那会不会将结果算少了，不会。
比如以下右端点均为5的有3个，但实际上最终能选择的只有一个。如果又加入了一个[2,3]，那么这个过程中右端点将会更新，5为右端点的筛选将减少。
[1,2], [2,5], [3,5],[4,5],

代码：

class Solution {
public:
    static bool cmp(vector<int> v1, vector<int> v2){
        return v1[1] < v2[1];
    }

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

leetcode刷题

455. 分发饼干

135. 分发糖果

435. 无重叠区间

455. 分发饼干

135. 分发糖果

435. 无重叠区间