1005.K次取反后最大化的数组和
2024-10-01 06:35:47
1005.K次取反后最大化的数组和
题目
给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)
以这种方式修改数组后,返回数组可能的最大和。
示例 1:
输入:A = [4,2,3], K = 1
输出:5
解释:选择索引 (1,) ,然后 A 变为 [4,-2,3]。
示例 2:
输入:A = [3,-1,0,2], K = 3
输出:6
解释:选择索引 (1, 2, 2) ,然后 A 变为 [3,1,0,2]。
示例 3:
输入:A = [2,-3,-1,5,-4], K = 2
输出:13
解释:选择索引 (1, 4) ,然后 A 变为 [2,3,-1,5,4]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
每次需要变换的都是最小的数。这里就需要找出最小的数。
对于有负数的数组,从最小值的开始变,直到k用完或者没有负数了。
对于全是正数的数组,k为偶数的时候不用变化,k为奇数的时候,操作一次最小数就行了。
可以先对数组进行从小到大的排序,但是变化之后的数组不一定也是有序的。
方法1:先把所有的负数变为正数,在循环过程中维护最小值,如果全正之后k还没有用完,就操作最小值。
方法2:为了让变化之后的数组仍然以一定的规则有序,可以使用对绝对值大小进行排序,这样变化之后的绝对值大小是不变的。这样不用去维持最小值,最小值为sum[0]。
排序+维护最小值min
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
int len = nums.length;
int sum=0;
int min=Integer.MAX_VALUE;
Arrays.sort(nums); //排序
for(int i=0;i<len;i++){
//负数变成正数,k--
if(nums[i]<0 && k>0){
nums[i]=-nums[i];
--k;
}
if(min>nums[i]) min=nums[i]; //维持最小值
sum+=nums[i]; //求和
}//结束之后元素全是正数
if(k==0||k%2==0) return sum;
return sum-min*2;
}
}
最新文章
- 判断windows操作系统平台
- OC-通讯录
- C++学习笔记(八):函数重载、函数指针和函数对象
- 计算 unique word numbers
- maven install 跳过 测试 test
- 数据挖掘 决策树算法 ID3 通俗演绎
- jerasure 2.0译文
- 【比赛】NOIP2018 铺设道路
- Office_PPT_让你一分钟完成上百张图片的快速保存
- 体验jQuery和AngularJS的不同点以及AngularJS的迷人之处
- 软工网络15团队作业4——Alpha阶段敏捷冲刺7.0
- 吴裕雄 oracle 管理数据表对象
- IOS 沙盒与清除缓存
- Mac 下配置php环境
- TensorFlow笔记-01-开篇概述
- python全栈开发-面向对象-进阶2
- qt 把整形数据转换成固定长度字符串(转)
- velecity报错:Caused by: org.apache.velocity.exception.ParseErrorException: Lexical error, Encountered: <;EOF>; after : ";\&#39;/order/pay?activity=\"; + activityId);\r\n }*/\r\n<;/script>;\r\n#end\r\n"; at /a
- Oracle作业3 —— 简单查询
- 51Nod 1002 数塔取数问题