当前位置:   article > 正文

Day34 贪心 part03

Day34 贪心 part03

Day34 贪心 part03

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

我的思路:
又需要考虑最大值,首先将数组进行排序,将数字中所有<0的全部取反,如果此时k还要剩余,剩余偶数的话,可以反复对数组其中一个数字取反,最终数组仍然不变;剩余奇数,只需要再排序,对第一个元素取反一次

解答:

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int i = 0;
        while(k > 0 && i < nums.length && nums[i] < 0) {
            nums[i] = -nums[i];
            k --;
            i ++;
        }
        if(k%2 != 0) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        return Arrays.stream(nums).sum();
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

134. 加油站

我的思路:
没想到如何用贪心思想
对着题解理解,只要gas比cost大,就能找到起始位置;而这个起始位置,只要索引 i 位置上gas < cost,就不断后移更新

解答:

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int cur = 0;
        int startIndex = 0;
        for(int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            cur += diff;
            if(cur < 0) {
                cur = 0;
                startIndex = i + 1;
            }
        }
        if(total < 0) {
            return -1;
        }
        return startIndex;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

135. 分发糖果

我的思路:
理解了题解
首先初始化candy为1,先从前往后遍历,如果rating后一个值大于前一个值,candy数 + 1;接着从后往前遍历,如果rating大于后一个值,比较自身candy数和后一个candy + 1,取较大值

解答:

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candy = new int[n];
        Arrays.fill(candy, 1);
        for(int i = 1; i < n; i ++) {
            if(ratings[i] > ratings[i-1]) {
                candy[i] = candy[i-1] + 1;
            }
        }
        for(int i = n-2; i >= 0; i--) {
            if(ratings[i] > ratings[i+1]) {
                candy[i] = Math.max(candy[i], candy[i+1] + 1);
            }
        }
        int sum = Arrays.stream(candy).sum();
        return sum;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/315440
推荐阅读
相关标签
  

闽ICP备14008679号