当前位置:   article > 正文

一文搞懂贪心算法,上机考试再也不会慌_贪心算法飞行问题,d[i]表示距离出发点的距离,每次最多飞k公里,d[i]–d[i–1]<

贪心算法飞行问题,d[i]表示距离出发点的距离,每次最多飞k公里,d[i]–d[i–1]<

一、前言

二、贪心及其解题步骤

2.1 认识贪心

贪心的本质是选择每一阶段的局部最优,从而达到全局最优。

1、无限制条件:可以无条件限制的执行局部最优;
2、无数次:可以执行无数次的局部最优。

只要同时满足这两个条件,就可以用贪心算法了。

这么说有点抽象,来举一个例子:有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?指定每次拿最大的,最终结果就是拿走最大数额的钱。每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。

再举一个例子:如果是 有一堆盒子,你有一个背包体积为n,如何把背包尽可能装满,如果还每次选最大的盒子,就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。

2.2 贪心的套路(什么时候用贪心)

问题:做贪心的题目的时候,想不出来是贪心,想知道有没有什么套路可以一看就知道这个题目是贪心。
回答:没有,贪心算法并没有固定的套路。所以唯一的难点就是如何通过局部最优,推出整体最优。

问题:那么如何能看出局部最优是否能推出整体最优呢?有没有什么固定策略或者套路呢?
回答:没有!靠自己手动模拟,如果模拟可行,就可以试一试贪心策略,如果不可行,可能需要动态规划。

问题:如何验证可不可以用贪心算法呢?
回答:最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧。

问题:贪心得到的最优解有理论依据吗?如何证明是最优的,严格的数学证明吗?
回答:一般没有。一般数学证明有如下两种方法:(1 )数学归纳法 (2) 反证法。面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了。

举一个不太恰当的例子:我要使用 “1+1 = 2”,但我要先证明1+1 为什么等于2。严谨是严谨了,但没必要。虽然这个例子很极端,但可以表达这么个意思:刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心。例如刚刚举的拿钞票的例子,就是模拟一下每次拿做大的,最后就能拿到最多的钱,这还要数学证明的话,其实就不在算法面试的范围内了,可以看看专业的数学书籍!

很多时候,我们通过(accept)了贪心的题目,但都不知道自己用了贪心算法,因为贪心大多数时候就是常识性的推导,所以会认为本应该就这么做,即贪心一般不需要数学推导。

2.3 贪心一般解题步骤

贪心算法一般分为如下四步:

(1) 将问题分解为若干个子问题
(2) 找出适合的贪心策略
(3) 求解每一个子问题的最优解
(4) 将局部最优解堆叠成全局最优解

其实这个分的有点细了,真正做题的时候很难分出这么详细的解题步骤,可能就是因为贪心的题目往往还和其他方面的知识混在一起。

三、分发饼干 + 摆动序列最长长度 + 最大序列和

3.1 分发饼干

题目链接:455. 分发饼干

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干(关键,显示条件说出来了,一个饼干只能一个孩子,这是隐性条件,没必要说出来)。

  1. 对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;
  2. 对于每块饼干 j,都有一个尺寸 s[j] 。
  3. 如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值(int)。

孩子数组g,饼干数组s

贪心问题注意两点:
第一,贪心问题就是资源分配给人的问题,这里核心,一个饼干不可以分给多个孩子(所以一定要避免浪费),同时一个孩子只能吃一个饼干
第二,从题目中提取出局部最优和全局最优
局部最优:大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个
全局最优:喂饱尽可能多的小孩
贪心问题中,题目答案需要的全局最优,但是解题思路只能给出局部最优的算法,所以,要保证这个局部最优的是可以满足的全局最优的(即不能举出反例),这里就是每个饼干(资源)被浪费的量最少
因为一个饼干只能分配给一个孩子,然后大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子,那么就应该优先满足胃口大的。
不这样就会危险:第一,大饼干给小胃口可以,但是小饼干给大胃口不一定能满足,存在危险。
这样是安全的(无法举出反例):如果饼干都可以满足的孩子胃口,那么给大胃口的孩子还是给小胃口的孩子是一样的,因为最后要得到的只是孩子的总数而已。

对于对两个数组排序,然后逐一比较值就好

为了了满足更多的小孩,就不要造成饼干尺寸的浪费。

可以尝试使用贪心策略,先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。

代码:

// 时间复杂度:O(nlogn)
// 空间复杂度:O(1)

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if (g == null && g.length == 0) return 0;  // 没有孩子,就是0
        Arrays.sort(g);
        Arrays.sort(s);
        int result = 0;  // 一开始还没满足一个孩子,所以为result为零
        int index = s.length-1; // 饼干也是从大的开始
        for (int i = g.length-1; i >= 0; i--) {  // 孩子从大到小开始,如果最大的饼干也不能满足某个孩子,就放弃这个孩子,将最大的饼干给第二胃口的孩子,还是满足的不了就再下一个
            if (index>=0){
             if (s[index]>=g[i]){  // 饼干满足孩子,那么计数器加一,然后饼干先前面移动,因为当前饼干已经被使用了
                result++;
                index--;
             }
            }
        }
        return result;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

关键:从饼干的角度考虑,对孩子for循环,如果最大的饼干喂不饱最大的孩子,就放弃这个孩子,就放弃这个孩子,孩子i–不断执行,只有满足条件才执行饼干index–

从孩子的角度来考虑,就会优先考虑小胃口的孩子,小饼干不一定能满足孩子,所以小饼干做for循环,如果最小的饼干不能满足最小的孩子,就放弃这个饼干,i++不断执行,孩子作为if判断

代码如下:

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if (g == null && g.length == 0) return 0;  // 没有孩子,就是0
        Arrays.sort(g);
        Arrays.sort(s);
        int result = 0;  // 一开始还没满足一个孩子,所以为result为零
        int index = 0;
        for (int i = 0; i < s.length; i++) {  // 小饼干不一定能满足孩子胃口,所以饼干的i要不断循环
            if (index < g.length) {
                if (s[i] >= g[index]) {      // 饼干大于孩子
                    result++;
                    index++; // 孩子拿到饼干,所以孩子移动了
                }
            }
        }
        return result;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

不写两个循环,写两个循环就是 O(n^2) 的时间复杂度了。

核心1:从小到大遍历饼干,小饼干不一定能满足孩子胃口,所以饼干的i要不断循环
核心2:从大到小遍历孩子,如果最大的饼干也不能满足某个孩子,就放弃这个孩子,将最大的饼干给第二胃口的孩子,还是满足的不了就再下一个

3.2 摆动序列

题目链接:376. 摆动序列

「局部最优:删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值」。
「整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列」。
局部最优推出全局最优,并举不出反例,那么试试贪心!

class Solution {
    public int wiggleMaxLength(int[] nums) {
       if (nums.length<=1) return nums.length;
       int preDiff=0;
       int curDiff=0;
       int result=1; // 长度为2,即使是两个数字相等,子序列长度也有一个
        for (int i=1;i<nums.length;i++){
            curDiff = nums[i]-nums[i-1];
            // 核心:和数学上的单调性一下,大于左边且小于右边,或,小于左边且大于右边
            if ((curDiff<0 && preDiff>=0) || (curDiff>0 && preDiff<=0)  ){  // 长度为2,即使是两个数字不等,子序列长度为2
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

摆动子序列的局部最优和全局最优:
核心:和数学上的单调性一下,大于左边且小于右边,或,小于左边且大于右边

问题:为什么preDiff可以用等于号?

3.3 最大子序和

题目链接:53. 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        // 从最大的整数开始
        int result=Integer.MIN_VALUE;   // 这里不要写0,如果nums中仅一个负数,这个负数可以不断小
        int sum=0;
        for (int i=0;i<nums.length;i++){  // [0,n-1]
            sum = sum + nums[i];
            if (sum > result){
                result =  sum; // 遇到更大的就更新
            }
            if (sum < 0 )sum=0;  // 变成了负数就马上设置为0,因为sum的初始化就是从0开始的
        }
        return result;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

最大序列和关键在于两个条件:
第一个条件,要取出最大序列和,所以 sum>result,就用result=sum;
第二个条件,因为sum初始化从0开始,所以当一段序列和变为负数了马上抛弃,继续将sum初始为0,从新开始技术,这就是局部最优和全局最优的联系。
即:只要目前sum还是正的,就可以继续累加上去,要是sum>result,就更新下result,但是一旦sum变成了负的,就要抛弃前面的子序列,重新开始。

四、跳跃游戏 + K 次取反后最大化的数组和

4.1 跳跃游戏

题目链接:55. 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
      if (nums.length<=1) return true;
      int distance=0;
      for (int i=0;i<=distance;i++){
          distance = Math.max(distance,i+nums[i]);
          if (distance>=nums.length-1) return true;
      }
      return false;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

核心(用局部最优模拟全局最优)
第一,如果长度为0或者为1,直接true,就算是唯一元素是0也是true,也可以达到本身。
第二,核心:i从0开始,在长度范围内(所以是<=distance,带等于号),不断更新最长的可以达到的值,到distance遍历结束还无法达到 nums.length-1,就是return false,中间某一次可以达到就是return true。
注意:都是以数组下标为计算的,所以开始i=0,最后是i>=nums.length-1 带等于号,因为distance大于1,所以不能用 i==nums.length-1 等于号

4.2 跳跃游戏II

题目链接:45. 跳跃游戏 II

class Solution {
    public int jump(int[] nums) {
      if (nums.length<=1) return 0;  // 长度为0和为1,都是返回0
      int currentDistance=0;
      int nextDistance=0;
      int ans=0;
      for (int i=0;i<nums.length;i++){  // 下标从0到n-1
          nextDistance = Math.max(nums[i]+i,nextDistance);
          if (i==currentDistance){  // i已经达到currentDistance,且i尚未达到nums.length-1
              if (i<nums.length-1){   // 这样代码可以修改成 i<nums.length-1
                  ans++;
                  currentDistance = nextDistance;
                  if (nextDistance >= nums.length-1) break;
              }else break;
          }
      }
      return ans;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

简化

if (currentDistance >= nums.length-1) break; 表示如果下一步就可以达到终点,现在currentDistance = nextDistance,就是当前步可以达到终点 代码可以改为 currentDistance >= nums.length-1
其实,这一句是一个剪枝简化算法,去掉也可以,
情况一:不去掉, currentDistance >= nums.length-1 之间返回ans
情况二:去掉,因为此时 currentDistance >= nums.length-1,所以下一次无法满足if(i==currentDistance),ans++,再也不会执行,最后还是返回ans

class Solution {
    public int jump(int[] nums) {
      if (nums.length<=1) return 0;  // 长度为0和为1,都是返回0
      int currentDistance=0;
      int nextDistance=0;
      int ans=0;
      for (int i=0;i<nums.length;i++){  // 下标从0到n-1
          nextDistance = Math.max(nums[i]+i,nextDistance);
          if (i==currentDistance){  // i已经达到currentDistance,且i尚未达到nums.length-1
              if (i<nums.length-1){   // 这样代码可以修改成 i<nums.length-1
                  ans++;
                  currentDistance = nextDistance;
              }else break;
          }
      }
      return ans;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

进一步简化,再去掉一个if…else…

将for循环修改为从0到n-2,因为 i 从0到n-2,一定满足i<nums.length-1,去掉if…else

class Solution {
    public int jump(int[] nums) {
      if (nums.length<=1) return 0;  // 长度为0和为1,都是返回0
      int currentDistance=0;
      int nextDistance=0;
      int ans=0;
      for (int i=0;i<nums.length-1;i++){  // 下标从0到n-1
          nextDistance = Math.max(nums[i]+i,nextDistance);
          if (i==currentDistance){  // i已经达到currentDistance,且i尚未达到nums.length-1
                  ans++;
                  currentDistance = nextDistance;
          }
      }
      return ans;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

核心(用局部最优模拟全局最优)
第一,如果长度为0或者为1,直接true,就算是唯一元素是0也是true,也可以达到本身。
第二,核心:i从0开始,不断更新nextDistance,如果 i==currentDistance ,而且 i<nums.length-1 ,表示尚未达到最终点(达到最终点就return ans),就ans++,currentDistance=nextDistance,如果此时,被更新后的currentDistance>=nums.length-1,就直接return ans。

注意:都是以数组下标为计算的,所以开始i=0,最后是i>=nums.length-1 带等于号,因为distance大于1,所以不能用 i==nums.length-1 等于号

4.3 K 次取反后最大化的数组和

题目链接:1005. K 次取反后最大化的数组和

class MyComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer a, Integer b) {   // 绝对值从大到小排序
        if (Math.abs(a) > Math.abs( b)){   // 
            return -1;
        }
        if (Math.abs( a) < Math.abs( b)){  // 返回1,交换位置 
            return 1;
        }
        return 0;
    }
}
class Solution {
    public  int largestSumAfterKNegations(int[] A, int K) {
        Comparator myComparator=new MyComparator();
        Integer[] AA = new Integer[A.length];
        for(int i=0;i<A.length;i++){
            AA[i]= new Integer(A[i]);
        }

        Arrays.sort(AA, myComparator);// 因为>是返回true,所以这里是按绝对值从大到小排序
        for (int i = 0; i < AA.length; i++) {
            if (AA[i] < 0 && K>0) {
                K--;
                AA[i] = -AA[i];
            }
        }
        while (K > 0) {
            AA[AA.length - 1] = -AA[AA.length - 1];  // 剩余的次数都作用到绝对值最小的那个元素,即最后一个元素身上
            K--;
        }
        // 累加
        int result = 0;
        for (int i = 0; i < AA.length; i++) {
            result = result + AA[i];
        }
        return result;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

return 0:不交换位置,不排序
return 1:交换位置
return -1:负数,正标,不交换位置

return o1-o2:升序排列
大于0:如果 o1>o2,那就要反转过来,较小的o2放在前面,所以是升序排列;
小于0:如果 o1(前面)<o2(后面),那就不动,较大的o2还是在后面,较小的o1还是在前面,所以是升序
return o2-o1:降序排列
大于0:如果 o2(后面)>o1(前面),那就要反转过来,较大的o2放在前面,所以是降序排列
小于0:如果 o2<o1,那就不动,较小o2放在后面,较大的o1还是在前面,所以降序;

这里注意,Compator泛型可以接受int[] Integer[] Integer,但是不能接受int
List泛型也是这样,所以这里只能用 Compator<Integer> 不能用 Compator<int>

五、 加油站问题 + 找零问题 + 根据身高重建队列

5.1 加油站

题目链接:134. 加油站

核心:把负掉的累计值都正向加回来,就返回此时对应的数组下标

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
       int curNum=0;
       int min = Integer.MAX_VALUE;
       for (int i=0;i<gas.length;i++){
           int save = gas[i]-cost[i];
           curNum = curNum + save;
           if ( curNum < min)
               min = curNum;   // min记录一个最小的curNum
       }
       if (curNum <0) return -1;
       if (min >= 0) return 0;
        // min < 0
       for (int i= gas.length-1;i>=0;i--){  // 从后往前来,因为默认车子行进是一个方向
           int save = gas[i] - cost[i];  
           min = min + save;    // 因为上面,min记录了一个最小的curNum
           if (min >=0 )  // 解释:下标就是可以开始下标,题目假定只有一个确定答案
               return i;
       }
       return -1;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

时间复杂度:O(n)
空间复杂度:O(1)

5.2 柠檬水找零

题目链接:860.柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five=0;
        int ten=0;
        for (int each : bills){
            if (each==5){
                five++;
                continue;
            }
            if (each==10){
                if (five<1) return false;
                five--;
                ten++;
                continue;
            }
            if (each==20){
                if (five>=1 && ten>=1){   //这种情况一定要写在前面,优先使用ten+five,而不是三个five,要不然可能某些可以的情况就不可以了
                    five--;
                    ten--;
                    continue;
                }
                if (five>=3){
                    five=five-3;
                    continue;
                }
                return false;
            }
        }
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

5.3 根据身高重建队列

题目链接:406.根据身高重建队列

身高从大到小降序排列,身高相同k从小到大升序排列

class MyCompator implements  Comparator<int[]>{
    @Override
    public int compare(int[] o1, int[] o2) {
        if (o1[0] == o2[0]){
            // 降序排列  大的放在前面
            if (o1[1] > o2[1]){
                return 1;  // 改变
            }
            if (o1[1] < o2[1]){
                return -1;  // 不改变
            }
            return 0;
        }
        if (o1[0] > o2[0]){
            return -1;  // 不改变
        }
        if (o1[0] < o2[0]){
            return 1;  // 改变
        }
        return 0;
    }
}
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Comparator comparator=new MyCompator();
        Arrays.sort(people,comparator);  //
        List<int[]> queue=new ArrayList<>();
        for (int i=0;i<people.length;i++){
            int position=people[i][1];  // 取出二维数组,peopleNew每个元素的第二个维度,表示queue要插入的位置
            queue.add(position,people[i]);
        }
        return  queue.toArray(new int[queue.size()][]);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

如果Compator泛型是Integer,一定要输入Integer数组或Integer;
如果Compator泛型是int,一定要输入int数组或int。

这里注意,Compator泛型可以接受int[] Integer[] Integer,但是不能接受int
List泛型也是这样,所以这里可以用 Compator<int[]>

List<int[]> queue=new ArrayList<>();
而不是 int[][] queue=new int[][]; 因为add插在中间,原有位置的元素会向后面移动,但是数组会直接覆盖

class MyCompator implements  Comparator<int[]>{
    @Override
    public int compare(int[] o1, int[] o2) {
        if (o1[0] == o2[0]){
            // 升序排列
            return o1[1] - o2[1];
        }
        // 降序排列
        return o2[0] - o1[0];
    }
}
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Comparator comparator=new MyCompator();
        Arrays.sort(people,comparator);
        List<int[]> queue=new ArrayList<>();
        for (int i=0;i<people.length;i++){
            int position=people[i][1];  // 取出二维数组,peopleNew每个元素的第二个维度,表示queue要插入的位置
            queue.add(position,people[i]);
        }
        return  queue.toArray(new int[queue.size()][]);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

继续简化,compator不要单独列出一个类来

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]){
                    // 升序排列
                    return o1[1] - o2[1];
                }
                // 降序排列
                return o2[0] - o1[0];
            }
        });
        List<int[]> queue=new ArrayList<>();
        for (int i=0;i<people.length;i++){
            int position=people[i][1];  // 取出二维数组,peopleNew每个元素的第二个维度,表示queue要插入的位置
            queue.add(position,people[i]);
        }
        return  queue.toArray(new int[queue.size()][]);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

5.3.1 为什么k一定要升序排列?

因为k代表这个元素插入到list的下标,所以当然是从前插到后,list不像数组,add()不能先插后面的,除非queue改成数组

这是一个错误程序,k降序排列,list指定位置add无法跳跃add

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]){
                    // 这里降序排列应该也没什么关系,就失败相同身高要先插入后面的,list要确定容量,否则size=0,index=1
                    return o2[1] - o1[1];
                }
                // 降序排列
                return o2[0] - o1[0];
            }
        });
        List<int[]> queue=new ArrayList<>(people.length);   // 初始化的时候peope.length,这样也不行
        for (int i=0;i<people.length;i++){
            int position=people[i][1];  // 取出二维数组,peopleNew每个元素的第二个维度,表示queue要插入的位置
            queue.add(position,people[i]);
        }
        return  queue.toArray(new int[queue.size()][]);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

将queue改成数组 用begin变量做一个偏移量,防止覆盖还要移动元素,太难了,不讨论了

5.3.2 为什么h一定要降序排列?

因为k这个维度表示的是,比当前元素大的前面有多少个,

如果h升序排列,先插入小的,

第一,小元素的k,大概率比大元素的k要大,而k代表插入的下标位置,list add()无法先插入后面的元素,会报错;

第二,会出现先插入[5,0],然后插入[7,0],就是[7,0]在[5,0]前面,所以[5,0]是错的,所以一定要先插入大元素(就是h更大的元素,身高更大的元素,按身高降序排列)

六、区间问题(右边界总是大于左边界-隐含条件)

1、贪心问题比较复杂,leetcode都是中等起步;
2、贪心问题都是 贪心要求+硬性要求 构成题目总要求。

6.1 用最少数量的箭引爆气球

题目链接:452. 用最少数量的箭引爆气球

局部最优:当气球出现重叠,一起射,所用弓箭最少。
全局最优:把所有气球射爆所用弓箭最少。
核心:就是找范围的交集

6.1.1 解法一:左边界升序排序,从左到右覆盖

class Solution {
    public int findMinArrowShots(int[][] points) {
      if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] > o2[0] ? 1: -1;  // 升序
            }
        });
      int arrow=1;
      for (int i=1;i<points.length;i++){  // 从【1,length-1】   下面只能出现i-1和i,不能出现i+1
          if (points[i-1][1] < points[i][0])
              arrow++;
          else{  // 小于等于  取出  points[i-1][1] >=  points[i][0]
              // 更改了元素  i++之后,point[i][1]就是上面比较的points[i-1][1]
              points[i][1] = Math.min(points[i-1][1],points[i][1]);
          }
      }
      return arrow;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

在java里面,int a = -2147483646 - 2147483646 = 4,不会为负数,所以不能用 减号return o1[0]-o2[0];
只能用 > < == return o1[0] > o2[0] ? 1: -1;

else块中的核心: points[i][1] = Math.min(points[i-1][1],points[i][1]);
1、因为已经按左边界升序排列,所以i++,每次左边界都会增加,右边界取当前的比较的两个区段中的min,就得到了交集;
2、i++ 之后,points[i-1][1] 就是指当前else块中更新的 points[i][1]

6.1.2 解法二:左边界升序排序,从右到左覆盖

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] > o2[0] ? 1: -1;  // 升序
            }
        });
        int arrow=1;
        for (int i=points.length-2;i>=0;i--){  // 从【1,length-1】   下面只能出现i-1和i,不能出现i+1
            if (points[i][1] < points[i+1][0])
                arrow++;
            else{ 
                points[i][0] = Math.max(points[i][0],points[i+1][0]);
            }
        }
        return arrow;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

左边界已经升序排列,要取max,直接取后面那个就好了

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] > o2[0] ? 1: -1;  // 升序
            }
        });
        int arrow=1;
        for (int i=points.length-2;i>=0;i--){  // 从【1,length-1】   下面只能出现i-1和i,不能出现i+1
            if (points[i][1] < points[i+1][0])
                arrow++;
            else{ 
                points[i][0] = points[i+1][0];  // 左边界已经排序,所以直接赋值就好了
            }
        }
        return arrow;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

else块中的核心: points[i][0] = Math.max(points[i][0],points[i+1][0]);
1、因为已经按左边界升序排列,所以i–,每次左边界都会减少,左边界取当前的比较的两个区段中的max,就得到了交集(其实,左边界已经排序,所以直接赋值就好了);
2、i-- 之后,points[i+1][0] 就是指当前else块中更新的 points[i][0]

6.1.3 解法三:右边界降序排序,从右往左覆盖

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] < o2[1] ? 1: -1;  // 右边界降序排序
            }
        });
        int arrow=1;
        for (int i=1;i<points.length;i++){  // 从【1,length-1】   下面只能出现i-1和i,不能出现i+1
            if (points[i-1][0] > points[i][1])  // i-1左边界更大
                arrow++;
            else{  // 小于等于  取出  points[i-1][1] >=  points[i][0]
                // 更改了元素  i++之后,point[i][1]就是上面比较的points[i-1][1]
                points[i][0] = Math.max(points[i-1][0],points[i][0]);
            }
        }
        return arrow;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

else块中的核心: points[i][0] = Math.max(points[i-1][0],points[i][0]);
1、因为已经按右边界降序排列,所以i++,每次右边界都会减少,左边界取当前的比较的两个区段中的max,就得到了交集;
2、i-- 之后,points[i-1][0] 就是指当前else块中更新的 points[i][0]

6.1.4 解法四:右边界降序排序,从左往右覆盖(两次反转,从“解法一”一样了)

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] < o2[1] ? 1: -1;  // 右边界降序排列
            }
        });
        int arrow=1;
        for (int i=points.length-2;i>=0;i--){  // 从【1,length-1】   下面只能出现i-1和i,不能出现i+1
            if (points[i+1][1] < points[i][0])
                arrow++;
            else{  // 小于等于  取出  points[i-1][1] >=  points[i][0]
                // 更改了元素  i++之后,point[i][1]就是上面比较的points[i-1][1]
                points[i][1] = Math.min(points[i][1],points[i+1][1]);
            }
        }
        return arrow;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

右边界已经降序,取min就去后面那个就好了,直接赋值就行

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length==0) return 0;
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] < o2[1] ? 1: -1;  // 右边界降序排列
            }
        });
        int arrow=1;
        for (int i=points.length-2;i>=0;i--){  // 从【1,length-1】   下面只能出现i-1和i,不能出现i+1
            if (points[i+1][1] < points[i][0])
                arrow++;
            else{  // 小于等于  取出  points[i-1][1] >=  points[i][0]
                // 更改了元素  i++之后,point[i][1]就是上面比较的points[i-1][1]
                points[i][1] = points[i+1][1];
            }
        }
        return arrow;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

else块中的核心: points[i][1] = Math.min(points[i][1],points[i+1][1]);
1、因为已经按右边界降序排列,所以i–,每次右边界都会增加,右边界取当前的比较的两个区段中的min,就得到了交集(其实,右边界已经排序,所以直接赋值就好了);
2、i-- 之后,points[i+1][1] 就是指当前else块中更新的 points[i][1]

6.2 无重叠区间

题目链接:435. 无重叠区间

给定一个区间的集合,找到需要移除区间的最小数量(贪心要求)使剩余区间互不重叠(目的)

注意1:右边界永远大于左边界;
注意2:区间 [1,2] 和 [2,3] 的边界相互“接触”,不算重叠。

按右边界排序之后,局部最优:优先选右边界小的区间,所以从左向右遍历,留给下一个区间的空间大一些,从而尽量避免交叉。全局最优:选取最多的非交叉区间(即最小的删除原有区间)。

6.2.1 解法一:右边界升序排列,从左向右遍历

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length==0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] < o2[1] ? -1:1; // 有边界升序排列,不要用减号
            }
        });
        int count=1; // 非重叠区间初始化为1
        int end=intervals[0][1]; // 第一个元素是有边界
        for (int i=1;i<intervals.length;i++){  // 遍历整个
            if (intervals[i][0] >= end){ //大于不是重叠,等于也不是重叠
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.length - count;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

6.2.2 解法二:左边界升序排列,从右向左遍历

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length==0) return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] < o2[0] ? -1:1; // 左边界升序排列,不要用减号
            }
        });
        int count=1; // 非重叠区间初始化为1
        int start=intervals[intervals.length-1][0]; // 从最后一个元素(左边界最大的元素)开始
        for (int i=intervals.length-2;i>=0;i--){  // 遍历整个
            if (intervals[i][1] <= start){ //大于不是重叠,等于也不是重叠    某个的右边界小于这个start了,覆盖不了了,非重叠区域加一
                start = intervals[i][0];
                count++;
            }
        }
        return intervals.length - count;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

七、单调递增的数字 + 划分字母区间 + 合并线段区间

7.1 单调递增的数字

题目链接:738.单调递增的数字

给定一个非负整数 N,找出小于或等于 N 的最大的整数(贪心要求),同时这个整数需要满足其各个位数上的数字是单调递增(硬性要求)

(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。)

题目要求小于等于N的最大单调递增的整数,那么拿一个两位的数字来举例。

例如:98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]–,然后strNum[i]给为9,这样这个整数就是89,即小于98的最大的单调递增整数。

这一点如果想清楚了,这道题就好办了。

局部最优:遇到strNum[i - 1] > strNum[i]的情况,让strNum[i - 1]–,然后strNum[i]给为9,可以保证这两位变成最大单调递增整数。

全局最优:得到小于等于N的最大单调递增的整数。

但这里局部最优推出全局最优,还需要其他条件,即遍历顺序,和标记从哪一位开始统一改成9。

此时是从前向后遍历还是从后向前遍历呢?

从前向后遍历的话,遇到strNum[i - 1] > strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能又小于strNum[i - 2]。

这么说有点抽象,举个例子,数字:332,从前向后遍历的话,那么就把变成了329,此时2又小于了第一位的3了,真正的结果应该是299。

所以从前后向遍历会改变已经遍历过的结果!

那么从后向前遍历,就可以重复利用上次比较得出的结果了,从后向前遍历332的数值变化为:332 -> 329 -> 299

确定了遍历顺序之后,那么此时局部最优就可以推出全局,找不出反例,试试贪心。

class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] charArray = (N + "").toCharArray();  // int变为String
        int flag = charArray.length;  // 如果没有进入第一个循环的if块,第二个循环不需要执行
        for (int i = charArray.length - 1; i >= 1; i--) {  // 下面使用到了 i i-1,所以从[1,length-1]
            if (charArray[i - 1] > charArray[i]) {  // 硬性要求是小于或等于,大于就不行
                flag = i;  // 低位要全部变为9,不是仅这个i的位置要变为9
                charArray[i - 1]--;   // 高位要减少一
            }
        }
        for (int i = flag; i < charArray.length; i++) {
            charArray[i] = '9';
        }
        return Integer.parseInt(new String(charArray));
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

7.2 划分字母区间

题目链接:763.划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段(贪心目的)同一字母最多出现在一个片段中(硬性要求)。返回一个表示每个字符串片段的长度的列表。

遍历的过程相当于是要找每一个字母的边界,「如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了」。此时前面出现过所有字母,最远也就到这个边界了。

可以分为如下两步:

1、统计每一个字符最后出现的位置;
2、从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点。

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> result=new ArrayList<>();   // 里面存放长度
        if (S==null || S.length()<=1) return result;
        char[] charArray=S.toCharArray();
        int[] hash=new int[27];
        
        for (int i=0;i<S.length();i++)
            hash[charArray[i]-'a']=i;  // 如果一个字母在后面又出现了,后面的i会覆盖前面的,所以hash数组记录的就是每个字母最后出现的下标位置了
        // 再遍历一次S字符串,因为要对其拆分
        int right=0;
        int left=0;
        for (int i=0;i<S.length();i++){
            right=Math.max(right,hash[charArray[i]-'a']);   // 取一个比较大的
            if (i == right){
                // 找到位置了,就要拆分
                result.add(right-left+1);   
                left=right+1; // 此时i==right 所以left=i+1也是一样的
            }
        }
        return result;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

7.3 合并区间

题目链接:56. 合并区间

给出一个区间的集合,请合并所有重叠的区间。

那么我按照左边界排序
排序之后局部最优:每次合并都取最大的右边界,这样就可以合并更多的区间了,
整体最优:合并所有重叠的区间。

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length<=1) return intervals;  // 长度为0或者长度为1,都可以直接返回
        List<int[]> result=new ArrayList<>();
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];  // 升序排列   相等的时候是否交换无所谓
            }
        });
       boolean isFinished=false; // 没完成
        for (int i=1;i<intervals.length;i++){
            int start=intervals[i-1][0];
            int end=intervals[i-1][1];
            while (i<intervals.length && intervals[i][0] <= end){  // 等于也算重叠,也要合并
                end = Math.max(end,intervals[i][1]);   // 第一个元素和第二个元素取取出大的为end,然后i++,和第三个元素的[i][0]比较
                if (i==intervals.length-1) isFinished=true;
                i++;
            }
            result.add(new int[]{start,end});
        }
        if (!isFinished){
            result.add(new int[]{intervals[intervals.length-1][0],intervals[intervals.length-1][1]});
        }
        return result.toArray(new int[result.size()][]);  // 这里是result.size() 不是intervals.length
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

简化

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length<=1) return intervals;  // 长度为0或者长度为1,都可以直接返回
        List<int[]> result=new ArrayList<>();
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];  // 升序排列   相等的时候是否交换无所谓
            }
        });
        result.add(new int[]{intervals[0][0],intervals[0][1]});  // 第一个先放进去
        for (int i=1;i<intervals.length;i++){
//            int start=intervals[i-1][0];
//            int end=intervals[i-1][1];
//            while (i<intervals.length && intervals[i][0] <= end){  // 等于也算重叠,也要合并
//                end = Math.max(end,intervals[i][1]);   // 第一个元素和第二个元素取取出大的为end,然后i++,和第三个元素的[i][0]比较
//                i++;
//            }
//            result.add(new int[]{start,end});
            int[] lastElement = result.get(result.size()-1);
            if (lastElement[1] >= intervals[i][0]){  // 大于和等于都算重叠,都要合并
                // 重新设置这个元素的end   list无法修改,只能先删除,后新增,删除前记得将需要的暂存下来
                int start=lastElement[0];
                result.remove(result.size()-1);  // 删除最后一个元素,可以这样写
                result.add(new int[]{start,Math.max(lastElement[1],intervals[i][1])});  // 直接赋值,不用Math.max了
            }else{
                result.add(intervals[i]);
            }
        }
        return result.toArray(new int[result.size()][]);  // 这里是result.size() 不是intervals.length
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

就是

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length<=1) return intervals;  // 长度为0或者长度为1,都可以直接返回
        List<int[]> result=new ArrayList<>();
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];  // 升序排列   相等的时候是否交换无所谓
            }
        });
        result.add(new int[]{intervals[0][0],intervals[0][1]});  // 第一个先放进去
        for (int i=1;i<intervals.length;i++){
            int[] lastElement = result.get(result.size()-1);
            if (lastElement[1] >= intervals[i][0]){  // 大于和等于都算重叠,都要合并
                // 重新设置这个元素的end   list无法修改,只能先删除,后新增,删除前记得将需要的暂存下来
                int start=lastElement[0];
                result.remove(result.size()-1);  // 删除最后一个元素,可以这样写
                result.add(new int[]{start,Math.max(lastElement[1],intervals[i][1])});  // 直接赋值,不用Math.max了
            }else{
                result.add(intervals[i]);
            }
        }
        return result.toArray(new int[result.size()][]);  // 这里是result.size() 不是intervals.length
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

八、尾声

一文搞懂贪心算法,上机考试再也不会慌,完成了。

天天打码,天天进步!!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/煮酒与君饮/article/detail/897513
推荐阅读
相关标签
  

闽ICP备14008679号