想要精通算法和SQL的成长之路K次取反后最大化的数组和

想要精通算法和SQL的成长之路 - 系列导航

原题链接

给你一个整数数组 nums 和一个整数 k &＃xff0c;按以下方法修改该数组&＃xff1a;选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后&＃xff0c;返回数组可能的最大和 。

• 输入&＃xff1a;nums &＃61; [4,2,3], k &＃61; 1
• 输出&＃xff1a;5
• 解释&＃xff1a;选择下标 1 &＃xff0c;nums 变为 [4,-2,3] 。

1.1 错误的做法

那么这题也是一个贪心思想&＃xff1a;

• 尽可能的保持正数不要改变&＃xff0c;如果k&＃61;0那最好。
• 优先把负数取反&＃xff0c;负数越小越好。
• 如果负数全部取反了&＃xff0c;k依旧>0怎么办?那只能对正数取反呀&＃xff0c;越小越好。

那么对于上面而言&＃xff0c;越小越好&＃xff0c;那不就是要对数组排序嘛&＃xff1a;

Arrays.sort(nums);


那么第一反应&＃xff1a;

1. 排序完&＃xff0c;从前到后遍历&＃xff0c;将前面的数字尽管取反即可。同时k减1。
2. 一旦k<&＃61;0的时候&＃xff0c;后面的数字尽管加就好了。

那么不难得出代码如下&＃xff1a;

public int largestSumAfterKNegations(int[] nums, int k) {
// 排序
Arrays.sort(nums);
int count &＃61; 0;
for (int i &＃61; 0; i < nums.length; i&＃43;&＃43;) {
if (k <&＃61; 0) {
count &＃43;&＃61; nums[i];
continue;
}
count &＃43;&＃61; -nums[i];
k--;
}
return count;
}


但是这样是错的&＃xff1a;

仔细想想为啥&＃xff1f;题目里面有一句话&＃xff1a;可以多次选择同一个下标 i &＃xff0c;芜湖&＃xff0c;那破案了。我们的程序写出来之后&＃xff0c;每个元素只遍历了一次。

那么上面的一个测试案例&＃xff0c;正确的做法是&＃xff1a;

1. -1这个元素反转一次。
2. 0这个元素反转两次。最终结果1&＃43;2&＃43;3&＃43;0&＃61;6。

1.1 正确的做法

1. 我们累加数组元素的时候&＃xff0c;应该优先加入绝对值大的数字。因此我们不能从小到大排序&＃xff0c;应该根据绝对值来从大到小排序。
2. 遍历过程中&＃xff0c;遇到负数&＃xff0c;反转一次。
3. 遍历完之后&＃xff0c;如果k还是>0&＃xff0c;那么就取绝对值最小的数字&＃xff0c;也就是排序后的最后一个数字。将其反转n在这里插入代码片次&＃xff0c;直到k&＃61;&＃61;0。
4. 最后一次性统计值即可。

代码如下&＃xff1a;

public int largestSumAfterKNegations(int[] nums, int k) {
// 排序
nums &＃61; Arrays
.stream(nums)
.boxed()
.sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
.mapToInt(Integer::intValue)
.toArray();
int len &＃61; nums.length;
// 优先先把负数转换
for (int i &＃61; 0; i < len; i&＃43;&＃43;) {
if (nums[i] < 0 && k > 0) {
nums[i] &＃61; -nums[i];
k--;
}
}
// 如果k是偶数&＃xff0c;那么反转两次还是本身&＃xff0c;因此如果为奇数&＃xff0c;反转一次即可
if (k % 2 &＃61;&＃61; 1) {
nums[len - 1] &＃61; -nums[len - 1];
}
// 统计累加
return Arrays.stream(nums).sum();
}


知识点&＃xff1a;

1. sorted()函数&＃xff1a;sorted自定义排序的话&＃xff0c;需要操作面向对象类&＃xff0c;因此int类型需要转化为Integer类型。
2. boxed()函数&＃xff1a;就相当于把int转为Integer。