【算法训练记录——Day31】

1. 理论
2. leetcode455——分发饼干
3. leetcode376——摆动序列
4. leetcode53 —— 最大字序和

1. 理论

算法随想录——贪心

1.1 什么是贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

1.2 什么时候用贪心

刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心
常识性推导加上举反例

1.3 贪心算法一般步骤

1. 将问题分解为若干子问题
2. 找出合适的贪心策略
3. 求解每一个子问题的最优解
4. 将局部最优解堆叠成全局最优解

2.leetcode455——分发饼干

思路：肯定要排序，然后一个一个看能否满足

	int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        
        int gIndex = 0;
        int sIndex = 0;
        while(gIndex < g.size() && sIndex < s.size()) {
            if(s[sIndex] >= g[gIndex]) {
                gIndex++;
            }
            sIndex++;

        }
        return gIndex;
    }

但是为什么这种解法是贪心呢？
贪在要尽可能满足大多数小孩，局部最优解是小饼干喂给胃口小的同学，因此排序

3.leetcode376——摆动序列