初識貪心思想
- 2019 年 11 月 22 日
- 筆記
作者：小小演算法
初識貪心思想
貪心演算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。貪心演算法的本質就是，每次只顧眼前利益，並且到最後能獲得最大利益。 」
貪心和動態規劃一樣，考驗的是對問題分析的能力，貪心演算法解題的關鍵在於如何找到每次的局部最優解，動態規劃則是如何找到狀態轉移方程。
如何判斷一個題是不是貪心題呢？這裡沒有什麼套路，只要它能通過局部能得到全局最優，那就可以使用貪心思想的步驟去解決了。
接下來通過我從 leetcode 精選的一個貪心題來體驗一下貪心思想和這類題的解題步驟。
不同字元的最小子序列
返回字元串 text 中按字典序排列最小的子序列，該子序列包含 text 中所有的不同字元一次。
示例 1： 輸入："cdadabcc" 輸出："adbc"
示例 2： 輸入："ecbacba" 輸出："eacb"
解釋一下兩個名詞：
字典序：對於字元而言，按 ascii 碼值進行比較，小的排在前，大的排在後。對於字元串，從第 0 位字元開始比較，ascii 碼數值小的排在前面，如果相同，就延後一位比較 ascii 碼值大小。
子序列：子序列不同於子串，子串要求它們在原串中連續，而子序列則不要求連續。例如acd是abcd的子序列，但不是子串。
首先判斷能否用貪心演算法來解決
再次強調，一個題能不能用貪心思想來解決取決於它能不能通過局部最優得到全局最優。
這道題的全局最優是找到這樣一個子序列：「字典序排列最小並且包含 text 中所有的不同字元一次」。
例如，對於text = "cabcc"，滿足包含 text 中所有的不同字元一次的子序列有"cab"和"abc"，但其中字典序最小是"abc"。所以對於text = "cabcc"而言，它的全局最優就是"abc"。
image
通過對比我們發現，只要保證所求的子序列串中從第 0 位開始的每一個字元的 ascii 碼是最小的，那整個子序列的字典序就是最小的了。所以局部最優就是保證子序列從第 0 位開始子序列的每一個字元的 ascii 碼是最小的。
這樣我們就找到了可以到達全局最優的局部最優了，這就說明這道題可以使用貪心思想來解決。
如何得到局部最優
也就是如何保證子序列從第 0 位開始每個字元的 ascii 碼最小呢？
還是以text = "cabcc"為例， 我們可以每次都從 26 個英文字母表'a'~'z'依次遍歷，先看看a可不可以放到第一個：
image
我們發現 text 中沒有a，所以子序列中也不能有a。a不行我們再看看字母b可不可以：
image
這時我們發現 text 中有b了，但有b就可以填入了嗎？題目要求的是」包含 text 中所有的不同字元「，我們選擇b的話，還要看看pos後面的所有字元加上已選的字元b能不能包含 text 中所有的不同字元。
幸運的是pos後面還有字元c,e，加上b之後就正好是 text 中的所有字元了：e,b,c。所以子序列的第一個字元就確定下來了！填入b。
image
這樣我們就保證子序列的第 0 位填上了最優的字元。
按照這個選擇局部最優的方式再填充子序列下一位：從字母表'a'~'z'依次遍歷，a在 text 中沒有，b在子序列中已經存在了，最後發現c可以填入，並且pos後面的字元e可以和已選的b,c構成 text 中的所有字元，於是子序列第 1 位填上了最優字元c。
image
最後再按照相同的操作填入了e:
image
接著發現text中所有的唯一字元('e','b','c')都已經選過了，結束循環。
這樣按照每次都儘可能選擇 ascii 最小的字元進行填充所得到的子序列就是字典序最小的子序列了。
while (text中還有字元沒有選) { for (int i = 0; i < 26; i++) { if (text包含該字元 && 子序列可包含text中所有字元) { ret.push_back(i+'a'); //添加到子序列末尾 } } }
到了這步，貪心思想就已經完全體現出來了：每一次我們都在滿足一定條件下選擇字典序最小的字元，最後得到的子序列勢必是符合條件，並且字典序最小的。
接下來就到了將思想用程式體現出來的過程了，這個過程註定是樸實無華且枯燥you qu的。
我不建議大家直接閱讀程式碼，因為這道題的解題思想已經知道了，不妨理理思路，然後自己去實現它。
程式碼實現
這裡使用位掩碼來保存 text 中的所有字元：
int all = 0; for (int i = 0; i < len; i++) { all |= (1 << (text[i] - 'a')); }
使用all & (1 << i)來判斷 text 中是否包含字元i+'a'。
函數isOk(text, all, i+'a', pos)用來判斷字元i+'a'之後的所有字元能否包含 text 中剩下未選的所有字元，如果包含則附帶更新pos的位置。
all ^= (1 << i)表示將所選字元從剩下的字符集all中移除。
//pos表示所選的當前字元在text中的位置 int pos = 0; while (all) { for (int i = 0; i < 26; i++) { if ((all & (1 << i)) && isOk(text, all, i+'a', pos)) { ret.push_back(i+'a'); all ^= (1 << i); break; } } }
完整程式碼貼在了文末。
總結
像這類題型屬於純粹的使用貪心思想就能解決的問題，當然這道題的leetcode題解中還有很多巧妙的方法，不過不建議初學者立刻去學習這些巧妙的方法。前期多使用純粹的貪心思想解決題目會對我們理解貪心很有幫助。
這裡我還找了一個可以使用純粹貪心思想解決的題，大家有空可以去做做：
135. 分發糖果[1]
你知道嗎？Dijkstra 最短路徑演算法也使用了貪心思想，貪心思想還經常和二分、前綴和一起使用哦。加油吧。
完整程式碼：
class Solution { public: string smallestSubsequence(string text) { string ret = ""; int len = text.length(); int all = 0; for (int i = 0; i < len; i++) { all |= (1 << (text[i] - 'a')); } //pos表示所選的當前字元在text中的位置 int pos = 0; while (all) { for (int i = 0; i < 26; i++) { if ((all & (1 << i)) && isOk(text, all, i+'a', pos)) { ret.push_back(i+'a'); all ^= (1 << i); break; } } } return ret; } bool isOk(string& text, int all, char ch, int& pos) { int len = text.length(); int i = pos; for (; i < len; i++) { if (text[i] == ch) { break; } } int p = i+1; int t = 0; for (; i < len; i++) { if (all & (1 << (text[i]-'a'))) { t |= (1 << (text[i]-'a')); } } if (t == all) { pos = p; return true; } return false; } };
