day31贪心算法part01| 理论基础 455.分发饼干 376. 摆动序列 53. 最大子序和

本文主要是介绍day31贪心算法part01| 理论基础 455.分发饼干 376. 摆动序列 53. 最大子序和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

455.分发饼干

视频讲解 | 力扣链接
刚开始想到的，但是这样太暴力了，太笨了

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 胃口g 饼干尺寸sint result = 0;sort(s.begin(), s.end());sort(g.begin(), g.end());vector<bool> usedg(g.size(), false);vector<bool> useds(s.size(), false);for (int i = s.size() - 1; i >= 0; i--) {for (int j = g.size() - 1; j >= 0; j--) {// cout << s[i] << " " << g[j] << endl;if (s[i] >= g[j] && usedg[j] == false && useds[i] == false) {result++;usedg[j] = true;useds[i] = true;} } }cout << result;return result;}
};

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 孩子胃口g 饼干尺寸ssort(s.begin(), s.end());sort(g.begin(), g.end());int result = 0;// 从最大的饼干开始int index = s.size() - 1;for (int i = g.size() - 1; i >= 0; i--) {if (index >= 0 && s[index] >= g[i]) {result++;index--;}}return result;}
};

376. 摆动序列

视频讲解 | 力扣链接

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int result = 1;int prediff = 0, currdiff = 0; for (int i = 0; i < nums.size() - 1; i++) {int currdiff = nums[i + 1] - nums[i];if ((currdiff < 0 && prediff >= 0) ||(currdiff > 0 && prediff <= 0)) {result++;prediff = currdiff;}}return result;}
};

ChatGPT给的另一个种方法
nums = [1, 7, 4, 9, 2, 5]

起始时，数组的第一个元素（1）不需要比较。
继续看第二个元素 (7)，由于 7 > 1，说明有一个上升的摆动，所以 up 更新为 2。
继续看第三个元素 (4)，由于 4 < 7，说明有一个下降的摆动，所以 down 更新为 3。
继续看第四个元素 (9)，由于 9 > 4，说明又有一个上升的摆动，所以 up 更新为 4。
继续看第五个元素 (2)，由于 2 < 9，说明又有一个下降的摆动，所以 down 更新为 5。
最后看第六个元素 (5)，由于 5 > 2，说明又有一个上升的摆动，所以 up 更新为 6。

nums = [1,2,2,2,3,4]

起始时，数组的第一个元素（1）不需要比较。
继续看第二个元素 (2)，由于 2 > 1，说明有一个上升的摆动，所以 up 更新为 2。
继续看第三个元素 (2)，由于 2 == 2，两个相等，没有变化，up 和 down 保持不变。
继续看第四个元素 (2)，由于 2 == 2，两个相等，没有变化，up 和 down 保持不变。
继续看第五个元素 (3)，由于 3 > 2，说明有一个上升的摆动，但由于之前的 up 已经是 2，up 保持不变。
最后看第六个元素 (4)，由于 4 > 3，说明有一个上升的摆动，但由于之前的 up 已经是 2，up 保持不变。

由于数组中的相等元素和连续的上升序列，不会影响最终的摆动序列的长度。贪心算法会自动跳过这些不影响摆动的元素，并只在检测到实际的上升或下降时更新 up 和 down 的值。

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) return nums.size();// 遍历数组并且仅在找到符合摆动条件的元素时更新子序列的长度。int up = 1, down = 1;for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) {up = down + 1;} else if (nums[i] < nums[i - 1]) {down = up + 1;}}return max(up, down);}
};

53. 最大子序和

视频讲解 | 力扣链接
如果加和的过程中sum小于0了，那么立即从下一个数开始，因为sum为0了肯定得不到最大的连续和，负数只会拖累总和

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN, sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i];result = sum > result ? sum : result;if (sum < 0) {sum = 0;}}return result;}
};