【贪心算法Part03】| 1005.K次取反后最大化的数组和、134.加油站、135.分发糖果-Toy模板网

这篇具有很好参考价值的文章主要介绍了【贪心算法Part03】| 1005.K次取反后最大化的数组和、134.加油站、135.分发糖果。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

🎈LeetCode134.加油站

🎈LeetCode135.分发糖果

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

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

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

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

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

【贪心算法Part03】| 1005.K次取反后最大化的数组和、134.加油站、135.分发糖果,贪心算法,算法

方法一：

直接把最小的一直取反，但是时间复杂度为O(n^2logn)

public int largestSumAfterKNegations(int[] nums, int k) {
        for(int i=0;i<k;i++){
            Arrays.sort(nums);
            nums[0]=-nums[0];    
        }
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        return sum;
    }

🎈LeetCode134.加油站

链接：134.加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

【贪心算法Part03】| 1005.K次取反后最大化的数组和、134.加油站、135.分发糖果,贪心算法,算法

方法一：

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int min=Integer.MAX_VALUE;
        int curSum=0;
        for(int i=0;i<gas.length;i++){
            int temp=gas[i]-cost[i];   //每天的剩余油量
            curSum+=temp;
            if(curSum<min){
                min=curSum;
            }
        }
        if(curSum<0){
            return -1;   //油量总和小于要用的油
        }
        if(min>=0){
            return 0;   //从0出发油没有断过
        }
        // 不是从0出发的情况
        for(int i=gas.length-1;i>=0;i--){
            int temp=gas[i]-cost[i];
            min += temp;
            if(min>=0){
                return i;
            }
        }
        return -1;
    }
}

方法二：

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

🎈LeetCode135.分发糖果

链接：135.分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。

相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

【贪心算法Part03】| 1005.K次取反后最大化的数组和、134.加油站、135.分发糖果,贪心算法,算法文章来源地址https://www.toymoban.com/news/detail-598395.html

public int candy(int[] ratings) {
        int[] candys=new int[ratings.length];
        for(int i=0;i<candys.length;i++){
            candys[i]=1;
        }
        
        // 从前向后
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1]){
                candys[i]=candys[i-1]+1;
            }
        }
        // 从后向前
        for(int i=ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                candys[i]=Math.max(candys[i],candys[i+1]+1);
            }
        }
        int result=0;
        for(int i=0;i<candys.length;i++){
            result+=candys[i];
        }
        return result;
    }

到了这里，关于【贪心算法Part03】| 1005.K次取反后最大化的数组和、134.加油站、135.分发糖果的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！