贪心算法

1 贪心算法

1.1 简介

• 贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。也就是说，不从整体最优上加以考虑，做出的只是在某种意义上的局部最优解。
• 注意
  • 贪心算法不是对所有问题都能得到整体最优解

1.2 分配问题

455. 分发饼干（Easy）

• 分析

  • 每个孩子按照胃口的大小从小到大依次吃饼干，要保证胃口小的孩子先吃到满足胃口的大小最小的饼干

• 代码

  public int findContentChildren(int[] g, int[] s) {
      Arrays.sort(g);
      Arrays.sort(s);
      int child = 0;
      int cookies = 0;
      while (child<g.length && cookies<s.length) {
          if (g[child] <= s[cookies]) {
              child++;
          }
          cookies++;
      }
      return child;
  }
  

135. 分发糖果（Hard）

• 分析

  • 第一次从左向右遍历，如果右边孩子的评分 > 左边，则右边孩子的糖果=左边的+1
  • 第二次从右向左遍历，如果左边孩子的评分 > 右边，且左边孩子的糖果小于等于右边，则左边的糖果=右边+1
  • 贪心策略：每次遍历过程中，只考虑一遍的评分情况

• 代码

  public int candy(int[] ratings) {
      int[] array = new int[ratings.length];
      Arrays.fill(array, 1);
      for (int i = 1; i < ratings.length; i++) {
          // 右边大于左边，右边=左边+1
          if (ratings[i] > ratings[i-1]) {
              array[i] = array[i-1] + 1;
          }
      }
      int res = array[ratings.length-1];
      for (int i = ratings.length-2; i >= 0; i--) {
          // 左边大于右边，如果左边<=右边，则左边=右边+1，不然左边不变
          if (ratings[i] > ratings[i+1]) {
              array[i] = array[i] <= array[i+1] ? array[i+1] + 1 : array[i];
          }
          res += array[i];
      }
      return res;
  }
  

1.3 区间问题

435. 无重叠区间（Medium）

• 分析

  • 要想尽可能多的保留区间，那么我们需要将选择区间长度尽可能短的区间，这样，就会留给其他区间更多的空间
  • 因此，采取如下的贪心策略
    • 优先保留结尾小的且不相交的区间
  • 先将区间们按照结尾从小到大进行排序，然后依次比较是否相交。不相交则不用删除，相交则删除

• 代码

  public static int eraseOverlapIntervals(int[][] intervals) {
      if (intervals.length <= 1)
      return 0;
      // 先排序
      Arrays.sort(intervals, new Comparator<>() {
          @Override
          public int compare(int[] o1, int[] o2) {
               return o1[1] - o2[1];
          }
      });
      for (int[] interval : intervals) {
          System.out.println(interval[0] + "-" + interval[1]);
      }
      int res = 0;
      int[] prev = intervals[0];
      // 如果当前区间和prev区间相交，那么则删除。
      for (int i = 1; i < intervals.length; i++) {
          if (intervals[i][0] < prev[1]) {
              res++;
          } else {
              prev = intervals[i];
          }
      }
      return res;
  }
  

• 注意

  • 如果只给出0个或1个区间，那么删除0个

1.4 基础练手

605. 种花问题（Easy）

• 分析

• 先判断头尾是否满足能种上的条件，然后依次逐个判断能否种上

• 代码

  public static boolean canPlaceFlowers(int[] flowerbed, int n) {
      if(n==0) {
          return true;
      }
      int len = flowerbed.length;
      if (len == 1) {
          return flowerbed[0] == 0 && n == 1;
      }
  
      if (flowerbed[0] == 0 && flowerbed[1] == 0) {
          flowerbed[0] = 1;
          n--;
      }
      if (flowerbed[len-1] == 0 && flowerbed[len-2] == 0) {
          flowerbed[len-1] = 1;
          n--;
      }
      for (int i = 1; i < len - 1; i++) {
          if (flowerbed[i-1] == 0 && flowerbed[i+1] == 0 && flowerbed[i] == 0) {
              flowerbed[i] = 1;
              n--;
          }
      }
      return n <= 0;
  }
  

• 注意：

  • 因为依次判断3个，所以需要对头尾进行特殊处理
  • 特殊情况下的判断：[0]，n=1

452. 用最少数量的箭引爆气球（Medium）

• 分析

  • 先对给出的气球坐标数组排序，按照Xstart升序排序。对于start一样的，按照end升序排序
  • 对于排好序后的数组做如下判断，
    • 前1个是否和当前的相交，如果相交，取交集。下一个继续和交集比较。如果不相交，则说明要多花一根箭去射爆气球

• 代码

  public static int findMinArrowShots(int[][] points) {
      if (points.length <= 1) {
          return points.length;
      }
      Arrays.sort(points, new Comparator<int[]>() {
          @Override
          public int compare(int[] o1, int[] o2) {
              if (o1[0] > o2[0])
                  return 1;
              else if (o1[0] < o2[0])
                  return -1;
              else {
                  if (o1[1] > o2[1])
                      return 1;
                  else if (o1[1] < o2[1])
                      return -1;
                  else
                      return 0;
              }
          }
      });
      int[] temp = points[0];
      int res = 1;
      for (int i = 1; i < points.length; i++) {
          // 相交的情况下
          if (temp[1] >= points[i][0]) {
              temp[0] = Math.max(temp[0], points[i][0]);
              temp[1] = Math.min(temp[1], points[i][1]);
          } else {
              temp = points[i];
              res++;
          }
      }
      return res;
  }
  

• 注意

  • -2^31 <= xstart < xend <= 2^31 - 1
    • 这个条件导致了两个int类型的数直接进行加减运算可能导致溢出，所以需要在进行排序的时候不能简单的返回一个o1[0]-o2[0]

1.5 进阶尝试

406. 根据身高重建队列（Medium）

• 分析

  • 我的思路
    • 先对拿到的数组进行排序，按照K升序排序。若K一样，则按照H升序排序。同时记录下最高的高度
    • 先把K等于0的插入到队列中
    • 对于剩余元素，因为K是递增的，所有从头开始遍历队列，找到高于H的前K+1个元素，记录位置index，在index处插入

• 代码

  public static int[][] reconstructQueue(int[][] people) {
      Arrays.sort(people, new Comparator<int[]>() {
          @Override
          public int compare(int[] o1, int[] o2) {
              return o1[1] - o2[1] != 0 ? o1[1] - o2[1] : o1[0] - o2[0];
          }
      });
      int maxHeight = 0;
      for (int[] person : people) {
          maxHeight = Math.max(person[0], maxHeight);
      }
      List<int[]> queue = new LinkedList<>();
      for (int i = 0; i < people.length; i++) {
          if (people[i][1] == 0 || people[i][0] == maxHeight) {
              queue.add(people[i]);
              continue;
          }
          int heigher = 0;
          int index = 0;
          // 找到高于当前元素的前K个
          while (heigher < people[i][1]) {
              int[] ints = queue.get(index);
              index++;
              if (ints[0] >= people[i][0]) {
                  heigher++;
              }
          }
          // 找到第K+1个，找不到就加在
          while (index < queue.size()) {
              int[] p = queue.get(index);
              if (p[0] < people[i][0]) {
                  index++;
              } else {
                  break;
              }
          }
          queue.add(index, people[i]);
      }
      return queue.toArray(people);
  }
  

• 问题：耗时太长了，不够简练，时间复杂度为O(n^3)

• 优化改进（来自LeetCode官方题解）

  • 让我们从最简单的情况下思考，当队列中所有人的 (h,k) 都是相同的高度 h，只有 k 不同时，解决方案很简单：每个人在队列的索引 index = k。

  • 即使不是所有人都是同一高度，这个策略也是可行的。因为个子矮的人相对于个子高的人是 “看不见” 的，所以可以先安排个子高的人。

  • 总结

    • 将最高的人按照 k 值升序排序，然后将它们放置到输出队列中与 k 值相等的索引位置上。
      按降序取下一个高度，同样按 k 值对该身高的人升序排序，然后逐个插入到输出队列中与 k 值相等的索引位置上。
      直到完成为止。

  • 简直太强了好吗

• 新代码

  public int[][] reconstructQueue(int[][] people) {
      Arrays.sort(people, new Comparator<int[]>() {
          @Override
          public int compare(int[] o1, int[] o2) {
              return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
          }
      });
      List<int[]> res = new LinkedList<>();
      for (int[] person : people) {
          res.add(person[1], person);
      }
      return res.toArray(people);
  }
  

665. 非递减数列（Easy）

• 分析

  • 要将递减的部分修改成非递减的，一共有两种修改方法（此时 nums[i-1] > nums[i]），拉高nums[i]或拉低 nums[i-1]
    • 采用拉低的情况：nums[i]>=nums[i-2]
      • 对于nums[i]>=nums[i-2]这种情况时，既可以采取拉高也可以从采取拉低，但是采取拉低能避免 nums[i]<nums[i+1]<nums[i-1]拉高无法修复的问题
    • 采用拉高的情况：nums[i]<nums[i-2]

• 代码

  public boolean checkPossibility(int[] nums) {
      int times = 0;
      for (int i = 1; i < nums.length; i++) {
          if (nums[i-1] > nums[i]) {
              times++;
              if (i == 1 || nums[i-2] <= nums[i]) {
                  nums[i-1] = nums[i];
              } else {
                  nums[i] = nums[i-1];
              }
          }
  
      }
      return times <= 1;
  }
  

贪心算法

原文：https://www.cnblogs.com/primabrucexu/p/13937478.html