当前位置:   article > 正文

【代码随想录训练营】Day34-贪心算法

【代码随想录训练营】Day34-贪心算法

代码随想录训练营 Day34

今日任务

1005.K次取反后最大化的数组和
134.加油站
135.分发糖果
语言:Java

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

链接:https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int sum = 0;
        int idx = 0; //用于记录要进行取负操作的下标
        //取负顺序
        //先对所有负数取负
        //如果处理完所有负数后k还不为0,就对绝对值最小的整数不断取负
        for(int i = 0; i < k; i++){
            if(i < nums.length - 1 && nums[idx] < 0){
                //如果排序后的数组开头有一堆负数,idx会一直加加
                nums[idx] = -nums[idx];
                //绝对值最小的元素只能在最大负数/最小正数处取得
                //idx最后会落到绝对值最小数处
                //不要忘记等于号,否则相邻两数为绝对值相同的负数时,idx不会前进
                if(Math.abs(nums[idx]) >= Math.abs(nums[idx + 1])){
                    idx++;
                }
                continue;
            }
            nums[idx] = -nums[idx];
        }
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        return sum;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

134. 加油站

链接:https://leetcode.cn/problems/gas-station/

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

135. 分发糖果

链接:https://leetcode.cn/problems/candy/
两侧分别求最优-局部最优
最终得到整体最优

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

闽ICP备14008679号