补博客 5 ( 1 )

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

public int largestSumAfterKNegations(int[] nums, int k) {
        if (nums.length == 1) {
            return k % 2 == 1 ? -nums[0] : nums[0];
        }
        Arrays.sort(nums);
        int tmp = k;
        int end = 0;
        for (int i = 0; i < nums.length && nums[i] < 0; i++) {
            nums[i] = -nums[i];
            k--;
            end = i;
        }
        int minAbs = 0;
        if (nums.length == end + 1) {
            minAbs = end;
        } else {
            minAbs = nums[end] < nums[end + 1] ? end : end + 1;
        }
        nums[minAbs] = k % 2 == 1 ? -nums[minAbs] : nums[minAbs];
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

134. 加油站

public int canCompleteCircuit(int[] gas, int[] cost) {

        int curTotal = 0, total = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            curTotal += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if (curTotal < 0) {
                curTotal = 0;
                start = i + 1;
            }
        }
        return total < 0 ? -1 : start;
    }

135. 分发糖果

public int candy(int[] ratings) {
        int num = ratings.length;
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        for (int i = 0; i < ratings.length - 1; i++) {
            if (ratings[i] < ratings[i + 1]) {
                candies[i + 1] = candies[i] + 1;
            }
        }
        for (int i = ratings.length - 1; i > 0; i--) {
            if ((ratings[i - 1] > ratings[i]) && (candies[i - 1] <= candies[i])) {
                candies[i - 1] = candies[i] + 1;
            }
        }
        int sum = 0;
        for (int candy : candies) {
            sum += candy;
        }
        return sum;
    }