day31
代码随想录
2023.12.29
今天开始贪心之路！
贪心的本质很简单，就是选取每一阶段的局部最优，从而达到全局最优。听起来很简单，但是遇到题就不一样了，有的非常简单，简单到你没有意识到自己用了贪心，但有的很难，难到无从下手。
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
当然，这是一个粗略的大致步骤，真正做题要灵活运用。
1. 455分发饼干
这道题就是比较典型的贪心的，局部最优的点在于，针对孩子需求，每次饼干找刚好满足的，也就是说对于g数组中的数，遍历中找s中满足且最小的值！每次遍历达到这种效果，整体遍历就是满足孩子数量最多的了，至于代码写法也有很多了，开始写的时候，还有点写不出来，就多写了一个bool函数，表示饼干是否已经分发给孩子了，
class Solution {
public:
bool find(int num, vector<int>& s, vector<bool>& used){
for(int i=0;i<s.size();i++){
if((num<s[i] || num==s[i]) && used[i]==false){
//找到满足条件的饼干，值满足且最小且未分发给孩子
used[i] = true;
return true;
}
}
return false;
}
int findContentChildren(vector<int>& g, vector<int>& s) {
int result = 0;
vector<bool> used(s.size(), false);
if(s.size()==0){
return result;
}
sort(s.begin(), s.end());
sort(g.begin(), g.end());
for(int i=0;i<g.size();i++){
if(find(g[i],s, used)){
result++;
}
}
return result;
}
};
2. 376摆动序列
这道题，看蒙了，不会做，还要删除节点，剩余节点满足最大摇摆序列，数组删除都麻烦，难不成每次删除然后位置都动一动？看文字讲解后发现，只需要统计满足要求的峰值就行（最大或最小），而峰值判断就是一个点两边差值正负相反。问题实际情况可能有很多种，平坡，一直是上坡、下坡等等，这种情况怎么办，以为又要分别判断了，但最后发现，就算有这些情况，不用做处理啊，直接跳过就行了，我们要的只有坡峰，所以只需要在坡峰时做一些操作就行，首先肯定结果数++，最后就是这个前后差值，后差值并不是值得当前节点紧挨的后插值，而是上次满足坡峰要求是的前差值，到这个点就变成后差值了，因此这个后差值，只需要在满足坡峰要求时更新就好，仔细想想，这个操作也就是将刚才说的各种情况全部跳过去的意思
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;
}
};
3. 53最大子数组和
这道题跟上道题，都感觉贪心有点牵强，这道题就是在遍历时候，当和小于0，也就是负数的时候重新计数，因为，一旦和是负数了，则就是拉低整体和的，所以就不能算最大值，因此当和为负数时，更新和为0，也就是变量调整了起始位置。
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;
