建一个个人网站多少钱,创造与魔法官网站_一起做喜欢的事,搭建wordpress个人博客,班级优化大师app贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。
无固定套路#xff0c;举不出反例#xff0c;就可以试试贪心。
一般解题步骤#xff1a;
1.将问题分解成若干子问题
2.找出适合的贪心策略
3.求解每一个子问题的最优解
4.将局部最优解堆叠成全局最…贪心的本质是选择每一阶段的局部最优从而达到全局最优。
无固定套路举不出反例就可以试试贪心。
一般解题步骤
1.将问题分解成若干子问题
2.找出适合的贪心策略
3.求解每一个子问题的最优解
4.将局部最优解堆叠成全局最优解
分发饼干
思路为了满足更多的小孩就不要造成饼干尺寸的浪费大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩。可以尝试使用贪心策略先将饼干数组和小孩数组进行排序。然后从后向前遍历小孩数组用大饼干优先满足胃口大的并统计满足小孩数量。
class Solution{
public:int findContentChildren(vectorintg,vectorint 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;}
};
从代码中可以看出index用来控制饼干数组的遍历遍历饼干没有再起一个循环而是采用自减的方式这是常用的技巧。
不可以先遍历比骨干再遍历胃口因为外面fori是固定移动的if的index才是符合条件移动的。 反过来先满足胃口小的从小到大去满足
class Solution{
public:int findContentChildren(vectorint g,vectorints){sort(g.begin(),g.end());sort(s.begin(),s.end());int index 0;for(int i 0; i size(); i){if(index g.size() g[index] s[i]){index;}}return index;}
};
//思路一
class Solution{public int findContentChildren(int[] g, int[] s){Arrays.sort(g);Arrays.sort(s);int start 0;int count 0;for(int i 0; i s.length start g.length; i){if(s[i] g[start]){start;count;}}return count;}
}
class Solution{public int findContentChildren(int[] g,int[] s){Arrays.sort(g);//排序胃口Arrays.sort(s);//排序饼干int count 0;int start s.length - 1;//胃口数组长度从start开始遍历倒着遍历先考虑胃口大的//遍历胃口从大到小for(int index g.length - 1;index 0;index--){if(start 0 g[index] s[start]){start--;//从大到小count;//满足一个计数1}}return count;//返回计数}
}
摆动序列
如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。第一个差如果存在地话可能是正数或负数少于两个元素的序列也是摆动序列。
给定一个整数序列返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些元素来获得子序列剩下的元素保持其原始顺序。
思路
贪心 删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。
整体最优整个序列有最多的局部峰值从而达到最长摆动序列。
实际操作中删除操作都不用因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了相当于是删除单一坡度上的节点然后统计长度
这就是贪心所贪的地方 让峰值尽可能地保持峰值然后删除单一坡度上的节点。
在计算是否有峰值的时候大家知道遍历的下标i计算presiff(nums[i] - nums[i - 1])和curdiff(nums[i 1] - nums[i]),如果presiff 0 surdiff 0或者prediff 0 curdiff 0此时就有波动就需要统计。
这是我们思考本题的一个大体思路但本题还要考虑三种情况
1.上下坡有平坡
[122221]删除左边的三个2或者删除右边的三个2摆动长度为3 当i指向第一个2的时候prediff 0curdiff0当 i 指向最后一个2的时候prediff0 curdiff 0.
如果采用删除左面三个2的规则那么当prediff 0curdiff 0也要记录一个峰值因为他是把之前相同的元素都删掉留下的峰值。
我们记录峰值的条件应该是(preDiff 0 curDiff 0)||(preDiff 0curDiff 0)
2.数组首尾两端
本题统计峰值的时候数组最左面和最右面如何统计。
当有两个不同的元素时摆动序列也是2.
例如[2,5],如果靠统计差值来计算峰值个数就需要考虑数组最左面和最右面的特殊情况。
因为我们在计算prediffnums[i] - nums[i - 1]和curdiff(nums[i1] - nums[i])的时候至少需要三个数字才能计算而数组只有两个数字。这里如果只有两个数字且是不同的元素那结果为2.
3.单调坡中有平坡
之前我们在讨论 情况一 相同数字练习的时候prediff 0curdiff 0或者0也记为波谷
为了统一规则。针对序列[2,5],可以假设为[2,2,5],这样就有了坡度即preDiff 0.
[2,2,5]
针对以上情形result初始值为1此时curDiff 0preDiff0,那么result(计算了左面的峰值)最后得到结果为2峰值个数为2即摆动序列长度为2 class Solution{
public:int wiggleMaxLength(vectorintnums){if(num.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;}};
} 3.在上面解法中忽略了第三种情况即如果在一个单调坡度上有平坡例如[1,2,2,2,3,4] 图中我们可以看出应该记录2单调中的平坡不能算作峰值摆动 需要在坡度摆动变化时更新prediff这样prediff在单调区间有平坡的时候就不会发生变化造成误判。
class Solution{
public:int wiggleMaxLength(vctorintnums){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;}}return result;}
};
用动态规划求解
思路
对于我们当前考虑的这个数要么是作为山峰nums[i] nums[i - 1],要么是作为山谷即nums[i] nums[i-1]
设dp状态dp[i][0],表示考虑前i个数第i个数作为山峰的摆动子序列的最长长度。
设dp状态为dp[i][1],表示考虑前i个数第i个数作为山谷的摆动子序列的最长长度
则转移方程为
dp[i][0] max(dp[i][0],dp[j][1] 1),其中0ji且nums[j] nums[i],表示将
