代码随想录第三十四天｜贪心算法

今天继续贪心算法，重点是学习贪心算法的思维

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

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        int i = 0;
        while(k>0 && i < n && nums[i] < 0){
            nums[i] = - nums[i];
            k--;
            i++;
        }
        
        if(k > 0 ){
            Arrays.sort(nums);
            if ((nums[0] != 0) && (k % 2 != 0)) {
                nums[0] = -nums[0];
            }
        }

        return Arrays.stream(nums).sum();




    }

尽量把所有负数都反转，次数过多的话就尽量把最小的数字变为负数

134. 加油站

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int m = cost.length;

        if(Arrays.stream(gas).sum()< Arrays.stream(cost).sum()){
            return -1;
        }

        int cur = 0;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i< n; i++){
            int rest = gas[i] - cost[i];
            cur += rest;
            if(cur < min){
                min = cur;
            }
        }
        if(cur < 0){
            return -1;
        }
        if(min >= 0){
            return 0;
        }

        for(int i=n - 1; i>=0; i--){
            int rest = gas[i] - cost[i];
            min += rest;
            if(min >= 0){
                return i;
            }
        }
        return -1;

    }
}

看是否车子所存的油能从i 开到 i+1

135. 分发糖果

class Solution {
    public int candy(int[] ratings) {
        int[] candyVec = new int[ratings.length];
        candyVec[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candyVec[i] = candyVec[i - 1] + 1;
            } else {
                candyVec[i] = 1;
            }
        }

        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
            }
        }

        int ans = 0;
        for (int s : candyVec) {
            ans += s;
        }
        return ans;
    }
}

左右两边都需要进行遍历对比

今天的困难题比较让人没有思路