第八章 贪心算法 part01
贪心算法其实就是没有什么规律可言，所以大家了解贪心算法 就了解它没有规律的本质就够了。
不用花心思去研究其规律， 没有思路就立刻看题解。
基本贪心的题目 有两个极端，要不就是特简单，要不就是死活想不出来。
学完贪心之后再去看动态规划，就会了解贪心和动规的区别。
理论基础
- 贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
- 如何验证可不可以用贪心算法呢？：最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
简单题目
455.分发饼干
- 用小饼干先喂饱小胃口的思路
- 自己一开始写的
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int index = 0;
int result = 0;
for(int i = 0; i < s.length; i++){
if(index < g.length && g[index] <= s[i]){
index++;
result++;
}
}
return result;
}
}
代码随想录的
for (int i = 0; i < s.length && start < g.length; i++) {
if (s[i] >= g[start]) {
start++;
count++;
}
}
- 在 for 循环条件中同时检查数组长度限制，避免了在每次循环中重复检查条件。
- 另外注意应该用index访问g，g[index] <= s[i]，而不是g[i] <= s[i]
376. 摆动序列
思路
- 尽量保留峰值，删除单一坡度上的节点。已知遍历的下标 i ，计算
prediff（nums[i] - nums[i-1]）和curdiff（nums[i+1] - nums[i]），如果prediff < 0 && curdiff > 0或者prediff > 0 && curdiff < 0此时就有波动就需要统计。 - 三个特殊情况
- 情况一：上下坡中有平坡
考虑删掉靠左边相同的节点 (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0) - 情况二：数组首尾两端
为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0。result初始值为1 - 情况三：单调坡中有平坡
只在坡度有变化时更新 prediff ，就是把preDiff = curDiff;放在if条件判断里面
- 情况一：上下坡中有平坡
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length <= 1) return nums.length;
int result = 1;
int preDiff = 0;
int curDiff = 0;
for(int i = 1; i < nums.length; i++){ //注意这里i=1，或者i=0;i<nums.length -1
curDiff = nums[i] - nums[i-1];
if((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff <0)){
result++;
preDiff = curDiff;
}
}
return result;
}
}
53. 最大子序和
思路
- 当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
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;
}
}
