贪心算法

刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
455、分发饼干

class Solution {
    public int count;
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        count = 0;
        int indexS = 0;
        int indexG = 0;
        while(indexS < s.length && indexG < g.length){
            if(s[indexS] >= g[indexG]){
                count++;
                indexG++;
                indexS++;
            }else{
                indexS++;
            }
        }
        return count;
    }
}

376、摆动序列

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1){
            return nums.length;
        }
        int pre = 0;
        int cur = 0;
        int count = 1;
        for(int i = 1; i < nums.length; i++){
            cur = nums[i] - nums[i - 1];
            if((cur > 0 && pre <= 0) || (cur < 0 && pre >= 0)){
                count++;
                pre = cur;
            }        
        }
        return count;
    }
}

53、最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int count = 0;
        int sum = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count);
            if(count <= 0){
                count = 0;
            }
        }
        return sum;
    }
}

122、买卖股票的最佳时机 II

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] > prices[i - 1]){
                max += prices[i] - prices[i - 1];
            }
        }
        return max;
    }
}

55、跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1){
            return true;
        }
        int coverMax = 0;
        for(int i = 0; i <= coverMax; i++){//防止中途就出现覆盖范围中断
            coverMax = Math.max(coverMax, i + nums[i]);
            if(coverMax >= nums.length - 1){
                return true;
            }
        }
        return false;
    }
}

45、跳跃游戏 II

class Solution {
    public int jump(int[] nums) {
        int count = 0;
        if(nums.length == 1){
            return count;
        }
        // 当前覆盖范围
        int coverMax = 0;
        // 最大覆盖范围
        int maxCover = 0;
        for(int i = 0; i < nums.length; i++){
            // 更新在当前覆盖范围内的最大覆盖范围（下一步可以跳到的最大范围）
            maxCover = Math.max(nums[i] + i, maxCover);
            // 再跳一步就可以到达
            if(maxCover >= nums.length - 1){
                count++;
                break;
            }
            // 到达当前覆盖范围最大值，需要下一跳
            if(i == coverMax){
                count++;
                coverMax = maxCover;
            }
        }
        return count;
    }
}

1005、K 次取反后最大化的数组和

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int index = 0;
        for(int i = 0; i < k; i++){
            if(i < nums.length - 1 && nums[index] < 0){
                nums[index] = -nums[index];
                if(nums[index] >= Math.abs(nums[index + 1])){
                    index++;
                }
                continue;
            }
            nums[index] = -nums[index];
        }
        int sum = 0;
        for(int j = 0; j < nums.length; j++){
            sum += nums[j];
        }
        return sum;
    }
}

134、加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] arr = new int[gas.length];
        int sum = 0;
        int curSum = 0;
        int index = 0;
        for(int i = 0; i < arr.length; i++){
            arr[i] = gas[i] - cost[i];
            sum += arr[i];
            curSum += arr[i];
            if(curSum < 0){
                index = (i + 1)%arr.length;
                curSum = 0;
            }
        }
        if(sum >= 0){
            return index;
        }else{
            return -1;
        }
    }
}

135、分发糖果

class Solution {
    public int candy(int[] ratings) {
       // 最少糖果数目
       int[] arrResult = new int[ratings.length];
       arrResult[0] = 1;
        for(int i = 1; i < ratings.length; i++){
            arrResult[i] = ratings[i] > ratings[i - 1] ? arrResult[i - 1] + 1 : 1;
        }
        for(int i = ratings.length - 2; i >= 0; i--){
            if(ratings[i] > ratings[i + 1]){
                arrResult[i] =  Math.max(arrResult[i],arrResult[i + 1] + 1);
            } 
        }
        int sum = 0;
        for(int j = 0; j < arrResult.length; j++){
            sum += arrResult[j];
        }
        return sum;
    }
}

860、柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        if(bills[0] != 5){
            return fal