1.
class Solution {
public int largestSumAfterKNegations(int[] nums, int K) {
// 将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
nums = IntStream.of(nums)
.boxed()
.sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
.mapToInt(Integer::intValue).toArray();
int len = nums.length;
for (int i = 0; i < len; i++) {
//从前向后遍历,遇到负数将其变为正数,同时K--
if (nums[i] < 0 && K > 0) {
nums[i] = -nums[i];
K--;
}
}
// 如果K还大于0,那么反复转变数值最小的元素,将K用完
if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
return Arrays.stream(nums).sum();
}
}
2.
代码随想录 (programmercarl.com)
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int index = 0;
for (int i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) { //负数情况,只能从i+1开始
index = (i + 1) % gas.length ;
curSum = 0;
}
}
if (totalSum < 0) return -1; //总和小于0,一定不符合
return index;
}
}
3.文章来源:https://www.toymoban.com/news/detail-505102.html
文章来源地址https://www.toymoban.com/news/detail-505102.html
class Solution {
/**
分两个阶段
1、起点下标1 从左往右,只要 右边 比 左边 大,右边的糖果=左边 + 1
2、起点下标 ratings.length - 2 从右往左, 只要左边 比 右边 大,此时 左边的糖果应该 取本身的糖果数(符合比它左边大) 和 右边糖果数 + 1 二者的最大值,这样才符合 它比它左边的大,也比它右边大
*/
public int candy(int[] ratings) {
int len = ratings.length;
int[] candyVec = new int[len];
candyVec[0] = 1;
for (int i = 1; i < len; i++) { //从左往右遍历
candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
}
for (int i = len - 2; i >= 0; i--) { //从右往左遍历
if (ratings[i] > ratings[i + 1]) {
candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
}
}
int ans = 0;
for (int num : candyVec) {
ans += num;
}
return ans;
}
}
到了这里,关于DAY34——贪心part3的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!