「代码随想录算法训练营」第二十三天 | 贪心算法 part1
455. 分发饼干
题目链接：https://leetcode.cn/problems/assign-cookies/
题目难度：简单
文章讲解：https://programmercarl.com/0455.分发饼干.html
视频讲解：https://www.bilibili.com/video/BV1MM411b7cq
题目状态：初次有贪心算法的总体概念，有点懵
思路：
先将饼干尺寸大的满足胃口大的小孩，直到遍历完。
代码：
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 res = 0;
for(int i = g.size() - 1; i >= 0; --i) {
if(index >= 0 && s[index] >= g[i]) {
res++;
index--;
}
}
return res;
}
};
376. 摆动序列
题目链接：https://leetcode.cn/problems/wiggle-subsequence/
题目难度：中等
文章讲解：https://programmercarl.com/0376.摆动序列.html
视频讲解：https://www.bilibili.com/video/BV17M411b7NS
题目状态：贪心好难，只能看题解，自己做一点思路也没有
思路：
记录一下每个元素的前后坡度（有正负的），然后判断前后坡度符号是否一致，如果不一致就加1，如果一致就跳过。
注意：当有平坡出现的时候，只需要记录一次，并且前坡只有在发生改变的时候在需要变化。
代码：
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() == 1) return 1;
int res = 1;
int prediff = 0;
int curdiff = 0;
for(int i = 0; i < nums.size() - 1; ++i) {
curdiff = nums[i + 1] - nums[i];
if((prediff >= 0 && curdiff < 0) ||
(prediff <= 0 && curdiff > 0)) {
res++;
prediff = curdiff;
}
}
return res;
}
};
53. 最大子数组和
题目链接：https://leetcode.cn/problems/maximum-subarray/
题目难度：中等
文章讲解：https://programmercarl.com/0053.最大子序和.html
视频讲解：https://www.bilibili.com/video/BV1aY4y1Z7ya
题目状态：还是学习思路...
思路：
先遍历前面的和，当前面的和为负数的时候，那个前面所有的内容相加就对后面的元素没有作用，直接从后面元素开始，一直遍历结束。期间会记录所有遍历的最大值。
代码：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int count = 0;
int res = INT_MIN;
for(int i = 0; i < nums.size(); ++i) {
count += nums[i];
if(count > res) res = count;
if(count <= 0) count = 0;
}
return res;
}
};