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

先将数组排序，依次将负数变为正数，如果到了末尾，k还是大于0，那么需要判断k的奇偶，如果是奇数，那么将数组重新排序，开头元素取反，如果是偶数不需要操作（注意同一个元素可以多次取反，所以只需要判断最后k的奇偶即可，不需要遍历）

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        //先将负数处理完
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            } else {
                break;
            }
        }
        //如果k有剩余，并且k为奇数
        if (k > 0 && k % 2 == 1) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        return sum;
    }
}

134. 加油站

134. 加油站 - 力扣（LeetCode）
本题先计算出在某个加油站往下一个加油站行驶后的剩余油量，定义一个curSum，记录经过的加油站所剩余的油量，如果小于0，那么从下一个加油站重新开始，如果总和为负数，说明不存在合适的起始位置

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0; //经过的剩余油量总和
        int totalSum = 0; //所有剩余油量和
        int start = 0; //起始位置
        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i]; //将totalSum在遍历的for循环中计算，可以省去一个for循环
            if (curSum < 0) {
                start = i + 1;
                curSum = 0;
            }
        }
        if (totalSum < 0) {
            return -1;
        }
        return start;
    }
}

135. 分发糖果

135. 分发糖果 - 力扣（LeetCode）
本题需要两个方向分开考虑，一是右边比左边大，二是左边比右边大，首先从左到右遍历，如果右边比左边大，那么右边就比左边大1，然后从右到左遍历，如果左边比右边大，那么左边就比右边大1，并且取两种情况的最大值，注意这里不能从左到右遍历

class Solution {
    public int candy(int[] ratings) {
        int[] result = new int[ratings.length];
        result[0] = 1;
        //从左到右遍历
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                result[i] = result[i - 1] + 1;
            } else {
                result[i] = 1;
            }
        }
        //从右到左遍历
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                result[i] = Math.max(result[i], result[i + 1] + 1);
            }  
        }
        //求和
        int sum = 0;
        for (int i : result) {
            sum += i;
        }
        return sum;
    }
}