系列文章目錄

代碼隨想錄——回溯
代碼隨想錄——貪心算法

概述

簡單

分發(fā)餅干

鏈接：https://leetcode.cn/problems/assign-cookies/description/
這道題我自己一開始的想法是從大到小遍歷孩子數(shù)組，對于每個(gè)元素從大到小遍歷餅干數(shù)組，滿足則total+1,并且該元素置0防止被再次使用。這樣雖然是可以的，但時(shí)間復(fù)雜度為O（n2），更好的做法是同時(shí)從大到?。ɑ蛘邚男〉酱螅┍闅v兩個(gè)數(shù)組，對應(yīng)餅干不滿足時(shí)則額外向前一位，這樣的時(shí)間復(fù)雜度是O（n）。

擺動(dòng)序列

鏈接：https://leetcode.cn/problems/wiggle-subsequence/description/
擺動(dòng)序列一定滿足(nums[ n + 1] - nums[n]) * (nums[ n ] - nums[n - 1]) < 0，所以我們可以通過tag和pre_tag變量分別表示當(dāng)前差值和前一個(gè)差值，由于只要前兩個(gè)數(shù)不相同，則必然滿足條件，所以初始的pre_tag設(shè)為0，只有新的元素不相同時(shí)，才更新tag和pre_tag。

***最大子數(shù)組和

鏈接：https://leetcode.cn/problems/maximum-subarray/description/
這題一開始往滑動(dòng)區(qū)間的想法上靠了，貪心算法的思路是順序往后加，但一旦總和為負(fù)數(shù)之后，那么這段必然不在最大子序列之內(nèi)，所以直接從下一個(gè)元素從頭加起。
需要注意的是，一開始我將max = 0，但其實(shí)序列完全可能全是負(fù)數(shù)，所以應(yīng)該定位INT32_MIN，然后先比較賦值，再判斷是否舍棄當(dāng)前序列。

買賣股票的最佳時(shí)機(jī) II

鏈接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
這題的貪心想法是不必考慮在最低買入最高賣出，我只需要保證如果賣出昨天買入今天是賺得，則當(dāng)日的收益就為正，所有收益都為正，則最后一定是最高的收益。

跳躍游戲

https://leetcode.cn/problems/jump-game/description/
對于每一個(gè)元素，都可以得到一個(gè)最遠(yuǎn)可跳至的范圍。那可以在這個(gè)范圍內(nèi)遍歷，每到一個(gè)新元素，便將這個(gè)元素可到達(dá)的范圍與之前的最大范圍進(jìn)行對比，如果更大則更新這個(gè)范圍，直至范圍無法再被更新，最后判斷這個(gè)范圍是否能到數(shù)組結(jié)尾。

跳躍游戲II

https://leetcode.cn/problems/jump-game-ii/description/
現(xiàn)在是必然可以跳到最后，但是求最小步數(shù)。還是拆分成局部最優(yōu)，即記錄當(dāng)前元素能跳至的最遠(yuǎn)距離，然后在這個(gè)范圍內(nèi)遍歷，找到下一步能跳至的最遠(yuǎn)距離，此時(shí)步數(shù)+1,每一步都跳得是最遠(yuǎn)的距離，最后一定是最短步數(shù)到終點(diǎn)。

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

https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
這題一開始沒注意到只要返回值就行，以為不能sort，但sort之后打算負(fù)數(shù)都轉(zhuǎn)正，正數(shù)最小的轉(zhuǎn)負(fù)，但這樣其實(shí)也不對，因?yàn)橛锌赡艹霈F(xiàn)-1，10這種情況，正確的想法是將數(shù)組按絕對值排序，然后盡可能將負(fù)數(shù)轉(zhuǎn)正，如果此時(shí)還有額外的k，則將絕對值最小的數(shù)轉(zhuǎn)負(fù)。

加油站

https://leetcode.cn/problems/gas-station/description/
思路就是兩個(gè)數(shù)組相減，得到的是到達(dá)該站所剩余的油量，把這些油量加起來，只要總數(shù)不為0，則一定可以到達(dá)該站。那么怎么實(shí)現(xiàn)環(huán)狀呢，只要在復(fù)制一份vector放在后面，就可以實(shí)現(xiàn)環(huán)狀，因?yàn)樽疃嗖粫?huì)超過一圈。

***分發(fā)糖果

https://leetcode.cn/problems/candy/description/
這道題的比左右兩遍都大，如果同時(shí)判斷一定會(huì)出錯(cuò)，所以好的方式是兩遍遍歷，從前到后遍歷判斷左比右大，從后到前遍歷判斷右比左大，由于這兩個(gè)條件是都必須滿足的，所以最后結(jié)果去較大值。

檸檬水找零

https://leetcode.cn/problems/lemonade-change/description/
維護(hù)5塊和10塊的數(shù)量，每次找零后統(tǒng)計(jì)判斷，小于0則沒法找零。

***根據(jù)身高重建隊(duì)列

https://leetcode.cn/problems/queue-reconstruction-by-height/description/
核心思想是矮個(gè)子的位置不會(huì)影響到高個(gè)子，所以應(yīng)該先從大到小排序，然后從高個(gè)子開始按規(guī)則放到指定位置，這樣后面的矮個(gè)子移動(dòng)不會(huì)影響到高個(gè)子。由于涉及到insert，應(yīng)該使用list。

用最少數(shù)量的箭引爆氣球

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
本質(zhì)上是一個(gè)求交集的問題，首先按起始位置從小到大排序，然后從頭開始逐個(gè)往后比，如果有交集，則范圍變成交集，直到?jīng)]有交集之后，就相當(dāng)于必須要再射一箭，此時(shí)箭++。

無重疊區(qū)間

https://leetcode.cn/problems/non-overlapping-intervals/description/
和上一題很類似，還是先按起始位置從小到大排序，從頭比較，如果有交集，則去除的數(shù)量+1，直到?jīng)]有交集為止。但這里有一個(gè)重要的條件就是，如果下一個(gè)范圍是當(dāng)前范圍的真子集，即當(dāng)前范圍完全包含了下一個(gè)范圍，則要去掉的是當(dāng)前范圍（做一個(gè)break的判斷）。

***劃分字母區(qū)間

https://leetcode.cn/problems/sudoku-solver/
不太會(huì)寫，統(tǒng)計(jì)每個(gè)字母最后出現(xiàn)的位置，一旦出現(xiàn)了，就分一塊。

合并區(qū)間

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
思路基本上一樣，先排序，有交集就合并，沒有交集了就push_back進(jìn)結(jié)果里去。

***單調(diào)遞增的數(shù)字

https://leetcode.cn/problems/monotone-increasing-digits/description/
這題的思路一開始不會(huì)，想法其實(shí)是只要出現(xiàn)前一個(gè)數(shù)字比后一個(gè)數(shù)字大，那么就應(yīng)該這位數(shù)字-1，后面所有都變成9，這就是最大的滿足條件的數(shù)字。

***監(jiān)控二叉樹

https://leetcode.cn/problems/binary-tree-cameras/description/
復(fù)習(xí)完二叉樹回頭再寫。文章來源地址http://www.zghlxwxcb.cn/news/detail-835598.html

到了這里，關(guān)于代碼隨想錄——貪心算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！