算法训练day34 贪心算法理论，455.376.53

理论基础

概念

选择每一阶段的最优解，从而达到全局最优
一般步骤（鸡肋
- 问题分解为子问题
- 找出合适的贪心策略
- 求解每一个子问题的最优解
- 将局部最优叠加成全局最优解

455.分发饼干

题目

https://leetcode.cn/problems/assign-cookies/

题解

代码随想录 (programmercarl.com)

优先用尽可能小的饼干喂饱孩子

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

376. 摆动序列

题目

376. 摆动序列 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

判断单调区间，节点数为区间数+1

class Solution
{
public:
    int wiggleMaxLength(vector<int> &nums)
    {
        if (nums.size() <= 1)
            return nums.size();
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值
        int result = 0;  // 记录增减区间个数，峰值数比区间数大一
        for (int i = 0; i < nums.size() - 1; i++)
        {
            curDiff = nums[i + 1] - nums[i];
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0))
            {
                result++;
                preDiff = curDiff;
            }
        }
        return result+1;
    }
};