代码随想录训练营第31天|LeetCode 455.分发饼干、 376. 摆动序列、53. 最大子序和

参考

代码随想录

什么是贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 。
举个例子，例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？指定每次拿最大的，最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

题目一：LeetCode 455.分发饼干

对胃口值和饼干尺寸都进行排序，然后最大的饼干优先满足胃口值较大的。这里求解思想是贪心，实现过程用的是双指针，一个遍历g，一个遍历s。

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

题目二：LeetCode 376.摆动序列

题目中说子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。但其实不必删除元素，因为只需要求序列长度而不需要直到具体的序列。代码随想录中给出的方法是求极值，但是这样会涉及到边界的处理，最左边和做右边的两个点不好处理。进一步，可以转化为求区间，一个区间对应着两个点，中间点是两个区间共用的，因此最后的子序列长度等于区间数再加1，这里的区间是递增和递减交替出现的，如下图所示：

求递增和递减区间就可以不用关注边界点了。用两个变量来记录上一个区间和当前区间的变化情况（包括递增和递减，注意这里只求递增和递减区间，保持不变的情况不统计），这里用-1表示递减，1表示递增，0表示保持不变，这样只要上一个区间的状态的当前不同就认为是两个区间。这样做可以不用关注边界。
总结来说，就是把原来的小区间按照其数值的变化情况重新划分区间，划分为三大类：递增，递减，非增非减（即保持不变），但是只统计递增和递减区间。
代码实现如下：

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int len = 0;
        int pre = 0;  //用0标记区间内数值保持不变的情况，这种区间不统计
        int cur;
        for(int i = 1;i < nums.size(); i++){
            int diff = nums[i] - nums[i-1];
            if(diff > 0) cur = 1;  //用1标记递增
            else if(diff < 0) cur = -1;  //用-1标记递减
            else cur = 0;   //用0标记数值保持不变
            if(cur != 0 && cur != pre){  //如果两个区间增减不同就进行统计
                len++;
                pre = cur;
            }
        }
        return len+1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

题目三：LeetCode 53.最大子序和

可以用暴力求解，但是会超时。两层for循环，i遍历外层，j遍历内层，组成的区间为[i,j]。代码如下：

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

贪心解法

贪心贪的是哪里呢？

如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

从代码角度上来讲：遍历nums，从头开始用sum累积，如果sum一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积sum了，因为已经变为负数的count，只会拖累总和。

这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
代码实现如下：

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

注意，每次加上nums[i]后应该更新max的值，即使max当前可能为负数，因为可能整个数组都是负数，那么最大值也只能是负数。