专业网站维护,淘宝客cms网站模板下载,微信公众号 上传wordpress,wordpress自定义DIV样式仅做学习笔记#xff0c;详细请访问代码随想录
● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和
● 理论基础
有同学问了如何验证可不可以用贪心算法呢#xff1f;
最好用的策略就是举反例#xff0c;如果想不到反例#xff0c;那么就试一试贪心吧。 …仅做学习笔记详细请访问代码随想录
● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和
● 理论基础
有同学问了如何验证可不可以用贪心算法呢
最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。
贪心一般解题步骤 贪心算法一般分为如下四步
将问题分解为若干个子问题 找出适合的贪心策略 求解每一个子问题的最优解 将局部最优解堆叠成全局最优解
这个四步其实过于理论化了我们平时在做贪心类的题目 很难去按照这四步去思考真是有点“鸡肋”。
做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int indexs.size()-1;int result0;for(int ig.size()-1;i0;i--){if(index0s[index]g[i]){result;index--;}}return result;}
};● 376. 摆动序列
class Solution {
public:int wiggleMaxLength(vectorint nums) {
if(nums.size()1){return nums.size();
}
int result1;
int curf0;
int pref0;
for(int i0;inums.size()-1;i){curfnums[i1]-nums[i];if(pref0curf0||pref0curf0){prefcurf;result;}
}
return result;}
};思路 2动态规划
● 53. 最大子序和
