代码随想录算法训练营第三十一天|455.分发饼干，376. 摆动序列，53. 最大子序和

本文主要是介绍代码随想录算法训练营第三十一天|455.分发饼干，376. 摆动序列，53. 最大子序和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心算法

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
贪心算法没有模板。

题目：455.分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j]= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

在这里插入图片描述

题目链接/讲解链接
https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

思路

为了满足更多的小孩，就不要造成饼干尺寸的浪费。
大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略，先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。

解题

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int index = s.size() - 1; // 饼干数组的下标int result = 0;for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口if (index >= 0 && s[index] >= g[i]) { // 遍历饼干result++;index--;}}return result;}
};

题目：376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如，[1,7,4,9,2,5]是一个摆动序列，因为差值(6,-3,5,-7,3)是正负交替出现的。相反，[1,4,7,2,5]
和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

在这里插入图片描述

题目链接/讲解链接：
https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

解题

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) return nums.size();int curDiff = 0; // 当前一对差值int preDiff = 0; // 前一对差值int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值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; // 注意这里，只在摆动变化的时候更新prediff}}return result;}
};

题目：53. 最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

在这里插入图片描述

题目链接/讲解链接：
https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

思路

第一种是暴力求解。
两层for循环，外层for循环控制索引开始的地方，内层for循环控制求和。
但是容易超时。

第二种是利用贪心算法的思想。
“贪心”体现在哪里？
数组中有正有负，要想尽可以得到较大的和，就要尽可能的避开负数，负数会拉低总和。

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素“连续和”只会越来越小。

全局最优：选取最大“连续和”。

解题

1、暴力求解

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) { // 设置起始位置count = 0;for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值count += nums[j];result = count > result ? count : result;}}return result;}
};

2、贪心

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) {count += nums[i];if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）result = count;}if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和}return result;}
};