Greedy (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（455:Easy）Assign Cookies

• 该题是一道非常简单的贪心算法题目，为了保证分到曲奇饼的小孩个数足够多，我们尽量用较小的曲奇饼满足greedy factor较小的小孩，而将较大size的曲奇饼分给较大greedy factor的小孩。

2.（406:Medium）（非常非常经典题）Queue Reconstruction by Height

• 其实该题很难辨别清楚：在局部条件下，最好的选择究竟是什么？根据思考和提示，我们可以在直观上这样认为，排序应该整体上是按高度排序，但又需要同时考虑到该位置前有多少个比他高或与他相等的人数，但所谓的局部最优个人感觉在该题中体现并不清晰。
• 其实解决该题还是需要运用一个技巧，那就是题目中的k的束缚。如果我们从高到低进行从无到有的排序,先排个子高的人,那么假如接下来排与他同高或比他低的人时,之前排过的人数一定会被算入k中,但后排序的人数不会对之前已排序的人的k值产生影响。因此，一个排序的过程可以理解为：从高到底、k值从小到大的顺序，将当前的人people[i]插入到之前已排序序列的people[i][1]位置上。

3.（392:Medium）（经典题）Is Subsequence

• 该题说实话是很简单的，正如之前我们在String类题目中碰到的子序列匹配问题，当判断一个字符串是否包含某个子序列的时候，我们以子序列为基准，不断向后移动指向字符串的指针进行比较即可。

该题也有动态规划的解法，可能是t的前j个字符是否包含s的前i个字符的思路，下次复习时可以仔细研究一下。同时follow up下次复习时也需要搞懂

4.（452:Medium）（非常经典题）Minimum Number of Arrows to Burst Balloons

• 这道题属于Greedy题目，所以直接从直觉上进行判断，如何才能以最少的箭射穿尽量多的气球。当然要寻找一个公共的区间，它可以尽量多的包含气球，最后我们找到的最少区间数就是射箭的个数。换句话说，我们从头开始遍历points数组，当已经求得的区间与当前遍历的区间有重合时，我们更新该已求得的区间为两者的交集，否则另开一个新的区间，该新区间就是当前遍历的未重叠区间。但该方法需要借助ArrayList来存储区间集合，效率并不高，beat 15%。
• 为了方便处理，类似于动态规划中的任务调度问题，我们根据区间的起始坐标进行排序，这样每次遍历区间时只需要与之前已求得区间集合的最后一个区间进行比较即可。
• 第二种方法是discuss的高票答案：我们以气球的结束位置排序，并尽可能在当前气球的结尾位置射箭来射穿该气球及范围包含该结尾位置的气球。代码思路如下：

public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }
        Arrays.sort(points, (a, b) -> a[1] - b[1]);
        int arrowPos = points[0][1];
        int arrowCnt = 1;
        for (int i = 1; i < points.length; i++) {
            if (arrowPos >= points[i][0]) {
                continue;
            }
            arrowCnt++;
            arrowPos = points[i][1];
        }
        return arrowCnt;
}

• 其实以上两种方法本质上思想是相同的

5.（435:Medium）（非常经典题）Non-overlapping Intervals

• 直观上感觉：我们应该删除区间范围大的元素，而留下区间范围小的元素。为了方便处理，做到区间范围的合理处理，应该先将数组进行排序。在排序时，可以根据区间的起点进行排序，也可以根据区间的结点进行排序。我在处理时，是根据起点进行排序，用preStart和preEnd记录之前一个区间的范围，如果当前区间与之前区间有重叠，则需要删除其中一个区间。在删除时，我们需要考虑，preEnd若比当前区间的结点值还大，则需要更新preStart和preEnd为当前的区间范围，删除之前的区间，因为我们要保证之前区间对之后区间的影响尽量小；否则我们删除当前区间。若当前区间与之前区间范围不重叠，则更新preStart和preEnd为当前区间值即可。
• 从Leetcode的提交结果上来看，根据区间结点值进行排序，处理起来会更简单，效率会更高。因为按结点值进行升序排列，我们每次若进行删除时，一定删除的是结点值在后的区间，因为之前的区间对之后区间的影响肯定相对会更小。实现参看代码。
• 注意：区间的start、end可能为负数。

6.（738:Medium）（非常经典题）Monotone Increasing Digits

• 分两种情况：如12345这样本身各位数字就是单调递增的数字，则直接返回原数即可。而对于本身非单调递增的数字，则再细分为两种情况。
• 非单调递增的数字：1.如123421这样的数字，在i=4时出现递减，则再[0,2]范围内保留原数即可，i=3的数字要进行减1，而i>3的数字全部填充为9。2.如345521这样的数字，在出现递减趋势i=4时，i=2和i=3的数字相同，此时我们应从i=2处就进行预处理，将i=2的数字进行减1，而i>2的数字应全部填充为9。因为如果要将i=3的数字减1，则最后结果为345499，仍然不是单调递增的。（beat 50%）

7.（649:Medium）（非常经典题）Dota2 Senate

• 该题是贪心算法题，为了争取利益的最大化，R党派参议员一定优先禁止相邻最近的下一个D党派参议员的权利，同样D党派也是优先禁止相邻下一个最近的R党派参议员权利。为了便于做出上述决策，我们分别用两个队列保存两个党派参议员的下标索引，同时取队列头进行比较，索引低的参议员会禁止另一个其他党派索引高的参议员，然后将该索引小的参议员的索引加n再次插入队尾，代表该参议员可以进入下一轮的投票过程。

8.（376:Medium）（非常非常经典题）Wiggle Subsequence

• 该题用贪心算法思想非常经典，非常奇妙。我们可以发现，如果要使数字序列相邻两数的difference上下摆动，要做到：小->大->小->大->...，而应用贪心算法思想，若要使该符合条件的子序列长度尽量长，应使小的数尽量小，大的数尽量大，这样才能找到一个最长子序列。我们可以参考下面的示例进行理解：

Now for explanation, we take example series:2,1,4,5,6,3,3,4,8,4

First we check if the series is starting as (big, small) or (small, big). So as 2,1 is big, small. So we will start the loop as we need small number first that is 1 as 2 is already there.

Step 1: First we check our requirement is to get small number. As 1<2 so the series will be 2,1

Step 2: Now we need big number that is greater than 1. As 4>1 so series will be 2,1,4

Step 3: Now we need small number. But 5>4 so 4 will be replaced by 5. So the series will become 2,1,5

Step 4: We need small number. But 6>5. Series will be 2,1,6

Step 5: Require small number. 3<6. Series will be 2,1,6,3

Step 6: Require big number. 3=3. No change in series 2,1,6,3

Step 7: Require big number. 4>3. Series will become 2,1,6,3,4

Step 8: Require small number. 8>4. 8 will replace 4 and series will become 2,1,6,3,8

Step 9: Require small number. 4<8. So final series will be 2,1,6,3,8,4

Answer is 6.

该题可能也可以用DP动态规划求解，下次复习时再研究

9.（842:Medium）（非常经典题）Split Array into Fibonacci Sequence

• 做该题前参考Leetcode 第306题Additive Number。306题是要返回True和False，这个是要求返回具体的一个例子。
• 该题discuss中的参考答案是利用backtracking回溯，类似于暴力求解来做的，它对于所有的切分都进行一次尝试，最后找到合适的切分，然后进行更深层次的递归。具体思路可以参看代码实现及注释。

10.（134:Medium）（非常非常经典题）Gas Station

• 感觉该题并不是一个典型的贪心算法题目。
• 非常经典的一道题。可以转换成求最大连续和做，但是有更简单的方法。基于一个数学定理：

如果一个数组的总和非负，那么一定可以找到一个起始位置，从他开始绕数组一圈，累加和一直都是非负的

（证明貌似不难，以后有时间再补）

有了这个定理，判断到底是否存在这样的解非常容易，只需要把全部的油耗情况计算出来看看是否大于等于0即可。

那么如何求开始位置在哪？

注意到这样一个现象：

1. 假如从位置i开始，i+1，i+2...，一路开过来一路油箱都没有空。说明什么？说明从i到i+1，i+2，...肯定是正积累。
2. 现在突然发现开往位置j时油箱空了。这说明什么？说明从位置i开始没法走完全程(废话)。那么，我们要从位置i+1开始重新尝试吗？不需要！为什么？因为前面已经知道，位置i肯定是正积累，那么，如果从位置i+1开始走更加没法走完全程了，因为没有位置i的正积累了。同理，也不用从i+2，i+3，...开始尝试。所以我们可以放心地从位置j+1开始尝试。

• 参考链接：中文博客

11.（765:Hard）（非常非常经典题）Couples Holding Hands

• 对于row[0]来说，如果row[1] 和 row[0]是夫妻，那么他们两个就都不动就好。如果两个都移走，那么不是最优。
• 考虑row[0]和row[1]不是夫妻的情况：操作1: 要么把row[0]和 row[0]的夫妻旁边的交换（0XXX1X->XXXX10）。操作2: 要么把row[1]和row[0]的夫妻交换（0XXX1X->01XXXX）。操作3：要么row[0]和row[1]都移走。显然操作3要不得，并不是最优化决策。此外，操作1和操作2显然是等价的，但为了方便处理，我们执行操作2。
• 那么"总的思路"：我们遍历row[0]，若row[1]和row[0]不是夫妻，则向后找到row[0]的夫妻并与row[1]交换；若row[0]和row[1]本身就是夫妻，直接跳过，处理row[2]。
• 这里使用一个"小技巧"：因为我们在遍历到row[i]时，无法确定其夫妻的编号是row[i]+1还是row[i]-1，所以我们一开始先对数组进行预处理，将数组中所有元素的值都除以2，因此，对于(2,3)->(1,1)，方便我们寻找匹配的夫妻。

上面的时间复杂度为O(N^2)，但是却beat 98%，不明白为什么

12.（757:Hard）（非常经典题）Set Intersection Size At Least Two

• 这道题给了我们一些区间，让我们求一个集合S，使得S和每个区间的交集至少为2，即至少有两个相同的数字。最开始分析题目中的例子的时候，以为要求的集合S也必须是一个连续的区间，其实不需要的，离散的数字就可以了。比如如果区间是[1,3], [5,6]的话，那么返回的集合长度是4，而不是5。这道题可以是用贪婪算法来解，一般来说Hard的题目能用贪婪算法而不是DP解的是少之又少，这道题为我大Greedy算法正名了～！为了使得集合S中的数字尽可能的小，我们希望处理区间的时候从小区间开始，如果区间b完全覆盖了区间a，那么和区间a有两个相同数字的集合，一定和区间b也有两个相同数字。同样，我们不希望一会处理一个前面的区间，一会又处理一个很后面的区间，我们希望区间是有序的。那么如何给区间排序呢，是按起始位置排，还是按结束位置排，这里我们按结束位置从小往大排，当两个结束位置相同时，起始位置大的排前面先处理，这也符合我们先处理小区间的原则。那么遍历区间的时候，当前区间就和我们维护的集合S有三种情况：

1. 二者完全没有交集，这时候我们就需要从当前区间中取出两个数字加入集合S，取哪两个数呢？为了尽可能少使用数字，我们取当前区间中的最大两个数字，因为我们区间位置不断变大，所以取大的数字有更高的概率能和后面的区间有交集。
2. 二者有一个数字的交集，那么这个交集数字一定是区间的起始位置，那么我们需要从当前区间中再取一个数字加入集合S，根据上面的分析，我们取最大的那个数，即区间的结束位置。
3. 二者有两个及两个以上数字的交集，那么不用做任何处理。

该题只有一个数字相交的情况逻辑比较绕，下次复习时最好再仔细琢磨一下，具体实现参看代码及注释

13.（330:Hard）（非常经典题）Patching Array

• 这是贪心算法的一个应用。举个例子，对于数组 [1, 2, 3, 8] ：

1. 用一个miss来表示当前缺失的数，初始时为1，num[0] = 1，它的覆盖范围为 [1, 1] ，可以补足miss = 1
2. 那么哪个数是num[0]达不到的呢？答案是：miss + nums[0] = 2。那么向数组申请一个新的数nums[1]，它们的覆盖范围为 [1, 3] 发现可以补足miss = 2。
3. 那么哪个数是它们两达不到的呢？答案是：miss + nums[1] = 4。那么向数组申请一个新的数nums[2]，它们的覆盖范围为 [1, 6] 发现3可以补足miss = 4
4. 那么哪个数是它们三达不到的呢？答案是：miss + nums[2] = 7。那么向数组申请一个新的数nums[3]，发现由于8大于7，因此miss要自己申请一个7，此时由于7的加入，覆盖范围变为了 [1, 13]
5. 那么下一个 [1, 2, 3, 7]达不到的呢？答案是：miss + miss(补丁7) = 14。由于8 < 14因此可以覆盖到14，且它们的覆盖范围变为[1, 21]

• 对于情况5，当前的miss由nums[0..i]的和不能构成，nums[0..i]的和最大为miss-1，现在将其加入到数组中，他们最大的和可能为2miss-1，2miss可能不能达到
• 依此思维类推进行实现，具体思路参看代码及注释

每次miss+nums[i]的原因还不是很懂，下次复习时与其他同学请教

14.（630:Hard）（非常非常经典题）Course Schedule III

• 该题直接贴代码，参考下边的注释：

public int scheduleCourse(int[][] courses) {
    //贪心策略，优先上截止日期早的课程
    Arrays.sort(courses,(a,b)->a[1]-b[1]); //Sort the courses by their deadlines (Greedy! We have to deal with courses with early deadlines first)
    PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->b-a);//用来存储已经上过的课，按课程时长大小降序排列
    int time=0;
    for (int[] c:courses) 
    {
       time+=c[0]; // add current course to a priority queue
       pq.add(c[0]);
       //这里是用if而不是while，原因是，在上一轮循环结束时，time一定是小于当前的c[1]的，那么此时如果上了c课程，则会超过c的截止日期。于是此时的选择
       //是：从pq中删去课程时长最长的课程。这个持续时间最长的课程有两种情：1.一种是之前上过的课程中有比c的持续时间更长的课，我们将其drop掉 2.当前的
       //c课程持续时间就是最长的，那么我们只好放弃这门课。无论是哪种情况，均会保证time再次符合条件（这也是一种贪心策略）
       if (time>c[1]) time-=pq.poll(); //If time exceeds, drop the previous course which costs the most time. (That must be the best choice!)
    }        
    return pq.size();
}

15.（135:Hard）（非常经典题）Candy

• 该题本质上来讲还是比较简单的，只需要在处理时，保证rating高的小孩可以获得比他相邻小孩更多的candies即可。但需要注意的是，ratings数组存在升序片段和降序片段，我们单方向(从左到右)进行遍历时，只能正确处理升序的序列，对于降序的序列，如ratings = [1,2,87,87,87,2,1]，我们分法candies的数组为candies = [1,2,3, 1, "2", 2,1],总共分发12个candies，但实际上应该是13个。原因在于，倒数第二个小孩candies在加1时，给倒数第三个小孩的candies也应该加1，但因为我们此时已经扫描结束指针移动到倒数第二个元素，所以此时无法对倒数第三个元素进行处理，因而会出现错误。解决办法是，我们从左到右和从右到左扫描两次，单方向的扫描只能正确处理对应方向的升序序列，因而扫描两次即可处理正方向的升序及降序序列了。

16.（321:Hard）（非常经典题）Create Maximum Number

• 该题之接参看教程和discuss，理解后思路比较简单，但实现有些复杂。
• 参考链接：花花讲解

下次复习时需要仔细研究实现细节

17.（1057:Medium）（非常非常经典题）Campus Bikes

• As the question states, there are n workers and m bikes, and m > n. We are able to solve this question using a greedy approach.

1. initiate a priority queue of bike and worker pairs. The heap order should be Distance ASC, WorkerIndex ASC, Bike ASC，这个是按照题目里的描述，进行break tie时进行比较的优先级设定
2. Loop through all workers and bikes, calculate their distance, and then throw it to the priority queue (很粗鲁的解决方式).
3. Initiate a set to keep track of the bikes that have been assigned.
4. initiate a result array and fill it with -1. (unassigned)
5. poll every possible pair from the priority queue and check if the person already got his bike or the bike has been assigned.
6. early exist on every people got their bike.

• 上面的解法可能并不是最高效的，有待进一步的学习研究

18.（1094:Medium）（非常非常经典题）Car Pooling

• 很经典的一个思路，只需要在起点和终点两个端点位置记录人数变化即可，因为之后从左往右遍历是人数进行累加

public boolean carPooling(int[][] trips, int capacity) {
    int stops[] = new int[1001];
    for (int t[] : trips) {  //只需要在起点和终点两个端点位置记录人数变化即可，因为之后从左往右遍历是人数进行累加
        stops[t[1]] += t[0];
        stops[t[2]] -= t[0];
    }
    for (int i = 0; capacity >= 0 && i < 1001; ++i) capacity -= stops[i];
    return capacity >= 0;
}

19.（1005:Easy）（经典题）Maximize Sum Of Array After K Negations

• 永远操作的都是当前的最小值，这样可以保证对和的变化最小

public int largestSumAfterKNegations(int[] A, int K) {
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        
    for(int x: A) pq.add(x);
    while( K--  > 0) pq.add(-pq.poll());   //永远操作的都是当前的最小值，这样可以保证对和的变化最小

    int sum  = 0;
    for(int i = 0; i < A.length; i++){
        sum += pq.poll();
    }
    return sum;
}