贪心算法基础题(第三十四天)

本文主要是介绍贪心算法基础题(第三十四天)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目

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

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

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

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

答案

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {nums = IntStream.of(nums).boxed().sorted((a,b)->Math.abs(a)-Math.abs(b)).mapToInt(Integer::intValue).toArray();for(int i=nums.length-1;i>=0;i--){if(nums[i]<0 && k>0){nums[i] = -nums[i];k--;}}if(k>0 && k%2==1){nums[0] = - nums[0];}int res = 0;for(int num : nums){res += num;}return res;}
}

134. 加油站

题目

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

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

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

答案

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int tatolSum = 0;int currSum = 0;int index = 0;for(int i=0;i<gas.length;i++){tatolSum += gas[i] - cost[i];currSum += gas[i] - cost[i];if(currSum<0){currSum = 0;index = (i+1)%gas.length;} }return tatolSum<0 ? -1 : index; }
}

135. 分发糖果

题目

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

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

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

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

答案

class Solution {public int candy(int[] ratings) {int[] arr = new int[ratings.length];arr[0] = 1;for(int i=1;i<arr.length;i++){arr[i] = ratings[i]>ratings[i-1] ? arr[i-1]+1 : 1; }for(int i=arr.length-2;i>=0;i--){if(ratings[i]>ratings[i+1]){arr[i] = Math.max(arr[i],arr[i+1]+1);}}int res = 0;for(int num : arr){res += num;}return res;}
}

860. 柠檬水找零

题目

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

答案

class Solution {public boolean lemonadeChange(int[] bills) {int fiveNum = 0;int tenNum = 0;for(int i=0;i<bills.length;i++){if(bills[i]==5){fiveNum++;}else if(bills[i]==10){fiveNum--;tenNum++;}else{if(tenNum>0){tenNum--;fiveNum--;}else{fiveNum -= 3;}}if(fiveNum<0){return false;}}return true;}
}

406. 根据身高重建队列

题目

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

答案

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b)->{if(a[0]==b[0]) return a[1]-b[1];return b[0] - a[0];});List<int[]> list = new ArrayList();for(int i=0;i<people.length;i++){list.add(people[i][1],people[i]);}return list.toArray(new int[people.length][2]);}
}