办公网新闻上传网站开发,网站ip如何做跳转,做网站打广告,山东电力建设第三工程公司网站题目
给定一个整数数组 A#xff0c;我们只能用以下方法修改该数组#xff1a;我们选择某个索引 i 并将 A[i] 替换为 -A[i]#xff0c;然后总共重复这个过程 K 次。#xff08;我们可以多次选择同一个索引 i。#xff09;
以这种方式修改数组后#xff0c;返回数组可能…题目
给定一个整数数组 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]。 提示 1 A.length 10000 1 K 10000 -100 A[i] 100 思路1每次只取反数组中最小的元素
对示例进行逐步拆解
class Solution {
public:int largestSumAfterKNegations(vectorint A, int K) {auto minPosition min_element(A.begin(), A.end());while(K 0){*minPosition -*minPosition;minPosition min_element(A.begin(), A.end());K--;}int sum 0;for(int i 0;i A.size();i)sumA[i];return sum;}
};思路2按绝对值大小排序做。
1、将数组按照绝对值大小从大到小排序 2、从前向后遍历如果遇到负数将其变为正数同时K– 3、遍历完整个数组如果K0,那么反复转变数值最小的元素将K用完。 4、求和 5、技巧遍历完整个数组后这里数值最小的元素必定是最后一个元素可以直接判断K的奇偶性来进行计算,K为偶数不需要做修改K为奇数则只需要取反一次。
class Solution {
public:static bool cmp(int a,int b){return abs(a) abs(b);}int largestSumAfterKNegations(vectorint A, int K) {int n A.size();//1、将数组按照绝对值大小从大到小排序sort(A.begin(),A.end(),cmp);//2、从前向后遍历如果遇到负数将其变为正数同时K--for(int i 0;i n;i){if(A[i] 0 K 0) {A[i] -A[i];K--;}}//3、遍历完整个数组如果K0,那么反复转变数值最小的元素将K用完。//技巧这里数值最小的元素必定是最后一个元素可以直接判断K的奇偶性来进行计算,K为偶数不需要做修改K为奇数则只需要取反一次。if(K % 2 1) A[n - 1] -A[n - 1];//4、求和int sum 0;for(int i 0;i A.size();i)sumA[i];return sum;}
};两种方法的比较
