贪心算法刷题篇(1) 分发饼干与摆动序列
贪心算法不请自来。
455. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
https://leetcode-cn.com/problems/assign-cookies
class Solution {public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int i=0,j=0;for(;i<g.size()||j<s.size();i++){while(i<g.size()&&j<s.size()&&g[i]>s[j]){j++;}if(j>=s.size()||i>=g.size()) break;if(g[i]<=s[j]) j++;}return i;}};
376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
https://leetcode-cn.com/problems/wiggle-subsequence
class Solution {public:int wiggleMaxLength(vector<int>& nums) {if(nums.size()<=1) return nums.size();int count=1;int preDiff=0;int curDiff=0;int index=1;//ture为上升 false为下降，看完答案后发现用diff差值计算更加方便，弃用此方法//bool mark=nums[1]-nums[0];while(index<nums.size()){curDiff=nums[index]-nums[index-1];// if(curDiff*preDiff<0){// count++;// }if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {count++;//preDiff=curDiff要放在这个条件内，如果放在if外会损失preDiff的正负信息(如00112实际上是2，但如果放在外面会得到3)preDiff=curDiff;}index++;}return count;}};