- 贪心算法
- A、分发饼干问题
- B、分发糖果
- 3、无重叠区间
- 4、非递归数列
A、分发饼干问题就是采用贪心的算法思想，保证每次操作都是局部最优，从而保证最后结果是全局最优的。
举一个最简单的例子：小明和小王喜欢吃苹果，小明可以吃五个，小王可以吃三个。已知苹果园里有吃不完的苹果，求小明和小王一共最多吃多少个苹果。在这个例子中，我们可以选用的贪心策略为，每个人吃自己能吃的最多数量的苹果，这在每个人身上都是局部最优的。又因为全局结果是局部结果的简单求和，且局部结果互不相干，因此局部最优的策略也同样是全局最优的策略。
- 问题分析
这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发。
- 核心算法
//贪心的思想是，用尽量小的饼干去满足小需求的孩子，所以需要进行排序先
public int findContentChildren(int[] g, int[] s) {
int child = 0;
int cookie = 0;
Arrays.sort(g);
//先将饼干 和 孩子所需大小都进行排序
Arrays.sort(s);
while (child < g.length && cookie < s.length ){
//当其中一个遍历就结束
if (g[child] <= s[cookie]){
//当用当前饼干可以满足当前孩子的需求，可以满足的孩子数量+1
child++;
}
cookie++;
// 饼干只可以用一次，因为饼干如果小的话，就是无法满足被抛弃，满足的话就是被用了
}
return child;
}
B、分发糖果
- 问题分析
只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1；
先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；
再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。
在样例中，我们初始化糖果分配为 [1,1,1]，第一次遍历更新后的结果为 [1,1,2]，第二次遍历更新后的结果为 [2,1,2]。
- java算法
class Solution {
public int candy(int[] ratings) {
int[] candy = new int[ratings.length];
for (int i = 0; i < candy.length; i++) {
candy[i] = 1;
}
//初始化所有分配为1
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candy[i] = candy[i - 1] + 1;
}
}
//如果后面的人比较大，就把前面的人的糖果数+1给后面的人。（只看前面比较大的）
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candy[i] = Math.max(candy[i],candy[i + 1] + 1);
}
}
//反过来，前面的人比较大，就让前面的人的糖果数大于后面的。（只看后面比较大的）
int count = 0;
for (int i = 0; i < candy.length; i++) {
count += candy[i];
}
//计算总的糖果数
return count;
}
}
3、无重叠区间
- 算法分析
在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。
具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。我们这里进行自定义排序。
在样例中，排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略，首先初始化为区间[1,2]；由于 [1,3] 与 [1,2] 相交，我们跳过该区间；由于 [2,4] 与 [1,2] 不相交，我们将其保留。因此最终保留的区间为 [[1,2], [2,4]]。
- 算法实现
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> {
if (a[0] == a[0]) return a[1] - b[1];
return a[0] - b[0];
});
//java的自定义排序，把区间按照结尾的大小进行增序排序，
//每次选择结尾最小且和前一个选择的区间不重叠的区间
int count = 0;
int edge = Integer.MIN_VALUE;
for (int i = 0; i < intervals.length; i++) {
if (edge <= intervals[i][0]) {
edge = intervals[i][1];
} else {
count++;
}
}
//edge比较小于区间第一个数，就把第二个数赋值给edge，反之就+1，
return count;
}
}
4、非递归数列
- 算法分析
本题是要维持一个非递减的数列，所以遇到递减的情况时（nums[i] > nums[i + 1]），要么将前面的元素缩小，要么将后面的元素放大。
但是本题唯一的易错点就在这，
如果将nums[i]缩小，可能会导致其无法融入前面已经遍历过的非递减子数列；
如果将nums[i + 1]放大，可能会导致其后续的继续出现递减；
所以要采取贪心的策略，在遍历时，每次需要看连续的三个元素，也就是瞻前顾后，遵循以下两个原则：
需要尽可能不放大nums[i + 1]，这样会让后续非递减更困难；
如果缩小nums[i]，但不破坏前面的子序列的非递减性；
算法步骤：
遍历数组，如果遇到递减：
还能修改：
修改方案1：将nums[i]缩小至nums[i + 1]；
修改方案2：将nums[i + 1]放大至nums[i]；
不能修改了：直接返回false；
- Java算法
class Solution {
public boolean checkPossibility(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 1; ++i) {
int x = nums[i], y = nums[i + 1];
if (x > y) {
nums[i] = y;
if (isSorted(nums)) {
return true;
}
nums[i] = x; // 复原
nums[i + 1] = x;
return isSorted(nums);
}
}
return true;
}
public boolean isSorted(int[] nums) {
int n = nums.length;
for (int i = 1; i < n; ++i) {
if (nums[i - 1] > nums[i]) {
return false;
}
}
return true;
}
}
