算法训练营day33

一、K次取反后最大化的数组和

1. 贪心：尽可能将所有的负数转换为正数以达到整体最大值
2. 分情况，讨论k和负数数量的关系，0是否存在的问题
3. 模拟顾名思义，模拟题目的操作来解决问题(直接解决)，而不是靠技巧解决

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        //贪心 + 分情况讨论 + 模拟
        int n = nums.length, idx = 0;
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->nums[a]-nums[b]);
        boolean zero = false;
        for(int i = 0; i<n; i++){
            if(nums[i] < 0) q.add(i);
            if(nums[i] == 0) zero = true;
    //记录绝对值最小的值的索引
            if(Math.abs(nums[i]) < Math.abs(nums[idx])) idx = i;
        }
        if(k <= q.size()){
            //注意          该代码的执行顺序是从左到右，也就是先提取索引，再将索引抛出并取反数组对应值
            while(k-- > 0) nums[q.peek()] = -nums[q.poll()];
        }else{
            while(!q.isEmpty() && k-- > 0) nums[q.peek()] = -nums[q.poll()];
   //如果没有零并且剩余k的次数是奇数，那么就要将绝对值最小的值取反
            if(!zero && k % 2 != 0) nums[idx] = -nums[idx];
        }
        int ans = 0;
        for(int i : nums) ans += i;
        return ans;
    }
}

二、加油站

重点是发现暴力解法到底哪里浪费时间

1. 当前surplus < 0 时，设当前的索引为i，设[0,i]之间存在j，那么两个区间[0,j-1] , [j,i]有两种情况
   1. 前提 [0,j-1] + [j,i]的总和 < 0 且 都是从0开始遍历
   2. [0,j-1] > 0 ,[j,i] < 0  或者 [0,j-1] < 0 和 [j,i] > 0
2. 第一种情况，前面大于零，后面小于零，索引 从 0 -> 1时，大于零的值更少了，从索引1出发到i时一定 < 0，索引直接跳到 i+1判断即可
3. 第二种，会想在 [j-1,i]之间的索引选择一个，这里按照代码逻辑判断，前面的surplus < 0 会将index更新到j，如果[j-1,i-1] + i < 0的话就相当于第一种情况[j-1,i-1] > 0 和 [i] < 0，这里就不用赘述了，以免掉进技术的旋涡中

	class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int total_surplus = 0;
        int surplus = 0;
        int start = 0;
        
        for(int i = 0; i < n; i++){
            total_surplus += gas[i] - cost[i];
            surplus += gas[i] - cost[i];
            if(surplus < 0){
                surplus = 0;
                start = i + 1;
            }
        }
        return (total_surplus < 0) ? -1 : start;
    }
}

三、分发糖果

参考链接Candy - LeetCode

理解代码并不难，左规则能理解，现在开始深入剖析右规则，分情况讨论实现右规则时是否会对左规则产生影响

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }
}