本文主要是介绍贪心算法基础题(第三十四天)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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]);}
}
这篇关于贪心算法基础题(第三十四天)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
