当前位置:   article > 正文

码随想录算法训练营第二十七天|贪心算法、分发饼干、摆动序列、最大子数组和

码随想录算法训练营第二十七天|贪心算法、分发饼干、摆动序列、最大子数组和

贪心算法理论基础

1.什么是贪心

贪心的本质是选择每一阶段的局部最优,从而达到全局最优

例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?指定每次拿最大的,最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。

2.贪心没有套路,说白了就是常识性推导加上举反例

分发饼干 leetcode 455

拿最大的饼干给胃口最大的孩子,先对数组排序,之后使用双指针思想。

  1. class Solution {
  2. public:
  3. int findContentChildren(vector<int>& g, vector<int>& s) {
  4. int index1=g.size()-1,index2=s.size()-1;
  5. int count=0;
  6. sort(g.begin(),g.end());
  7. sort(s.begin(),s.end());
  8. while(index2>=0&&index1>=0){
  9. if(s[index2]>=g[index1]){
  10. count++;
  11. index1--;
  12. index2--;
  13. }else index1--;
  14. }
  15. return count;
  16. }
  17. };

摆动序列 leetcode 376

首先假设最前面加一个平坡(解决nums.size()=2的情况),以及最右边有一个摆动res=1(解决所有元素相同的情况),for循环中的if条件preDiff带等号是考虑到有连续相同元素的情况(不带等号就会少加一)。

  1. class Solution {
  2. public:
  3. int wiggleMaxLength(vector<int>& nums) {
  4. if(nums.size()<=1) return nums.size();
  5. int curDiff=0,preDiff=0;
  6. int res=1;
  7. for(int i=0;i<nums.size()-1;i++){
  8. curDiff=nums[i+1]-nums[i];
  9. if((preDiff<=0&&curDiff>0)||(preDiff>=0&&curDiff<0)){
  10. res++;
  11. preDiff=curDiff;
  12. }
  13. }
  14. return res;
  15. }
  16. };

最大子数组和 leetcode 53

如果当前和为负数,那么就放弃从下一个数开始重新累加。

  1. class Solution {
  2. public:
  3. int maxSubArray(vector<int>& nums) {
  4. //if(nums.size()==1) return nums[0];
  5. int res=INT_MIN;
  6. int sum=0;
  7. for(int i=0;i<nums.size();i++){
  8. sum+=nums[i];
  9. if(sum>res) res=sum;
  10. if(sum<=0) sum=0;
  11. }
  12. return res;
  13. }
  14. };

出现的错误

把if(sum<=0) sum=0;写在if(sum>res) res=sum;前面,应该先判断当前和与res的大小并对res赋值,如果都是负数的情况下,输出就是0,其实应该输出数组中第一个负数。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/943248
推荐阅读
相关标签
  

闽ICP备14008679号