您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“貪心算法之如何實(shí)現(xiàn)K次取反后最大化的數(shù)組和”,感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“貪心算法之如何實(shí)現(xiàn)K次取反后最大化的數(shù)組和”吧!
很多錄友都反饋?zhàn)蛱斓念}目:貪心算法:跳躍游戲II 很難,這樣我就放心了,哈哈,因?yàn)槲覄倓傊v解貪心的時(shí)候一些錄友會(huì)建議我:貪心沒有必要單獨(dú)講,直接講動(dòng)規(guī)就可以了。應(yīng)該不少同學(xué)都會(huì)感覺就貪心嘛,有啥難的?,F(xiàn)在我們可以發(fā)現(xiàn)貪心的道理雖然簡(jiǎn)單,但解決問題都很巧妙,難度上不照動(dòng)規(guī)差多少。
今天是一道簡(jiǎn)單題,關(guān)鍵在于培養(yǎng)貪心的解題思路!
給定一個(gè)整數(shù)數(shù)組 A,我們只能用以下方法修改該數(shù)組:我們選擇某個(gè)索引 i 并將 A[i] 替換為 -A[i],然后總共重復(fù)這個(gè)過程 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
思路
本題思路其實(shí)比較好想了,如何可以讓 數(shù)組和 最大呢?
貪心的思路,局部最優(yōu):讓絕對(duì)值大的負(fù)數(shù)變?yōu)檎龜?shù),當(dāng)前數(shù)值達(dá)到最大,整體最優(yōu):整個(gè)數(shù)組和達(dá)到最大。
局部最優(yōu)可以推出全局最優(yōu)。
那么如果將負(fù)數(shù)都轉(zhuǎn)變?yōu)檎龜?shù)了,K依然大于0,此時(shí)的問題是一個(gè)有序正整數(shù)序列,如何轉(zhuǎn)變K次正負(fù),讓 數(shù)組和 達(dá)到最大。
那么又是一個(gè)貪心:局部最優(yōu):只找數(shù)值最小的正整數(shù)進(jìn)行反轉(zhuǎn),當(dāng)前數(shù)值可以達(dá)到最大(例如正整數(shù)數(shù)組{5, 3, 1},反轉(zhuǎn)1 得到-1 比 反轉(zhuǎn)5得到的-5 大多了),全局最優(yōu):整個(gè) 數(shù)組和 達(dá)到最大。
雖然這道題目大家做的時(shí)候,可能都不會(huì)去想什么貪心算法,一鼓作氣,就AC了。
「我這里其實(shí)是為了給大家展現(xiàn)出來 經(jīng)常被大家忽略的貪心思路,這么一道簡(jiǎn)單題,就用了兩次貪心!」
那么本題的解題步驟為:
第一步:將數(shù)組按照絕對(duì)值大小從大到小排序,「注意要按照絕對(duì)值的大小」
第二步:從前向后遍歷,遇到負(fù)數(shù)將其變?yōu)檎龜?shù),同時(shí)K--
第三步:如果K還大于0,那么反復(fù)轉(zhuǎn)變數(shù)值最小的元素,將K用完
第四步:求和
對(duì)應(yīng)C++代碼如下:
class Solution { static bool cmp(int a, int b) { return abs(a) > abs(b); } public: int largestSumAfterKNegations(vector<int>& A, int K) { sort(A.begin(), A.end(), cmp); // 第一步 for (int i = 0; i < A.size(); i++) { // 第二步 if (A[i] < 0 && K > 0) { A[i] *= -1; K--; } } while (K--) A[A.size() - 1] *= -1; // 第三步 int result = 0; for (int a : A) result += a; // 第四步 return result; } };
到此,相信大家對(duì)“貪心算法之如何實(shí)現(xiàn)K次取反后最大化的數(shù)組和”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。