【Leetcode每日一刷】贪心算法01：455.分发饼干、376. 摆动序列、53. 最大子序和

文章目录

• 前言：贪心算法
• 一、455.分发饼干
• 二、376. 摆动序列
• 三、53. 最大子序和

  前言：贪心算法

  参考和学习：代码随想录

  贪心算法并没有任何套路，它的本质是寻找局部最优解。

  严格的数学证明为以下两者

  • 数学归纳
  • 反证

    前者基本上是劝退了，反证就是看能不能对你想出的这种算法or模拟举出反例。与其叫贪心，我个人现在更愿意将其理解为模拟，偏常识形式的，没有一个统一的套路。可以从下面的题目中看出。

    一、455.分发饼干

    思路：

    这题比较简单，当然是先用小的去喂饱小的，依次把饼干由小到大喂完，喂的孩子最多。反例举不出来这种方法不行。

    硬要解释的话，可以把“先用小的去喂饱小的”理解为局部最优解：给每个孩子满足胃口且尺寸最小的饼干。然后顺序进行便得到了全局最优解。

    步骤

    • 首先对g和s数组进行排序

    • 外层循环遍历s，表示对每个饼干进行分发。

    • 用坐标ig表示遍历到了哪个孩子

      • 如果此时s[i]>g[ig],ig++
      • 否则ig不变，i++，看看还有没有更大的饼干能满足当前孩子的胃口

      • 最后返回ig，表示当前喂了多少个孩子

        ‍♀️完整代码

        class Solution {public:    int findContentChildren(vector& g, vector& s) {        sort(g.begin(),g.end());        sort(s.begin(),s.end());        int ig = 0;        for(int i = 0; i = g[ig]){                ig++;            }else{                continue;            }        }       return ig;    }};

        二、376. 摆动序列

        力扣题目链接

        思路：

        这题的话，用贪心做复杂了。其实弄清楚这个题的本质：数一数：上坡+下坡，加起来即可。这里用图来表示：

        ‍♀️完整代码

        class Solution {public:    int wiggleMaxLength(vector& nums) {    int flag = -1;//0表示下坡，1表示上坡    //if (nums.size() == 0) return 1;    int ans = 0;    for(int i = 1; i  0) && (flag != 1);        if(down){            flag = 0;            ans++;        }else if (up){            flag = 1;            ans++;        }    }    return ans+1;//res是两两比较得来的值，差一个边界值要+1!    }};

        三、53. 最大子序和

        题目链接

        思路：

        这题的暴力解法就是两层for循环，不在这里赘述。

        这题我没想出来的核心是：我没想到最终答案由“擂台法”得来。当前的连续子序列的和不一定是答案，它只是当前的计算，它和已经记录下来的当前的最大连续和进行相比，如果小于它，则不更新答案。

        那再说回这道题的思路：

        • 局部贪心：-1和2，当然不要-1，因为前面是负数总会拖累后面的。于是放弃前面的负数，用后面的2重新当作子序列的开头。
        • 全局最优：一旦当前子序列的和为负数，立马放弃当前子序列，从下一个元素开头，重新计算子序列的和。

          用代码来说就是，设计一个res= INT32_MIN用来存储最终结果，count=0实时记录当前连续字串的和。若加上nums[i]后countpublic: int maxSubArray(vector int result = INT32_MIN; int count = 0; for (int i = 0; i