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

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

本日的内容比力简朴 简朴相识贪婪是通过局部最优解反推全局最优解（有履历身分）
455.分发饼干

   标题链接：455. 分发饼干 - 力扣（LeetCode）
  讲授链接：代码随想录
   Java代码：

1. class Solution{
2.     //思路1 优先考虑饼干 小饼干先喂饱小胃口
3.     public int findContentChildren(int[] g, int[] s){
4.         Arrays.sort(s);
5.         Arrays.sort(g);
6.         int start = 0, count = 0;
7.         for(int i = 0; i < s.length && start < g.length; i++){
8.             if(s[i] >= g[start]){
9.                 start++;
10.                 count++;
11.             }
12.         }
13.         return count;
14.     }
15. }

复制代码

 376. 摆动序列

   标题链接：376. 摆动序列 - 力扣（LeetCode）
  讲授链接：代码随想录
  感觉这道题我只明白了摆动 但是对于三个特殊情况我想不到 照旧得渐渐来思索

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

Java代码： 

1. class Solution{
2.     public int wiggleMaxLength(int[] nums){
3.         if(nums.length <= 1) return nums.length;
4.         //当前差值
5.         int curdiff = 0;
6.         //上一个差值
7.         int prediff = 0;
8.         int count = 1;
9.         for(int i = 1; i < nums.length; i++){
10.             //得到当前差值
11.             curdiff = nums[i] - nums[i - 1];
12.             //如果当前差值和上一个差值为一正一负
13.             //等于0 的情况 表示初始时的prediff
14.             if((curdiff > 0 && prediff <= 0) || (curdiff < 0 && prediff >= 0)){
15.                 count++;
16.                 prediff = curdiff;
17.             }
18.         }
19.         return count;
20.     }
21. }

复制代码

 53. 最大子序和

   标题链接：53. 最大子数组和 - 力扣（LeetCode）
  讲授链接：代码随想录
  这题可以暴力直接过 有大概TLE 照旧看看贪婪 这道题也能用前缀和 大概 dp做

1. class Solution{
2.     public int maxSubArray(int[] nums){
3.         if(nums.length == 1) return nums[0];
4.         int sum = Integer.MIN_VALUE;
5.         int count = 0;
6.         for(int i = 0; i < nums.length; i++){
7.             count += nums[i];
8.             sum = Math.max(sum, count);//取出区间累计最大值
9.             if(count <= 0){
10.                 count = 0;//相当于重置最大子序起始位置
11.                 //因为遇到负数一定拉低总和
12.             }
13.         }
14.         return sum;
15.     }
16. }

复制代码

积极学习 找工作
 
 
 


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。