贪心算法part01 算法

贪心算法part01 算法

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

1.leetcode455.分发饼干

https://leetcode.cn/problems/assign-cookies/description/

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //因为是尽可能满足多的孩子
        Arrays.sort(g);
        Arrays.sort(s);
        //计数器
        int count=0;
        int startIndex=0;
        for(int i=0;i<s.length;i++){//饼干
            if(startIndex<=g.length-1&&g[startIndex]<=s[i]){//孩子
             count++;
             startIndex++;//孩子位置  
            }
            //没有进入if，那就是孩子位置没有变，而饼干将要向后一个位置
        }
        return count;
    }
}

2.leetcode376. 摆动序列

https://leetcode.cn/problems/wiggle-subsequence/description/

class Solution {
    public int wiggleMaxLength(int[] nums) {
        //画图，上下坡
        //如果数组长度是0个或者1个，那么直接返回数组长度
        if(nums.length<=1){
            return nums.length;
        }
        //当前差值
        int curDiff=0;
        //上一个差值
        int preDiff=0;
        //累加结果
        int count=1;//最后一个已经包括
        for(int i=1;i<nums.length;i++){//因为下标为1的元素衔接上一个和当前的差值
            //得到当前差值
            curDiff=nums[i]-nums[i-1];
            //如果当前差值和上一个差值为一正一负的话
            //等于0的情况表示初始时的preDiff
            if((curDiff>0&&preDiff<=0)||(curDiff<0&&preDiff>=0)){
                count++;
                preDiff=curDiff;
            }
        }
        return count;
    }
}

3.leetcode53. 最大子序和

https://leetcode.cn/problems/maximum-subarray/description/

class Solution {
    public int maxSubArray(int[] nums) {
        //找出一个具有最大和的连续子数组
        //连续
        //最大，那就每次都是最大的
        //用来保存结果，每次都是最大的
        int result=Integer.MIN_VALUE;
        //用来计数
        int sum=0;
        for(int i=0;i<nums.length;i++){
            //进行累加
            sum+=nums[i];
            if(result<sum){
                result=sum;
            }
            //当让整合为负数的时候，我们就舍弃掉重新出发
            if(sum<0){
                sum=0;
            }
        }
        return result;
    }
}