欢迎关注个人公众号：爱喝可可牛奶
LeetCode算法训练-贪心算法 455.分发饼干 376. 摆动序列 53. 最大子序和
前置知识
贪心算法核心是找局部最优解，通过局部最优推导出全局最优
LeetCode 455. 分发饼干
分析
要求：把饼干分给孩子，并返回分了多少个孩子
局部最优：小饼干分给胃口小的
代码
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i = 0, j = 0;
int num = 0;
while(i < g.length && j < s.length){
if(s[j] >= g[i]){
num++;
j++;
i++;
}else{
j++;
}
}
return num;
}
}
LeetCode 376. 摆动序列
分析
返回 nums 中作为 摆动序列 的 最长子序列的长度
对于我们当前考虑的这个数，要么是作为山峰（即nums[i] > nums[i-1]），要么是作为山谷（即nums[i] < nums[i - 1]）
代码
class Solution {
public int wiggleMaxLength(int[] nums) {
// 0 i 作为波峰的最大长度
// 1 i 作为波谷的最大长度
int dp[][] = new int[nums.length][2];
dp[0][0] = dp[0][1] = 1;
for (int i = 1; i < nums.length; i++){
//i 自己可以成为波峰或者波谷
dp[i][0] = dp[i][1] = 1;
for (int j = 0; j < i; j++){
if (nums[j] > nums[i]){
// i 是波谷
dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);
}
if (nums[j] < nums[i]){
// i 是波峰
dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);
}
}
}
return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
}
}
LeetCode 53. 最大子数组和
分析
局部最优： 遍历到当前元素cur时，和为正数，继续遍历； 如果遍历到当前元素后和为负数，从后一个元素重新开始遍历
代码
class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 1){
return nums[0];
}
int sum = Integer.MIN_VALUE;
int count = 0;
for (int i = 0; i < nums.length; i++){
count += nums[i];
sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
if (count <= 0){
count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
}
}
return sum;
}
}
总结
贪心算法没有银弹，如果找出局部最优并可以推出全局最优，就是贪心，关键是如何去找局部最优
