Day 31 | 贪心算法 理论基础 、455.分发饼干 、 376. 摆动序列 、 53. 最大子序和

理论基础

文章讲解

455.分发饼干

题目
文章讲解
视频讲解

思路:从小饼干开始喂小胃口

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

376. 摆动序列

题目
文章讲解
视频讲解

思路:初始时preDiff可能为0

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. 最大子序和

题目
文章讲解
视频讲解

思路:在处理负数的情况下,对于任何负数,如果将其加入当前的和中,都会导致和变小。因此,如果当前的和已经为负数,那么加上任何负数都不会使和变大,因此应该将当前的 count 重置为0

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;
    }
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>