欢迎关注个人公众号：爱喝可可牛奶

LeetCode算法训练-贪心算法 455.分发饼干 376. 摆动序列 53. 最大子序和

前置知识

贪心算法核心是找局部最优解，通过局部最优推导出全局最优

LeetCode 455. 分发饼干

分析

要求：把饼干分给孩子，并返回分了多少个孩子

局部最优：小饼干分给胃口小的

代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0, j = 0;
        int num = 0;
        while(i = g[i]){
                num++;
                j++;
                i++;
            }else{
                j++;
            }
        }
        return num;
    }
}

LeetCode 376. 摆动序列

分析

返回 nums 中作为 摆动序列 的 最长子序列的长度

对于我们当前考虑的这个数，要么是作为山峰（即nums[i] > nums[i-1]），要么是作为山谷（即nums[i]

代码

class Solution {
    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[i]){
                    // i 是波谷
                    dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
                }
                if (nums[j] 

LeetCode 53. 最大子数组和

分析

局部最优： 遍历到当前元素cur时，和为正数，继续遍历； 如果遍历到当前元素后和为负数，从后一个元素重新开始遍历

代码

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 

总结

贪心算法没有银弹，如果找出局部最优并可以推出全局最优，就是贪心，关键是如何去找局部最优