網際網路面試題目「貪心算法」K次取反後最大化的數組和

2020-12-04 代碼隨想錄

很多錄友都反饋昨天的題目: 很難,這樣我就放心了,哈哈,因為我剛剛講解貪心的時候一些錄友會建議我:貪心沒有必要單獨講,直接講動規就可以了。應該不少同學都會感覺就貪心嘛,有啥難的。現在我們可以發現貪心的道理雖然簡單,但解決問題都很巧妙,難度上不照動規差多少。

今天是一道簡單題,關鍵在於培養貪心的解題思路!

1005.K次取反後最大化的數組和

題目地址:https://leetcode-cn.com/problems/maximize-sum-of-array-after-k-negations/

給定一個整數數組 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

思路

本題思路其實比較好想了,如何可以讓 數組和 最大呢?

貪心的思路,局部最優:讓絕對值大的負數變為正數,當前數值達到最大,整體最優:整個數組和達到最大。

局部最優可以推出全局最優。

那麼如果將負數都轉變為正數了,K依然大於0,此時的問題是一個有序正整數序列,如何轉變K次正負,讓 數組和 達到最大。

那麼又是一個貪心:局部最優:只找數值最小的正整數進行反轉,當前數值可以達到最大(例如正整數數組{5, 3, 1},反轉1 得到-1 比 反轉5得到的-5 大多了),全局最優:整個 數組和 達到最大。

雖然這道題目大家做的時候,可能都不會去想什麼貪心算法,一鼓作氣,就AC了。

「我這裡其實是為了給大家展現出來 經常被大家忽略的貪心思路,這麼一道簡單題,就用了兩次貪心!」

那麼本題的解題步驟為:

  • 第一步:將數組按照絕對值大小從大到小排序,「注意要按照絕對值的大小」
  • 第二步:從前向後遍歷,遇到負數將其變為正數,同時K--
  • 第三步:如果K還大於0,那麼反覆轉變數值最小的元素,將K用完
  • 第四步:求和

對應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;    }};

總結

貪心的題目如果簡單起來,會讓人簡單到開始懷疑:本來不就應該這麼做麼?這也算是算法?我認為這不是貪心?

本題其實很簡單,不會貪心算法的同學都可以做出來,但是我還是全程用貪心的思路來講解。

因為貪心的思考方式一定要有!

「如果沒有貪心的思考方式(局部最優,全局最優),很容易陷入貪心簡單題憑感覺做,貪心難題直接不會做,其實這樣就鍛鍊不了貪心的思考方式了」

所以明知道是貪心簡單題,也要靠貪心的思考方式來解題,這樣對培養解題感覺很有幫助。

此時,有沒有感覺Carl為了給大家寫出優質的題解真的是煞費苦心啊!!哈哈,還不趕緊幫忙宣傳一波「代碼隨想錄」,讓更多的小夥伴知道這裡,這樣Carl也更有動力寫下去呀![加油]

打算從頭開始打卡的錄友,可以在「算法匯總」這裡找到歷史文章,很多錄友都在從頭打卡,你並不孤單!

-------end-------

我將算法學習相關的資料已經整理到了Github :https://github.com/youngyangyang04/leetcode-master,裡面還有leetcode刷題攻略、各個類型經典題目刷題順序、思維導圖看一看一定會有所收穫,如果給你有幫助給一個star支持一下吧!

我是程式設計師Carl,個人主頁:https://github.com/youngyangyang04

更多精彩點擊下方了解更多!

相關焦點

  • 網際網路高頻面試題目:「回溯算法」求組合總和
    」和一樣,依然需要一維數組path來存放符合條件的結果,二維數組result來存放結果集。在上面已經說了,k其實就已經限制樹的深度,因為就取k個元素,樹再往下深了沒有意義。所以如果path.size() 和 k相等了,就終止。如果此時path裡收集到的元素和(sum) 和targetSum(就是題目描述的n)相同了,就用result收集當前的結果。
  • 網際網路公司經典面試題目:「回溯算法」求組合問題
    組合題目連結:https://leetcode-cn.com/problems/combinations/給定兩個整數 n 和 k,返回 1 ... n 中所有可能的 k 個數的組合。直接的解法當然是使用for循環,例如示例中k為2,很容易想到 用兩個for循環,這樣就可以輸出 和示例中一樣的結果。
  • 網際網路公司高頻面試題目「回溯算法」遞增子序列
    在中我們是通過排序,再加一個標記數組來達到去重的目的。而本題求自增子序列,是不能對原數組進行排序的,排完序的數組都是自增子序列了。「所以不能使用之前的去重邏輯!」「其實用數組來做哈希,效率就高了很多」。注意題目中說了,數值範圍[-100,100],所以完全可以用數組來做哈希。
  • 貪心算法:跳躍遊戲
    跳躍遊戲題目連結:https://leetcode-cn.com/problems/jump-game/給定一個非負整數數組,你最初位於數組的第一個位置。數組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最後一個位置。
  • 「西法帶你學算法」一次搞定前綴和
    二者在連續問題中,對於「優化時間複雜度」有著很重要的意義。 因此如果一道題你可以用暴力解決出來,而且題目恰好有連續的限制, 那麼滑動窗口和前綴和等技巧就應該被想到。我們來抽象一下,就是給你一個數組, 讓你「選定一個子數組, 這個子數組最多只有兩種數字」,這個選定的子數組最大可以是多少。這不就和母題 3 一樣麼?只不過 k 變成了固定值 2。
  • 網際網路公司高頻面試題目「回溯算法」:求組合總和II
    很多同學在去重的問題上想不明白,其實很多題解也沒有講清楚,反正代碼是能過的,感覺是那麼回事,稀裡糊塗的先把題目過了。這個去重為什麼很難理解呢,「所謂去重,其實就是使用過的元素不能重複選取。」」與套路相同,此題還需要加一個bool型數組used,用來記錄同一樹枝上的元素是否使用過。
  • 網際網路公司高頻面試題目:「回溯算法」電話號碼的字母組合
    大家應該感覺出和回溯算法:求組合問題!遇到的一樣的問題,就是這for循環的層數如何寫出來,此時又是回溯法登場的時候了。再來看參數,參數指定是有題目中給的string digits,然後還要有一個參數就是int型的index。注意這個index可不是 和中的startIndex了。這個index是記錄遍歷第幾個數字了,就是用來遍歷digits的(題目中給出數字字符串),同時index也表示樹的深度。
  • 騰訊面試題目「回溯算法」排列問題
    ,也就是說[1,2] 和[2,1] 是兩個集合,這和之前分析的子集以及組合所不同的地方」。當收集元素的數組path的大小達到和nums數組一樣大的時候,說明找到了一個全排列,也表示到達了葉子節點。「而used數組,其實就是記錄此時path裡都有哪些元素使用了,一個排列裡一個元素只能使用一次」。
  • (一文學會字符串算法題目)
    甚至一些同學習慣於調用substr,split,reverse之類的庫函數,卻不知道其實現原理,也不知道其時間複雜度,這樣實現出來的代碼,如果在面試現場,面試官問:「分析其時間複雜度」的話,一定會一臉懵逼!所以建議「如果題目關鍵的部分直接用庫函數就可以解決,建議不要使用庫函數。」
  • 網際網路公司高頻面試題目「回溯算法」求子集問題
    子集題目地址:https://leetcode-cn.com/problems/subsets/給定一組不含重複元素的整數數組 nums,返回該數組所有可能的子集(冪集)。說明:解集不能包含重複的子集。
  • 網際網路公司高頻面試題目「回溯算法」:分割回文串
    path存放切割後回文的子串,二維數組result存放結果集。可以使用雙指針法,一個指針從前向後,一個指針從後先前,如果前後指針所指向的元素是相等的,就是回文字符串了。除了這些難點,「本題還有細節,例如:切割過的地方不能重複切割所以遞歸函數需要傳入i + 1」。所以本題應該是一個道hard題目了。
  • 經典面試題目「回溯算法」解數獨
    大家已經跟著「代碼隨想錄」刷過了如下回溯法題目,例如:77.組合(組合問題),131.分割回文串(分割問題),78.子集(子集問題),46.全排列(排列問題),以及51.N皇后(N皇后問題),其實這些題目都是一維遞歸。
  • 貪心算法:跳躍遊戲II
    /給定一個非負整數數組,你最初位於數組的第一個位置。說明:假設你總是可以到達數組的最後一個位置。思路本題相對於貪心算法:跳躍遊戲還是難了不少。「這裡需要統計兩個覆蓋範圍,當前這一步的最大覆蓋和下一步最大覆蓋」。
  • 網際網路公司高頻面試題目「回溯算法」求子集問題(二)
    這道題目和區別就是集合裡有重複元素了,而且求取的子集要去重。那麼關於回溯算法中的去重問題,「在中已經詳細講解過了,和本題是一個套路」「劇透一下,後期要講解的排列問題裡去重也是這個套路,所以理解「樹層去重」和「樹枝去重」非常重要」。
  • 經典面試題目「回溯算法」求組合總和(二)
    組合總和題目連結:https://leetcode-cn.com/problems/combination-sum/給定一個無重複元素的數組 candidates 和一個目標數 target ,找出 candidates 中所有可以使數字和為 target 的組合。candidates 中的數字可以無限制重複被選取。
  • 「力扣」鍊表經典面試題目大總結!(每逢總結必經典)
    數組和鍊表在不同場景下的性能分析。反轉鍊表是面試中高頻題目,很考察面試者對鍊表操作的熟練程度。我在文章中,給出了兩種反轉的方式,迭代法和遞歸法。建議大家先學透迭代法,然後再看遞歸法,因為遞歸法比較繞,如果迭代還寫不明白,遞歸基本也寫不明白了。
  • 網際網路公司面試題目之哈希表總結篇!(每逢總結必經典)
    對於哈希表,要知道「哈希函數」和「哈希碰撞」在哈希表中的作用在中,我們提到了數組就是簡單的哈希表,但是數組的大小是受限的!這道題目包含小寫字母,那麼使用數組來做哈希最合適不過。在中同樣要求只有小寫字母,那麼就給我們濃濃的暗示,用數組!本題和很像,是求 字符串a 和 字符串b 是否可以相互組成,在中是求字符串a能否組成字符串b,而不用管字符串b 能不能組成字符串a。
  • 經典面試題目本周小結!(回溯算法系列一)
    「剪枝精髓是:for循環在尋找起點的時候要有一個範圍,如果這個起點到集合終止之間的元素已經不夠 題目要求的k個元素了,就沒有必要搜索了」。例如這裡for循環,可不像是在 和 中從startIndex開始遍歷的。「因為本題每一個數字代表的是不同集合,也就是求不同集合之間的組合,而回溯算法:求組合問題!和回溯算法:求組合總和!都是是求同一個集合中的組合!」
  • 字節跳動的算法面試題是什麼難度?
    由於 lucifer 我是一個小前端, 最近也在準備寫一個《前端如何搞定算法面試》的專欄,因此最近沒少看各大公司的面試題。都說字節跳動算法題比較難,我就先拿 ta 下手 。這次我們就拿一套 2018 年的前端校招(第四批)來看下字節的算法筆試題的難度幾何。
  • 數組:總結篇
    首先要知道數組在內存中的存儲方式,這樣才能真正理解數組相關的面試題「數組是存放在連續內存空間上的相同類型數據的集合。」數組可以方便的通過下表索引的方式獲取到下表下對應的數據。「二分法是算法面試中的常考題,建議通過這道題目,鍛鍊自己手撕二分的能力」。雙指針法 雙指針法(快慢指針法):「通過一個快指針和慢指針在一個for循環下完成兩個for循環的工作。」