1005.K次取反后最大化的數(shù)組和

先將數(shù)組排序，依次將負數(shù)變?yōu)檎龜?shù)，如果到了末尾，k還是大于0，那么需要判斷k的奇偶，如果是奇數(shù)，那么將數(shù)組重新排序，開頭元素取反，如果是偶數(shù)不需要操作（注意同一個元素可以多次取反，所以只需要判斷最后k的奇偶即可，不需要遍歷）

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        //先將負數(shù)處理完
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            } else {
                break;
            }
        }
        //如果k有剩余，并且k為奇數(shù)
        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，記錄經(jīng)過的加油站所剩余的油量，如果小于0，那么從下一個加油站重新開始，如果總和為負數(shù)，說明不存在合適的起始位置

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0; //經(jīng)過的剩余油量總和
        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循環(huán)中計算，可以省去一個for循環(huán)
            if (curSum < 0) {
                start = i + 1;
                curSum = 0;
            }
        }
        if (totalSum < 0) {
            return -1;
        }
        return start;
    }
}

135. 分發(fā)糖果

135. 分發(fā)糖果 - 力扣（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;
    }
}