题目描述:
给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组:
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后,返回数组 可能的最大和 。
LeetCode-1005题目链接
思路见注释~文章来源:https://www.toymoban.com/news/detail-693800.html
代码实现文章来源地址https://www.toymoban.com/news/detail-693800.html
class Solution {
/**
* 先分情况:
* ① 当数组中有正有负:优先将负数取反,负数中优先对找绝对值最大的进行取反;
* ② 当数组中全是正数:如果还有机会则找绝对值最小的进行取反
*
* 步骤:
* ① 按绝对值从大到小进行排序
* ② 从前往后遍历数组,遇到负数就取反,当 k 还没用完,判断奇偶,是奇数则对最后一个元素取反,偶数不操作
* ③ 求数组的和再返回即可
*/
public int largestSumAfterKNegations(int[] nums, int k) {
if (nums.length == 1){
if (k%2==0){//偶数,等于本身
return nums[0];
}else {
return -nums[0];// 奇数,会变成相反数
}
}
int sum = 0;
// 对数组进行排序是重点,这个地方我掌握的并不熟
nums = IntStream.of(nums)
.boxed()
.sorted((o1,o2) -> Math.abs(o2) - Math.abs(o1))
.mapToInt(Integer::intValue).toArray();
// Arrays.sort((x,y)->Math.abs(y) - Math.abs(x));
// Arrays.asList(nums).stream().sorted((x,y)->Math.abs(y) - Math.abs(x)).toArray();
// 第一次遍历取反
for (int i = 0; i < nums.length; i++) {
if (nums[i] <0 && k>0){
nums[i] *= -1;
k--;
}
}
if (k > 0){
if (k % 2==1){
nums[nums.length-1] *= -1;// 取反
}
}
// 第一种求和方法:第二次遍历求和
// for (int i = 0; i < nums.length; i++) {
// sum += nums[i];
// }
return Arrays.stream(nums).sum();//第二种求和方法
}
}
到了这里,关于LeetCode-1005-K次取反后最大化的数组和-贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!