1005.K次取反后最大化的數(shù)組和

每日編程中遇到任何疑問(wèn)、意見(jiàn)、建議請(qǐng)公眾號(hào)留言或直接撩Q474356284(備注每日編程)

給定一個(gè)整數(shù)數(shù)組 A，我們只能用以下方法修改該數(shù)組：我們選擇某個(gè)個(gè)索引?i?并將?A[i]?替換為?-A[i]，然后總共重復(fù)這個(gè)過(guò)程?K?次。(我們可以多次選擇同一個(gè)索引?i。)

以這種方式修改數(shù)組后，返回?cái)?shù)組可能的最大和。

示例 1：

輸入：A = [4,2,3], K = 1輸出：5解釋：選擇索引 (1,) ，然后 A 變?yōu)?[4,-2,3]。

示例 2：

輸入：A = [3,-1,0,2], K = 3輸出：6解釋：選擇索引 (1, 2, 2) ，然后 A 變?yōu)?[3,1,0,2]。

示例 3：

輸入：A = [2,-3,-1,5,-4], K = 2輸出：13解釋：選擇索引 (1, 4) ，然后 A 變?yōu)?[2,3,-1,5,4]。

提示：

1 <= A.length <= 10000

1 <= K <= 10000

-100 <= A[i] <= 100

解決方法：

(1)算法的基本思想：

算法一：

只要K未減為0，每次都找到數(shù)組的最小值，將其取反，最后求和。

算法二：

對(duì)數(shù)組從大至小排序，遍歷數(shù)組。

如果當(dāng)前數(shù)組元素大于0，則加至res

如果當(dāng)前數(shù)組元素小于0，

????????K大于0，則取反，加至res中

????????K小于等于0，直接加至res中

遍歷完數(shù)組后對(duì)K進(jìn)行判斷，如果K為奇數(shù)，則res需要減去最后一個(gè)元素(最小值)的2倍。

(注：比如4,3,2數(shù)組，K = 1，res = 4+3+2，如果K為偶數(shù)，我們可以將2取反變成-2，再取反變成2，但是如果K為奇數(shù)，我們總要將數(shù)組中的其中一個(gè)數(shù)取反，而在遍歷數(shù)組的過(guò)程中，我們遇到正的就加起來(lái)了，并未取反，所以最后需要減掉最小值的2倍)

(2)代碼實(shí)現(xiàn)：

class?Solution
{
public:
????int?largestSumAfterKNegations(vector<int>?&A,?int?K){
????????while?(K--)
????????{
????????????auto?smallest?=?min_element(begin(A),?end(A));
????????????(*smallest)?*=?-1;
????????}
????????return?accumulate(A.begin(),?A.end(),?0);
????}
};class?Solution
{
public:
????int?largestSumAfterKNegations(vector<int>?&A,?int?K){
????????sort(A.begin(),?A.end(),?[](int?a,?int?b)?{?return?abs(a)?>?abs(b);?});

????????int?res?=?0;

????????for?(int?ele?:?A)
????????{
????????????if?(ele?>=?0)
????????????????res?+=?ele;
????????????else
????????????????K?>?0???res?+=?-ele,?K--?:?res?+=?ele;
????????}
????????//?res?=?x?+?abs(s)?==>?what?we?want?is?res?=?x?-?abs(s),?so:
????????if?(K?%?2)
????????????res?-=?2?*?abs(A.back());

????????return?res;
????}
};
明日預(yù)告：中南大學(xué)上機(jī)題(一)

大家都很關(guān)心考試的難易程度。K老師出題有一個(gè)規(guī)律，在出題之前，他會(huì)隨機(jī)寫下一個(gè)字符串，只要在這個(gè)字符串中能按順序找到E，A，S，Y四個(gè)字母，他出題就會(huì)比較簡(jiǎn)單。你拿到了字符串，請(qǐng)你告訴別人題目難不難吧。

輸入格式：

輸入的數(shù)據(jù)有多組，每組占一行，由一個(gè)字符串組成(字符串的長(zhǎng)度不超過(guò)1000)。

輸出格式：

對(duì)于每組輸入數(shù)據(jù)，輸出一行，對(duì)應(yīng)一個(gè)要求的答案(題目簡(jiǎn)單就輸出easy，難就輸出difficult)

輸入樣例：

eAsy
SEoAtSNY

輸出樣例：

difficult
easy

總結(jié)

以上是生活随笔為你收集整理的postgresql 遍历字符串数组_每日一道编程题（348）：1005.K次取反后最大化的数组和...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。