代码随想录算法训练营：27/60

非科班学习算法day27 | LeetCode455:分发饼干，Leetcode376:摆动序列，Leetcode53:最大子数组和

介绍

包含LC的两道题目，还有相应概念的补充。

二、LeetCode题目

1.LeetCode455:分发饼干

题目链接：455. 分发饼干 - 力扣（LeetCode）

题目解析

局部最优的方式是：用当前最大的饼干喂胃口最大的孩子，并依次向后寻找，直到饼干用完或者孩子都吃上。

c++代码如下：

class Solution {
public:
    // 数组排序，倒序遍历
    int count = 0;
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int max_s = s.size() - 1;
        for (int i = g.size() - 1; i >= 0; i--) {
            if (max_s >= 0 && s[max_s] >= g[i]) {
                count++;
                max_s--;
            }
        }
        return count;
    }
};

注意点1：一开始使用的是双循环然后还用break，很难控制，而且后来改对了但是容易超时。所以这里学习了使用标记位置的方法，满足条件就减去一个饼干

注意点2：这里孩子或者饼干的数量是没有固定关系的，所以都可能遍历完，for循环里控制的是孩子的遍历结束，而max_s>=0控制的是饼干的遍历结束

2.Leetcode376:摆动序列

题目链接：376. 摆动序列 - 力扣（LeetCode）

题目解析

我认为代码随想录中这道题的做法有点分类复杂了，虽然最后的代码呈现很简单，分为了三种情况去考虑；我学习了一种写法，我觉得理解更为容易，因为我们需要根据局部峰值的数量来统计全局最优的数量，那么也就是说只需要比较一个点前后两个坡度的正负，甚至值的大小都不重要；还有一个点就是怎么处理相等（平坡）？可以直接跳过循环，比分类要容易的多。

C++代码如下：

class Solution {
public:
    // 开贪！--局部最优为删除坡度中间值--全局最优统计峰值局部峰值个数
    int wiggleMaxLength(vector<int>& nums) {
        // 前坡
        int preDiff = 0;
        // 后坡
        int curDiff = 0;
        // 计数变量
        int count = 1;
        // 处理异常
        if (nums.size() <= 1)
            return nums.size();
        // 统计拐角
        for (int i = 0; i < nums.size() - 1; ++i) {
            curDiff = nums[i + 1] - nums[i];
            if ((preDiff >= 0 && curDiff < 0) ||
                (preDiff <= 0 && curDiff > 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
};

简易c++代码如下：

class Solution {
public:
    // 开贪！--也是统计局部峰值
    int wiggleMaxLength(vector<int>& nums) {
        // 初始化计数变量
        int count = 1;
        // 初始化前坡
        int preDiff = 0;
        // 初始化后坡
        int curDiff = 0;
        // 处理异常
        if (nums.size() <= 1)
            return nums.size();
        // 大于等于两个的序列
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] == nums[i - 1])
                continue;
            curDiff = (nums[i] > nums[i - 1]) ? 1 : -1;
            count += curDiff != preDiff;
            preDiff = curDiff;
        }
        return count;
    }
};

注意点1：这里运用了三目运算符，简化了代码写法，主要的意思就是，我们在遇到相等的时候已经跳过了，那么现在就看是正是负，值不重要

注意点2：在统计量做增加操作的时候，完全可以写成if的形式，这里是用了先用bool返回1或者0，然后做调整操作。

3.Leetcode53:最大子数组和

题目链接：53. 最大子数组和 - 力扣（LeetCode）

题目解析

首先利用暴力遍历的方法，可以计算每一个元素作为开头的子数组的最大和，然后用一个全局变量实时维护。

C++代码如下：

class Solution {
public:
    // 暴力求解
    int max_sum = INT_MIN;
    int maxSubArray(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            int sum = 0;
            for (int j = i; j < nums.size(); ++j) {
                sum += nums[j];
                max_sum = max(max_sum, sum);
            }
        }
        return max_sum;
    }
};

贪心c++代码如下：

class Solution {
public:
    // 开贪！遇到总和为负的就重新开始
    int max_sum = INT_MIN;
    int sum = 0;
    int maxSubArray(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            if (sum > max_sum) {
                max_sum = sum;
            }
            if (sum <= 0) {
                sum = 0; // 初始化--重新统计最大
            }
        }
        return max_sum;
    }
};

注意点1：容易陷入误区，认为如果全是负数的序列就会返回0，但实际上维护的是max_sum，所以不存在该问题，仍然会返回序列单个最大值作为结果。