代码随想录训练营第二十七天| 贪心理论基础 455.分发饼干 376. 摆动序列 53. 最大子序和

贪心没有套路，说白了就是常识性推导加上举反例

今天的内容比较简单 简单了解贪心是通过局部最优解反推全局最优解（有经验成分）

455.分发饼干

题目链接：455. 分发饼干 - 力扣（LeetCode）

讲解链接：代码随想录

 Java代码：

class Solution{//思路1 优先考虑饼干 小饼干先喂饱小胃口public int findContentChildren(int[] g, int[] s){Arrays.sort(s);Arrays.sort(g);int start = 0, count = 0;for(int i = 0; i < s.length && start < g.length; i++){if(s[i] >= g[start]){start++;count++;}}return count;}
}

 376. 摆动序列

题目链接：376. 摆动序列 - 力扣（LeetCode）

讲解链接：代码随想录

感觉这道题我只明白了摆动 但是对于三个特殊情况我想不到 还是得慢慢来思考

1. 情况一：上下坡中有平坡
2. 情况二：数组首尾两端
3. 情况三：单调坡中有平坡

Java代码： 

class Solution{public int wiggleMaxLength(int[] nums){if(nums.length <= 1) return nums.length;//当前差值int curdiff = 0;//上一个差值int prediff = 0;int count = 1;for(int i = 1; i < nums.length; i++){//得到当前差值curdiff = nums[i] - nums[i - 1];//如果当前差值和上一个差值为一正一负//等于0 的情况 表示初始时的prediffif((curdiff > 0 && prediff <= 0) || (curdiff < 0 && prediff >= 0)){count++;prediff = curdiff;}}return count;}
}

 53. 最大子序和

题目链接：53. 最大子数组和 - 力扣（LeetCode）

讲解链接：代码随想录

这题可以暴力直接过 有可能TLE 还是看看贪心 这道题也能用前缀和 或者 dp做

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;}
}

努力学习 找工作