代码随想录|贪心3

1005

这道题的思想是：
对数组进行排序，如果前k个数全部小于0，直接反转，如果k有剩余，则反转最小值

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
//排序
        Arrays.sort(nums);
        int count = k;
//前k个是否全为负数
        for(int i = 0 ; i < nums.length; i++){
            if(nums[i] <= 0 && count > 0){
                nums[i] = - nums[i];
                count--;
            }
        }
//进行第二次排序
        Arrays.sort(nums);
        if(count > 0){
//若有剩余，则剩余一直反转最小值
            while(count-- > 0){
                nums[0] = -nums[0];
            }
        }
        int sum = 0;
        for(int i = 0 ; i< nums.length;i++)
            sum = sum + nums[i];
        return sum;
    }
}

134.https://leetcode.cn/problems/gas-station/

这道题的思想是，当前累加gas[i] - cost[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行，同时更新curSum为0，重新开始记录和值。当遍历gas[i] - cost[i]的和小于0时，一定不能实现跑完，直接返回-1.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] sub = new int[gas.length];
//记录当前净补油累加和
        int subSum = 0;
//记录总净补油累加和
        int index = 0;
        int totalSum = 0;
        for(int i = 0 ; i < gas.length; i++){
            sub[i] = gas[i] - cost[i];
            subSum = subSum + sub[i];
            totalSum = totalSum + sub[i];
//当前净补油累加和<0,从下一个索引重新计数
            if(subSum < 0){
                index = i + 1;
                subSum = 0;
            }
        }
//总净补油累加和小于0，则一定不能
        if(totalSum < 0){
            return -1;
        }else{
            return index;
        } 
    }
}

135. 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

这道题的思想是：
从左往右比，比左边大的 ——》 左边值 + 1；比左边小的 ——》1；

从右往左比，比右边大的 ——》 右边值 + 1；比右边小的 ——》1；

最终的数组 ——》 max（左数组，右数组）

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        left[0] = 1;
        int[] right = new int[ratings.length];
        right[right.length - 1] = 1;
        for(int i = 1 ; i < ratings.length;i++){
            if(ratings[i] > ratings[i-1]){
                left[i] = left[i - 1] + 1;
            }else{
                left[i] = 1;
            }
        }
        for(int i = right.length - 2; i >= 0 ; i--){
            if(ratings[i] > ratings[i + 1]){
                right[i] = right[i+1] + 1;
            }else{
                right[i] = 1;
            }
        }
        int[] arr = new int[ratings.length];
        int sum = 0;
        for(int i = 0; i < arr.length; i++){
            arr[i] = Math.max(left[i],right[i]);
            sum = sum + arr[i];
        }
        return sum;
    }
}