【算法】面试笔试中的贪心算法

  贪心算法是面试中的常考问题。

它是在考虑局部最优解的情况下来得到全局最优解，即一个问题的最优解可以由它的子问题的最优解构造出来，一般使用反证法和数学归纳法来证明。

贪心算法没有固定的模板，是一种思想。

通常贪心算法都需要对原始数据进行排序，或者问题本身已经是一个序列，只需要在这个序列上对每一步做出决策。

下面通过几个问题来体会贪心策略的思想。

1.力扣 179.最大数^[1]

题目描述：

  给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：
  输入：nums = [10,2]
  输出：“210”
示例 2：
  输入：nums = [3,30,34,5,9]
  输出：“9534330”

分析：
  此题是典型的贪心问题。

按照贪心问题的一般解决方法，我们应该先排序，再进行组合。

排序的结果是使得数字组合后得到的字典序最大，因此我们可以得到排序的规则，即对于给定的两个数字 a 和 b，如果 ab >= ba，那么 a 排前面，否则 b 排前面。

具体代码如下：

public String largestNumber(int[] nums) {
    int n = nums.length;
    String[] strs = new String[n];
    for (int i = 0; i < n; i++) {
        strs[i] = String.valueOf(nums[i]);
    }
    // 1.首先排序
    Arrays.sort(strs, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            String s1 = o1 + o2;
            String s2 = o2 + o1;
            return s2.compareTo(s1);
        }
    });
    // 2.在有序序列上做出决策，这里直接按顺序添加进来
    StringBuilder sb = new StringBuilder();
    for (String s : strs) {
        sb.append(s);
    }
    // 注意输入全是 0 的情况，要删除多余的 0
    int k = 0, len = sb.length();
    while (k < len - 1 && sb.charAt(k) == '0') k++;
    return sb.substring(k);
}

2.力扣435.无重叠区间^[2]

题目描述：

  给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。

返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1：
  输入：intervals = [[1,2],[2,3],[3,4],[1,3]]
  输出：1
  解释：移除 [1,3] 后，剩下的区间没有重叠。

分析：为了能放更多的区间，每次选择 end 最小的，这样能保证后面可以放更多的区间。

所以排序应该按照 end 排序，end 越小越靠近前面。

具体代码如下：

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, new Comparator<int[]>(){
        @Override
        public int compare(int[] interval1, int[] interval2) {
            return interval1[1] - interval2[1];
        }
    });
    int end = intervals[0][1];
    int n = intervals.length;
    int cnt = 1;    // 合法区间的个数
    for (int i = 1; i < n; i++) {
        // 下一个候选区间的 start 大于等于上一个的 end 就是合法区间
        if (intervals[i][0] >= end) {
            cnt++;
            end = intervals[i][1];
        }
    }
    return n - cnt;
}

  从上面的例子可以看出贪心算法的基本思想，先排序，在做出决策。

想要完全掌握贪心的思想，还需要大量的练习，掌握提炼出最优子结构的能力。

Reference

[1]力扣179.最大数: https://leetcode-cn.com/problems/largest-number/

[2]力扣435.无重叠区间: https://leetcode-cn.com/problems/non-overlapping-intervals/
欢迎关注微信公众号。