写一个py的程序在这里先
摆动序列 这道题的贪心算法在于 每次都尽量使得它摆动的最大 这样更有利于摆动继续下去 所以说对于解法 我们只需要对连续递增或者递减的取两端值 只有变号的时候才计数 这样就可以 class Solution { public: int wiggleMaxLength(vector<int>& nums) { if(nums.size()<2){return nums.size();} int prediff=nums[1]-nums[0]; int val=(prediff==0)?1:2; for(int i=2;i<nums.size();i++){ int diff=nums[i]-nums[i-1]; if((diff>0 && prediff<=0) ||(diff<0 && prediff>=0)){ val++; prediff=diff; } } return val; } }; 判断子序列 这道题就是什么狗屁贪心算法吗 我觉得这个是基操 class Solution { public: bool isSubsequence(string s, string t) { if(t.size()<s.size()){return false;} int len1=s.size(); int len2=t.size(); int i=0; int j=0; while((i<s.size()) && (j<t.size())){ if(s[i]==t[j]){ i++; j++; } else{ j++; } } if(i==s.size()){return true;} else{return false;} } }; 最多可以买到的苹果数量 为什么会出错呢 明明很简单 class Solution { public: int maxNumberOfApples(vector<int>& arr) { if(arr.empty()){return 0;} sort(arr.begin(),arr.end()); int count=0; int res=0; for(int i=0;i<arr.size();i++){ count+=arr[i]; res++; if(count>5000){break;} } return res; } }; 跳跃游戏 II 这道题是正儿八经的贪心算法 他不是考虑每一次走能走的最大步数,而是考虑在这些能走的步中找一个下一步能跳最远的 下一步贪心 是这样 class Solution { public: int jump(vector<int>& nums) { int count =0; //需要跳跃的次数 int num=nums.size();//需要跳跃的位置数 int cur=0;//存储最优跳跃点的跳跃的最大位置 int i=0; while (cur<num-1) { //没到最后一个位置的时候进行循环,而出循环说明可以达到最大位置num-1 count++ ; //最远跳跃没有到最大位置时,说明还要进行跳跃 int pre=cur; for (;i<=pre;i++){ //遍历可跳范围之内,找出最佳跳跃点,并用cur 保存新的最远跳跃距离 cur=max(cur,i+nums[i]); } } return count; } }; 坏了的计算器 弱弱的问一句 贪心算法真的存在吗 为什么我觉得这些题没有几个是贪心的 这道题完全依赖于数学问题 因为这里需要我们证明 X的减和乘 应该先换算成 Y的加和除 然后 需要证明如果要除 一定是先除再加的 在这个情况下 我们再来看次数 class Solution { public: int brokenCalc(int X, int Y) { if(X>=Y){return X-Y;} if(Y%2==0){return 1+brokenCalc(X,Y/2);} else{ return 2+brokenCalc(X,(Y+1)/2); } } }; 将数组拆分成斐波那契序列 既然是斐波那契 所以只要确定前两个数 剩下的都是固定的 那么我门只需要遍历前两个数的可能 然后判断是否符合即可