代码随想录算法训练营第三十三天 | K 次取反后最大化的数组和

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

leetcode
文档题解
视频题解

决策问题，暴力回溯，等着超时。

class Solution {
    int max = Integer.MIN_VALUE;
    public int largestSumAfterKNegations(int[] nums, int k) {
        backtrace(nums, k);
        return max;
    }
    public void backtrace(int[] nums, int k) {
        if (k == 0) {
            int sum = 0;
            for (int n: nums) {
                sum += n;
            }
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            nums[i] = -nums[i];
            backtrace(nums, k - 1);
            nums[i] = -nums[i];
        }
    }
}

贪心法，思路是尽可能的反转负数，如果还有剩余的反转次数，再反转最小的正数。

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 先排序，可以按绝对值排序，后面反转最小的正数时更方便
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (k == 0) break;
            if (nums[i] < 0) {
                // 先将负数变正
                nums[i] = -nums[i];
                k--;
            } else {
                // 正数和 0 就不管了
                break;
            }
        }

        // 如果还有次数，就反复反转最小的正数
        if (k > 0) {
            // 再排一次序，可以优化
            Arrays.sort(nums);

            // 如果剩余的 k 为奇数，那就将最小的正数变为负数，这样代价最小，和最大
            if (k % 2 != 0) {
                nums[0] = -nums[0];
            }
        }

        int sum = 0;
        for (int n: nums) {
            sum += n;
        }

        return sum;
    }
}

134. 加油站

leetcode
文档题解
视频题解

模拟，暴力搜索，超时。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int rest = gas[i] - cost[i];
            int j = (i + 1) % n;
            while (rest > 0 && j != i) {
                rest += gas[j] - cost[j];
                j = (j + 1) % n;
            }
            // 有剩余油，或刚好回到起点
            if (rest >= 0 && j == i) return i;
        }
        return -1;
    }
}

时间复杂度：O(n^2)
空间复杂度：O(1)