贪心算法 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); // 每个孩子初始糖果数为1for (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;}
}