力扣爆刷第147天之贪心算法五连刷（跳跃、发糖果、加油站）

力扣爆刷第147天之贪心算法五连刷（跳跃、发糖果、加油站）

一、45. 跳跃游戏 II

题目链接：https://leetcode.cn/problems/jump-game-ii/description/
思路：本题求的是跳跃的最少次数，要想求最少次数当然是在每一个跳跃区间内寻找最远的下一跳，这样每次走完当前区间，要进行下一跳时，选择距离最远的选择进行跳跃，并且记录下跳跃次数，本质上是不断更新最远区间的过程，只不过更新时选择最远的进行更新。

class Solution {
    public int jump(int[] nums) {
        int cur = 0, temp = 0, max = 0, count = 0;
        for(int i = 0; i < nums.length; i++) {
            if(cur >= nums.length - 1) return count;
            temp = i + nums[i];
            max = Math.max(max, temp);
            if(cur == i) {
                cur = max;
                count++;
            }
        }
        return count;
    }
}

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

题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
思路：本题本质上是让把负数的部分先翻转，来消耗K，如果k没有被消耗完，就会出现两种情况，要么全为负数，要么负数消耗完了，如果全为负数，则只需要把剩余的k用在最后一个元素上，如果是负数消耗完了，则需要以0为界限，相邻的两个数的绝对值的最小值，来作为消耗值。由此即可解题。

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int i = 0, len = nums.length;
        for(; i < len; i++) {
            if(k == 0 || nums[i] >= 0) break;
            nums[i] = -nums[i];
            k--;
        }
        if(k > 0) {
            if(i < len) {
                if(i - 1 > 0 && nums[i-1] < nums[i]) i = i-1;
                nums[i] = k % 2 == 0 ? nums[i] : -nums[i];
            }else{
                nums[len-1] = k % 2 == 0 ? nums[len-1] : -nums[len-1];
            }
        }
        int sum = 0;
        for(int t : nums) {
            sum += t;
        }
        return sum;
    }
}

三、134. 加油站

题目链接：https://leetcode.cn/problems/gas-station/description/
思路：加油站问题其实就是油和消耗的问题，只需要认识到，如果油的总和大于等于消耗总和，是一定可以走完全场的，如果油的总和小于消耗的总和，是一定走不完全场的。
那么要寻找起点，只需要从第一个油量大于消耗量的点开始，向后累加差值，只需要差值小于0，就从下一个位置开始，这样只要遍历结束，油的总量还大于消耗，就一定记录了开始位置。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int cur = 0, total = 0, start = 0;
        for(int i = 0; i < gas.length; i++) {
            cur += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if(cur < 0) {
                start = i+1;
                cur = 0;
            }
        }
        if(total < 0) return -1;
        return start;
    }
}

四、135. 分发糖果

题目链接：https://leetcode.cn/problems/candy/
思路：分发糖果，要求如果一个数比左右的数都要大，那么他获得的糖果数量应该是大于左右的，对于这种双边问题，我们可以一条边一条边的处理，先从左往右寻找右值大于左值的，再从右往左，寻找左值大于右值的，第一次但凡出现符合条件的糖果数量+1，第二次，不仅要出现还得是糖果数不符合条件时才加，为了避免多用糖果。

class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        if(len == 1) return 1;
        int[] nums = new int[len];
        for(int i = 1; i < len; i++) {
            if(ratings[i] > ratings[i-1]) nums[i] = nums[i-1]+1;
        }
        for(int i = len-2; i >= 0; i--) {
            if(ratings[i] > ratings[i+1] && nums[i] <= nums[i+1]) nums[i] = nums[i+1]+1; 
        }
        int sum = len;
        for(int t : nums) sum += t;
        return sum;
    }
}

五、860. 柠檬水找零

题目链接：https://leetcode.cn/problems/lemonade-change/description/
思路：遍历应对，枚举所有的实例，分条判断即可。

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int a = 0, b = 0, c = 0;
        for(int i : bills) {
            if (i == 5) {
                a++;
            } else if(i == 10) {
                a--;
                b++;
            } else {
                c++;
                if(b > 0) {
                    b--;
                    a -= 1;
                }else{
                    a -= 3;
                }
            }
            if(a < 0) return false;
        }
        return true;
    }
}