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

仅做学习笔记，详细请访问代码随想录

● 理论基础
● 455.分发饼干
● 376. 摆动序列
● 53. 最大子序和

● 理论基础

有同学问了如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

贪心一般解题步骤
贪心算法一般分为如下四步：

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解

这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。

做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。

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. 摆动序列

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

思路 2（动态规划）

● 53. 最大子序和