代码随想录day34

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

题目

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

思路

我的思路很简单，先排序，那么它就有可能是从负数到正数的排列，它取反的话，先把负数都给取完，然后再轮到小的正数(一定是最小的)

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--;
            }
        }
        if(k > 0){
   
            Arrays.sort(nums);
            while(k > 0){
   
                nums[0] = -nums[0];
                k--;
            }
        }
        int res = 0;
        for(int i = 0;i < nums.length;i++){
   
            res += nums[i];
        }
        return res;

    }
}

 

  
 

加油站

思路

暴力超时，气死我了

一次遍历，重要的思路

• 车从i站能开到i+1
• 所有站里的油总量要>=车子的总耗油量

车从i站能开到i+1。

所有站里的油总量要>=车子的总耗油量。

那么，假设从编号为0站开始，一直到k站都正常，在开往k+1站时车子没油了。这时，应该将起点设置为k+1站。

问题1: 为什么应该将起始站点设为k+1？

因为k->k+1站耗油太大，0->k站剩余油量都是不为负的，每减少一站，就少了一些剩余油量。所以如果从k前面的站点作为起始站，剩余油量不可能冲过k+1站。
问题2: 为什么如果k+1->end全部可以正常通行，且rest>=0就可以说明车子从k+1站点出发可以开完全程？

因为，起始点将当前路径分为A、B两部分。其中，必然有(1)A部分剩余油量<0。(2)B部分剩余油量>0。

所以，无论多少个站，都可以抽象为两个站点（A、B）。(1)从B站加满油出发，(2)开往A站，车加油，(3)再开回B站的过程。

重点：B剩余的油>=A缺少的总油。必然可以推出，B剩余的油>=A站点的每个子站点缺少的油。

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

    }
}

 

  
 

135. 分发糖果

思路

重点在相邻
我们需要判断左边和右边最大的值

class Solution {
   
    public int candy(int[] ratings) {
   
        int [] count = new int[ratings.length];
        Arrays.fill(count,1);
        // 从前往后遍历
        for(int i = 1;i < ratings.length;i++){
   
            if(ratings[i] > ratings[i - 1]){
   
                count[i] = count[i -1] +1;
            }
        }
        // 从后往前遍历
        int res = 0;
        for(int i = ratings.length - 2;i>=0;i--){
   
            if(ratings[i + 1] < ratings[i]){
   
                count[i] = Math.max(count[i],count[i + 1] + 1);
            }
        }
        for(int num : count){
   
            res += num;
        }
        return res;
    }
}

 

  
 

转载：https://blog.csdn.net/weixin_43821876/article/details/128613931