算法细节系列（21）：贪心有理？
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434752
算法细节系列（21）：贪心有理？
详细代码可以fork下Github上leetcode项目，不定期更新。
题目摘自leetcode：
刷完挑战，继续刷leetcode，遇到的第一个题就是IPO，而这恰巧是贪心系列，那就顺便把贪心给学了，多门技术，多条生路。
《算法导论》也有关于贪心算法的相关章节，但我还不敢看，无非怕被书中的论述思维给限制住了。所以先刷点题，对贪心有了基本了解后，回过头来再看它的论证。
我所理解的贪心：
贪心，每一步决策都是局部最优的？一种短视的行为？好吧，这是我对贪心最真切的认识了，没有其他。日后，刷题时逐一完善加深对贪心的理解，话不多说，直接开始。
Leetcode 502: IPO
求n个项目所能累加的最大profit。
呵呵哒，leetcode的题目有个很大的特色，很多题在解释中把思路明确告诉你了，我一开始就纳闷了，直接找符合capital中的最大profit累加即可？好像也符合贪心的策略，选择局部最优。
思路：
没错，按照题目的意思来就可以了，代码如下：
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
int total = W;
for (int i = 0; i < k; i++){
int maxProfit = 0;
//find the max Profit
int index = -1;
for (int j = 0; j < Capital.length; j++){
if (Capital[j] <= total){
if (maxProfit < Profits[j]){
maxProfit = Profits[j];
index = j;
}
}
}
if (index == -1) return total;
Capital[index] = Integer.MAX_VALUE;
total += maxProfit;
}
return total;
}TLE了，如果有n个项目，那么上述代码时间复杂度为O(n2)O(n^2)。嘿，其实在它贪心的背后，它是一道数据结构题，用到了优先队列。
提到优先队列，相信你能很快想出了思路，但这对我来说，不够完美，如果不提优先队列这想法，我就很难想到用这数据结构了。所以，我慢慢分析下为啥用到了优先队列。
之前的博文中，我有提过所有的循环遍历，如果没有容器记录状态，都是无记忆遍历，它们是一种非常低级的手段。就拿上述代码：
for (int j = 0; j < Capital.length; j++){
if (Capital[j] <= total){
if (maxProfit < Profits[j]){
maxProfit = Profits[j];
index = j;
}
}
}遍历整个capital数组，只为找到最大值？更何况，当我使用完该最大值，我还得从capital数组中把它标识为不可使用状态，所以这样一个循环遍历，每次都得遍历整个数组，然后找出一个次大的。
嘿，这个特征比较符合优先队列了，用过的元素直接poll出去，而在队头的元素是次大的，直接把它poll出来。而构建优先队列的时间复杂度只有O(logn)O(\log n)，这是高级数据结构本身的特点，在构建之初就把大小关系维护进去，让它再插入新元素时，能够以较快的速度筛选出最大or最小。
思路：
- 构造一个pair对，把profit和capital关联起来，两者有着一一对应的关系。
- 筛选资产，在当前总资产下，把所有capitali小于等于当前总资产取出，并存入另外一个优先队列中。
- 该优先队列维护profit的大小关系，队头永远是符合资产中的最大profit（一种贪心策略）
总结：
看到删除+最大or最小，想想优先队列。
代码如下：
private class Pair{
int profit;
int capital;
Pair(int profit, int capital){
this.profit = profit;
this.capital = capital;
}
}
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
int n = Profits.length;
Pair[] pairs = new Pair[n];
for (int i = 0; i < n; i++){
pairs[i] = new Pair(Profits[i],Capital[i]);
}
PriorityQueue<Pair> q1 = new PriorityQueue<>((o1,o2) -> (o1.capital - o2.capital));
PriorityQueue<Pair> q2 = new PriorityQueue<>((o1,o2) -> (o2.profit - o1.profit));
for (int i = 0; i < n; i++){
q1.offer(pairs[i]);
}
int total = W;
for (int i = 0; i < k; i++){
while (!q1.isEmpty() && q1.peek().capital <= total){
q2.offer(q1.poll());
}
if (q2.isEmpty()) return total;
total += q2.poll().profit;
}
return total;
}Leetcode 055: Jump Game
这道题可谓是麻雀虽小，五脏俱全啊，贪心的味道很浓，得深入分析分析。
首先，看到这道题的第一眼，我想到了递归，思路如下：
根据当前能够jump的步数，选择后续的位置，这样就变成了相同的子问题，而只要最终pos能够抵达数组末端就能返回true。可谓是信心满满啊，为了防止TLE，还加了记忆化手段，代码如下：
public boolean canJump(int[] nums) {
boolean[] dp = new boolean[nums.length];
return canJump(nums,0,dp);
}
private boolean canJump(int[] nums, int pos,boolean[] dp){
if (dp[pos]) return false;
if (pos >= nums.length - 1) return true;
else{
int step = nums[pos];
for (int i = 1; i <= step; i++){
if (canJump(nums,pos + i,dp)){
return true;
}
}
}
dp[pos] = true;
return false;
}呵呵哒，stackoverflow了，这只能说明我还太嫩，递归显然无法解决该问题了，那这样，就用动规咯，所以又想了个动规的方案。代码如下：
public boolean canJump(int[] nums) {
boolean[] dp = new boolean[nums.length];
dp[0] = true;
for (int i = 0; i < nums.length; i++) {
if (!dp[i]) continue;
int step = nums[i];
for (int j = 1; j <= step; j++) {
if (i + j >= nums.length)
continue;
dp[i + j] = dp[i] || dp[i + j];
}
}
return dp[nums.length - 1];
}结果TLE了，TLE的原因在于step，上述代码，i每递增一次，都会更新step步的dp，如：
nums = [25000,25000,24000,1]
显然没必要更新step步，25000能走的位置涵盖了所有位置，应该直接返回true即可。此时，有了贪心，该贪心的含义是说，每到一个新的位置时，更新我能覆盖的所有范围（取最大），这就意味着，dp的状态没必要全部更新，因为我们知道在该范围内的dp都可以是true，换句话说，我们只需要知道一个边界即可。
所以代码如下：
public boolean canJump(int[] nums) {
int max = 0;
for (int i = 0; i < nums.length; i++){
if (i > max) return false;
max = Math.max(max, nums[i] + i);
if (max >= nums.length-1) return true;
}
return true;
}结构比起动规简单很多，只需要O(n)O(n)的时间复杂度。
Leetcode 330: Patching Array
这道题还未理解它，它的思路尝试来证明下，帮助理解这道题为什么是贪心。
思路：
Patching Array该问题的关键点在于用nums原有的数据集去构造0~n的数，举个最简单的例子：
nums = [1,2,5] n = 7
如何构造所有的和数？我们知道它们所有的和可以用三位1来表示：
111 表示 1+2+5=8
110 表示 1+2 = 3
所以总共有8种表示方法，如下：
000,001,010,011,100,101,110,111
得到的和从小到大排列为：
0,1,2,3,5,6,7,8
此处，我们可以明显看到当n=7时，缺了一个4，所以我们必须得补上。所以，
nums = [1,2,4,5] n = 7
以同样的方式构造所有和，得到：
0,1,2,3,4,5,6,7 (由1,2,4得)
在此处，我们还发现一个规律，当打一个补丁满足连续的数后，
我们在构造5的所有和时，可以直接在原来构造的和上加个5，所以有：
0,1,2,3,4,5,6,7
5,6,7,8,9,10,11,12
所以n在0~12之内都能满足条件，此时我们再来nums = [1,2,4,5,23], n = 100
我们知道：[1,2,4,5]构造的连续和为：
0,1,2,3,4,5,6,7,8,9,10,11,12
而为了能够构造尽可能多的和，构造的补丁一定为13，因为：
0,1,...,12
| 13,14,...,25
在这里你看到了贪心，nums = [1,2,4,5],但我们没有构造7的原因是因为构造7所能覆盖的范围非常少，如下:
0,1,2,...,6,...,12
| 7,8,9,10,...,19
构造7得到的范围为0-19，构造13能够得到的范围为0-25，你选谁？
在这里明确一个补丁的性质，在已有的连续和上，新的连续和是【补丁+已有连续和】，想想000-111,扩展到4位的情况。
而连续和我们只要维护一个界即可，所以有了网上大多数的做法，对具体做法感兴趣的，可以搜搜。代码如下：
public int minPatches(int[] nums, int n) {
long miss = 1;
int added = 0, i = 0;
while (miss <= n){
if (i < nums.length && nums[i] <= miss){
miss += nums[i++];
}
else{
miss += miss;
added++;
}
}
return added;
}注意miss的long，防止溢出，进入死循环。