贪心算法

leetcode455 分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //先对孩子的胃口和饼干尺寸进行排序
        Arrays.sort(g);
        Arrays.sort(s);
        int i=0;
        int j=0;
        //任意一个数组遍历结束就结束循环
        while(i<g.length&&j<s.length){
            //如果当前饼干能够满足则跳到下一个孩子
            if(s[j]>=g[i]){
                i++;
            }
            //不管当前饼干能否满足，都要跳到下一块饼干
            j++;
        }
        return i;
    }
}

leetcode53 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        //如果sum>0，则对后面子序列求和有帮助，否则重新寻找序列头
        int sum = 0;
        for(int i:nums){
            if(sum>0){
                sum +=i;
            }
            else{
                sum = i;
            }
            res = Math.max(res,sum);
        }
        return res;
    }
}

leetcode 摆动序列

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int up=1;
        int down=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]>nums[i-1]){
                up = down+1;
            }else if(nums[i]<nums[i-1]){
                down = up+1;
            }
        }
        return nums.length<2? nums.length:Math.max(up,down);
    }
}

leetcode45 跳跃游戏

class Solution {
    public int jump(int[] nums) {
        if(nums.length<2){
            return 0;
        }
        int res = 0;
        //每次能跳的最远处
        int end = 0;
        int posMax = 0;
        for(int i =0;i<nums.length;i++){
            posMax = Math.max(posMax,i+nums[i]);
            //当循环到最远处时，更新下次的边界
            if(i==end){
                res++;
                end = posMax;
            }
            //能跳到最远处时，跳出循环
            if(end>=nums.length-1){
                return res; 
            }
        }
        return res;
    }
}