初识贪心思想
- 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; } };
