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

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

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.length && j < s.length){
            if(s[j] >= g[i]){
                num++;
                j++;
                i++;
            }else{
                j++;
            }
        }
        return num;
    }
}

LeetCode 376. 摆动序列

分析

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

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

代码

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.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]);
    }
}

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 < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count); // 取区间累计的最大值(相当于不断确定最大子序终止位置)
            if (count <= 0){
                count = 0; // 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和
            }
        }
       return sum;
    }
}

总结

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

热门相关:地球第一剑   天启预报   寂静王冠   大神你人设崩了   天启预报