一、分发饼干
题目一：455. 分发饼干
455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
算法的思路是尽可能地满足胃口最小的孩子，这样可以尽可能多地满足更多的孩子。
首先对孩子的胃口值和饼干尺寸进行排序。
然后遍历每块饼干，尝试找到能够满足当前胃口最小孩子的饼干。
如果找到了，就将这个孩子从列表中移除，并继续到下一块饼干，否则就检查下一块饼干。
g是一个整数向量，表示每个孩子的胃口值
s是另一个整数向量，表示每块饼干的尺寸。函数返回能满足的孩子的最大数量。
/*
* @lc app=leetcode.cn id=455 lang=cpp
*
* [455] 分发饼干
*/
// @lc code=start
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
std::sort(g.begin(), g.end());
std::sort(s.begin(), s.end());
int child = 0, cookie = 0;
while (child < g.size() && cookie < s.size()) {
if (g[child] <= s[cookie]) {
child++;
}
cookie++;
}
return child;
}
};
// @lc code=end
二、摆动序列
题目一：376. 摆动序列
376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
-
例如，
[1, 7, 4, 9, 2, 5]是一个 摆动序列 ，因为差值(6, -3, 5, -7, 3)是正负交替出现的。 - 相反，
[1, 4, 7, 2, 5]和[1, 7, 4, 5, 5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
贪心算法的核心思想是遍历数组，记录每次数字序列摆动的变化（即差值由正变负或由负变正），不需要关心摆动的具体大小，只需要知道它是上升还是下降。
nums是一个整数数组，函数返回作为摆动序列的最长子序列的长度。首先检查数组长度，如果长度小于2，则直接返回数组长度。
然后使用两个变量，一个用来存储前一个差值
prevDiff，另一个用于计数摆动序列的长度。接着遍历数组，对于每个新的差值，如果它和前一个差值构成摆动，就更新计数器和
prevDiff。最后返回计数器的值作为最长摆动序列的长度。
/*
* @lc app=leetcode.cn id=376 lang=cpp
*
* [376] 摆动序列
*/
// @lc code=start
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() < 2) {
return nums.size();
}
int prevDiff = nums[1] - nums[0];
int count = prevDiff != 0 ? 2 : 1;
for (int i = 2; i < nums.size(); ++i) {
int diff = nums[i] - nums[i - 1];
if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {
count++;
prevDiff = diff;
}
}
return count;
}
};
// @lc code=end
三、最大子数组和
题目一：53. 最大子数组和
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
贪心算法的实现更加强调在和变为负数时的决策。当当前子数组的和小于0时，意味着它对于后续子数组的和只会有负面影响，因此应该从下一个元素开始重新计算子数组的和。
在这段代码中，遍历数组
nums，不断更新currentSum。如果
currentSum变成负数，将其重置为0，并从下一个元素开始计算新的子数组和。同时持续追踪并更新遇到的最大子数组和
maxSum。文章来源：https://www.toymoban.com/news/detail-801322.html最后返回
maxSum作为答案。文章来源地址https://www.toymoban.com/news/detail-801322.html
/*
* @lc app=leetcode.cn id=53 lang=cpp
*
* [53] 最大子数组和
*/
// @lc code=start
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int currentSum = 0;
for (int num : nums) {
currentSum += num;
maxSum = std::max(maxSum, currentSum);
if (currentSum < 0) {
currentSum = 0;
}
}
return maxSum;
}
};
// @lc code=end
到了这里，关于Day27- 贪心算法part01的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
