代码随想录day27 贪心1

理论基础

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

怎么判断能不能用贪心：举反例。举的出来则不用，举不出来则用贪心。

贪心算法一般分为如下四步：最重要的是想清楚局部最优，能否推倒出全局最优。

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

455.分发饼干

思路：1.首先排序

2.遍历饼干，从小到大，index记录到第几个孩子。

3.也可以遍历孩子，从大到小，index记录第几个饼干

注意：

另外两种组合也可以写，只是要多加几个变量来记录和控制。

代码：

1.从前往后，遍历饼干，即先满足小胃口

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index=0;
        for(int i=0;i<s.size();i++){
            if(index<g.size()&&g[index]<=s[i])
            index++;
        }
        return index;
    }
};

2.从前往后，遍历孩子（麻烦）

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index=0,num=0,time=0;
        for(int i=0;i<g.size()&&(time<=s.size()||time<=g.size());i++){
            time++;
            if(index<s.size()&&s[index++]>=g[i]){
                num++;
                continue;
            }
            i--;
        }
        return num;
    }
};

3.从后往前，遍历孩子.即先满足大胃口

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int num=0,index=s.size()-1;
        for(int i=g.size()-1;i>=0;i--){
            if(index>=0&&g[i]<=s[index]){
                index--;
                num++;
            }
        }
        return num;
    }
};

376. 摆动序列

思路1：1.因为题目说了可以增删元素，所以就在增删的基础上进行搜索。

2.只要是摆动的，就一定是上下上下或下上下上，所以一个波谷就是一个元素。

3.选择curdiff和prediff进行值的更新。res记录

4.考虑几种情况：

        1.正常，全是波峰波谷：prediff<0&&curdiff>0||prediff>0&&curdiff<0

        2.两端低或高中间平：1-2-2-2-1,这时候选择跳过前面的两个2，只记录最后一个2，则条件需要为：prediff<=0&&curdiff>0||prediff>=0&&curdiff<0。（只看最后一个2所处的左右状况就可以写出来）。

        3.上坡中间有多个平坡：1-2-2-2-3-4-4-5。这个时候，prefix的更新时间就必须要在最后一个平坡元素确认的时候才更新，以及正常坡的时候更新。

注意：res初始值为1。prediff可以由curdiff继承来。

代码：

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
       int curdiff=0;
       int prediff=0;
       int res=1;
       for(int i=0;i<nums.size()-1;i++){
        curdiff=nums[i+1]-nums[i];
        if(prediff<=0&&curdiff>0||prediff>=0&&curdiff<0){
            res++;
            prediff=curdiff;
        }
       }
       return res;
    }
};

思路2：动态规划。等学到动态规划再回来写

思路3：在思路2基础上，可以用两棵线段树来维护区间的最大值。

53. 最大子序和

思路：首先想法是暴力，从i开始，里面定义一个count，然后从j开始循环到最后。得到最大值。这样的代码超时了。

然后考虑贪心：局部为正且大即可

我需要的是不断求取为正且大的区间和，所以只要这段区间和的值小于0，我就让区间和count=0；

如何记录最大的？res，如果res<count ;则赋值。

注意：每次count都+=num，只是改变count的值。

思路是：不能让连续和为负数的时候再加上元素，而不是！不能让连续和加上负数

代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res=INT_MIN;
        int count=0;
        for(int i=0;i<nums.size();i++){
            count+=nums[i];
            if(count>res){
                res=count;
            }
            if(count<0)count=0;
        }
        return res;
    }
};