贪心算法 greedy

参考

https://github.com/changgyhub/leetcode_101

贪心算法

每次操作都是局部最优的，从而整体操作是最优的。

Leetcode455 分发饼干

分析

为了更多孩子能拿到饼干，对每个孩子的要求是“尽量给没拿到饼干的孩子留更多饼干”，换句话说就是“自己尽量拿更小的饼干”。因此可以对饼干排序，方便孩子挑选最小的。
不对孩子排序也可以实现分配。但是对孩子排序可以使用双指针提升计算效率。

题解

class Solution {
    public int findContentChildren(int[] g, int[] s) {
    	// 将饼干大小和孩子胃口从小到大排序
        Arrays.sort(g);
        Arrays.sort(s);

        int count = 0; // count表示拿到饼干的孩子数量
        for (int i = 0, j = 0; i < g.length && j < s.length; i++, j++) {
            while (j < s.length && g[i] > s[j]) { // 当前饼干不满足孩子胃口，则选择下一个更大的饼干
                j++;
            }
            if (j < s.length) {
                count++;
            }
        }
        return count;
    }
}

Leetcode135 分发糖果

分析

题目要求：每个孩子至少分配到 1 个糖果。为了更少分配糖果，设置每个孩子的初始糖果数为1.
题目要求：相邻两个孩子评分更高的孩子会获得更多的糖果。为了更少分配糖果，如果孩子评分更高，只比相邻1个糖果。
这里的相邻包括左邻和右邻。先从左到右遍历孩子，如果当前孩子比左边孩子评分更高，则糖果数=左孩糖果数加1.完成遍历后，满足左邻条件。再从右往左遍历孩子，如果当前孩子比右边孩子评分更高，则糖果数=右孩糖果数加1。为了同时满足两个相邻条件，糖果数取两次遍历的最大值。

题解

class Solution {
    public static int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1); // 每个孩子初始糖果数为1
        for (int i = 1; i < ratings.length; i++) { // 从左到右遍历
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = ratings.length- 2; i >= 0; i--) { // 从右往左遍历
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i + 1] + 1, candies[i]); // 取最大值
            }
        }

        int res = 0;
        for (int candy : candies) {
            res += candy;
        }
        return res;
    }
}

leetcode435无重叠区间

分析

为了不重叠且留下更多区间，每次被留下的区间的要求是“给后来者留更多空间”，即空间结束得更早。
因此按照区间的结束序号从小到大排序，每次都留下结束时间最早的，然后往后遍历，删去重叠的。

题解

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];
                }
        }); // 对结束序号排序

        int count = 0;
        int rightIndex = intervals[0][1]; // 留下的区间的结束序号
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < rightIndex) { // 被删除区间
                count++;
            } else {
                rightIndex = intervals[i][1]; // 留下的区间的结束序号
            }
        }
        return count;
    }
}