1005.K次取反后最大化的数组和
每日编程中遇到任何疑问、意见、建议请公众号留言或直接撩Q474356284(备注每日编程)
给定一个整数数组 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)算法的基本思想:
算法一:
只要K未减为0,每次都找到数组的最小值,将其取反,最后求和。
算法二:
对数组从大至小排序,遍历数组。
如果当前数组元素大于0,则加至res
如果当前数组元素小于0,
K大于0,则取反,加至res中
K小于等于0,直接加至res中
遍历完数组后对K进行判断,如果K为奇数,则res需要减去最后一个元素(最小值)的2倍。
(注:比如4,3,2数组,K = 1,res = 4+3+2,如果K为偶数,我们可以将2取反变成-2,再取反变成2,但是如果K为奇数,我们总要将数组中的其中一个数取反,而在遍历数组的过程中,我们遇到正的就加起来了,并未取反,所以最后需要减掉最小值的2倍)
(2)代码实现:
{ public: intlargestSumAfterKNegations(vector<int>&A,intK){ while(K--) { autosmallest=min_element(begin(A),end(A)); (*smallest)*=-1; } returnaccumulate(A.begin(),A.end(),0); } };classSolution
{ public: intlargestSumAfterKNegations(vector<int>&A,intK){ sort(A.begin(),A.end(),[](inta,intb){returnabs(a)>abs(b);}); intres=0; for(intele:A) { if(ele>=0) res+=ele; else K>0?res+=-ele,K--:res+=ele; } //res=x+abs(s)==>whatwewantisres=x-abs(s),so: if(K%2) res-=2*abs(A.back()); returnres; } };classSolution
明日预告:中南大学上机题(一)
大家都很关心考试的难易程度。K老师出题有一个规律,在出题之前,他会随机写下一个字符串,只要在这个字符串中能按顺序找到E,A,S,Y四个字母,他出题就会比较简单。你拿到了字符串,请你告诉别人题目难不难吧。
输入格式:
输入的数据有多组,每组占一行,由一个字符串组成(字符串的长度不超过1000)。
输出格式:
对于每组输入数据,输出一行,对应一个要求的答案(题目简单就输出easy,难就输出difficult)输入样例:
SEoAtSNYeAsy
输出样例:
easydifficult