代码随想录训练营第二十七天| 贪心理论基础 455.分发饼干 376. 摆动序列 53. 最大子序和

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

今天的内容比较简单 简单了解贪心是通过局部最优解反推全局最优解（有经验成分）

455.分发饼干

题目链接：455. 分发饼干 - 力扣（LeetCode）

讲解链接：代码随想录

 Java代码：

class Solution{
    //思路1 优先考虑饼干 小饼干先喂饱小胃口
    public int findContentChildren(int[] g, int[] s){
        Arrays.sort(s);
        Arrays.sort(g);
        int start = 0, count = 0;
        for(int i = 0; i < s.length && start < g.length; i++){
            if(s[i] >= g[start]){
                start++;
                count++;
            }
        }
        return count;
    }
}

 376. 摆动序列

题目链接：376. 摆动序列 - 力扣（LeetCode）

讲解链接：代码随想录

感觉这道题我只明白了摆动 但是对于三个特殊情况我想不到 还是得慢慢来思考

1. 情况一：上下坡中有平坡
2. 情况二：数组首尾两端
3. 情况三：单调坡中有平坡

Java代码： 

class Solution{
    public int wiggleMaxLength(int[] nums){
        if(nums.length <= 1) return nums.length;
        //当前差值
        int curdiff = 0;
        //上一个差值
        int prediff = 0;
        int count = 1;
        for(int i = 1; i < nums.length; i++){
            //得到当前差值
            curdiff = nums[i] - nums[i - 1];
            //如果当前差值和上一个差值为一正一负
            //等于0 的情况 表示初始时的prediff
            if((curdiff > 0 && prediff <= 0) || (curdiff < 0 && prediff >= 0)){
                count++;
                prediff = curdiff;
            }
        }
        return count;
    }
}

 53. 最大子序和

题目链接：53. 最大子数组和 - 力扣（LeetCode）

讲解链接：代码随想录

这题可以暴力直接过 有可能TLE 还是看看贪心 这道题也能用前缀和 或者 dp做

class Solution{
    public int maxSubArray(int[] nums){
        if(nums.length == 1) return nums[0];
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count);//取出区间累计最大值
            if(count <= 0){
                count = 0;//相当于重置最大子序起始位置
                //因为遇到负数一定拉低总和
            }
        }
        return sum;
    }
}

努力学习 找工作