代码随想录-算法训练营day31【贪心算法01：理论基础、分发饼干、摆动序列、最大子序和】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第八章 贪心算法 part01

● 理论基础 
● 455.分发饼干 
● 376. 摆动序列 
● 53. 最大子序和 

贪心算法其实就是没有什么规律可言，所以大家了解贪心算法 就了解它没有规律的本质就够了。 

不用花心思去研究其规律， 没有思路就立刻看题解。

基本贪心的题目 有两个极端，要不就是特简单，要不就是死活想不出来。  

学完贪心之后再去看动态规划，就会了解贪心和动规的区别。

详细布置 

理论基础 

https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html  

455.分发饼干  

https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html  

376. 摆动序列  

https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html  

53. 最大子序和  

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html  

往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任务以及具体安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任务以及具体安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ  
●day 29 任务以及具体安排：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3 
●day 30 任务以及具体安排：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR

目录

理论基础

0455_分发饼干

0376_摆动序列

0053_最大子序和

理论基础

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

0455_分发饼干

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;

import java.util.Arrays;

public class _0455_分发饼干 {
}

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

class Solution0455_2 {
    //思路2：优先考虑胃口，先喂饱大胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;
        //遍历胃口
        for (int index = g.length - 1; index >= 0; index--) {
            if (start >= 0 && g[index] <= s[start]) {
                start--;
                count++;
            }
        }
        return count;
    }
}

0376_摆动序列

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;

public class _0376_摆动序列 {
}

class Solution0376 {
    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;
    }
}

class Solution0376_2 {//DP
    public int wiggleMaxLength(int[] nums) {
        // 0 i 作为波峰的最大长度
        // 1 i 作为波谷的最大长度
        int dp[][] = new int[nums.length][2];
        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.length; i++) {
            //i 自己可以成为波峰或者波谷
            dp[i][0] = dp[i][1] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[i]) {
                    // i 是波谷
                    dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
                }
                if (nums[j] < nums[i]) {
                    // i 是波峰
                    dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
                }
            }
        }
        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
    }
}

0053_最大子序和

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;

public class _0053_最大子序和 {
}

class Solution0053 {
    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;
    }
}

class Solution0053_2 {//DP方法
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        ans = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            ans = Math.max(dp[i], ans);
        }
        return ans;
    }
}