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

• 博主简介：努力学习和进步中的的22级计科生
• 博主主页： @Yaoyao2024
• 每日一句: “ 路虽远，行则将至。事虽难，做则可成。”

前言：贪心算法

参考和学习：代码随想录

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

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

• 数学归纳
• 反证

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

一、455.分发饼干

🌷思路：

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

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

🌻步骤

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

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

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

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

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

🏄🏻‍♀️完整代码

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

二、376. 摆动序列

力扣题目链接

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

🏄🏻‍♀️完整代码

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

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

三、53. 最大子序和

题目链接

🌷思路：

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

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

那再说回这道题的思路：

1

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

用代码来说就是，设计一个res= INT32_MIN用来存储最终结果，count=0实时记录当前连续字串的和。若加上nums[i]后count<0，那么放弃当前字串，令count = 0，以nums[i+1]开始重新计算连续字串长度。

这样严谨吗？没有数学证明确实不好说，但是你完全找不到反例，因此这个算法就是OK的。贪心就是比较魔幻。我一开始对这个代码思路提出下面的反例：加上-3后，前面为负，从5元素开始计算，结果肯定是5；但是明显结果是[4,-3,5,-1,1]更大；我忽略了一点是，-2在最开始就不可能做连续字串的开头！

❌错误代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++){
            count += nums[i];
            if(count < 0){
                count = 0;
            }else{
                result = max(result, count);
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

错误原因：忽略了以下情况。也就是说，result = max(result, count);必须在count += nums[i];立马进行比较进行，它是不存在有调节的！！

✅正确代码：

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