算法随想Day28【贪心算法】| LC445-分发饼干、LC376-摆动序列、LC53-最大子序和

LC445. 分发饼干

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

LC376. 摆动序列

磕磕碰碰，加上这道题目本身就挺多种需要额外考虑到的特殊情况的。

• 开始审题错误，以为子序列一定要在原数组中是要连续的
• 仅有一个元素或者含两个不等元素的序列也视作摆动序列。那遇到nums.size() == 1 或 == 2时能不能直接返回这个size()呢？不可以，因为size为2，有可能是[0, 0]，此时只能返回1
• 开始就想用了这个思路，即用另一个数组存放1、-1和0分别代表一个元素跟前一个元素的大小关系，相等的时候放0。但是这个想法忽略了两个问题，一是vec[0]应该放什么，如果统一规定vec[0] = 0的话，像[3, 3, 2]、[0, 0, 0]、[0, 0, 0, 3]等多种情况是难以统一管理和处理的。
• 所以最后写了较为统一的一版：
  • 对传入的数组做 相同邻居去重 且 转为为"1"/"-1"数组 的操作（不要“0”）
  • 处理后的数组如果只剩1个元素，说明传入的是[3]或[0, 0, 0]类型的数组
  • 然后再根据第二个元素(如果存在的话)，给vec[0]赋值，最后再从头到尾遍历一次vec数组，即可得到结果

int wiggleMaxLength(vector<int>& nums)
{
    int count  = 1;
    int max = count;
    int size = nums.size();
    vector<int> vec(1);
    for (int i = 1; i < size; ++i)
    {
        if (nums[i] > nums[i - 1])  vec.emplace_back(1);
        else if (nums[i] < nums[i - 1])  vec.emplace_back(-1);
    }
    if (vec.size() == 1)
        return 1;
    else if (vec.size() >= 2)
        vec[0] = vec[0] > vec[1] ? 1 : -1;

    for (int i = 1; i < vec.size(); ++i)
    {
        if (vec[i] == -vec[i - 1])
        {
            ++count;
        }
        max = count > max ? count : max;
    }
    return max;
}

LC53. 最大子序和

没有很感觉到有“贪心算法”的思想

int maxSubArray(vector<int>& nums)
{
    int sum = INT_MIN;
    int max = nums[0];
    for (int i = 0; i < nums.size(); ++i)
    {
        sum += nums[i];
        if (sum > max)
        {
            max = sum;
        }
        if (sum < 0)
        {
            sum = INT_MIN;
        }
    }
}