Day 31 | 贪心算法 理论基础 、455.分发饼干 、 376. 摆动序列 、 53. 最大子序和

理论基础

文章讲解

455.分发饼干

题目
文章讲解
视频讲解

思路：从小饼干开始喂小胃口

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int start = 0;int count = 0;for (int i = 0; i < s.length && start < g.length; i++) {if (s[i] >= g[start]) {start++;count++;}}return count;}
}

376. 摆动序列

题目
文章讲解
视频讲解

思路：初始时preDiff可能为0

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. 最大子序和

题目
文章讲解
视频讲解

思路：在处理负数的情况下，对于任何负数，如果将其加入当前的和中，都会导致和变小。因此，如果当前的和已经为负数，那么加上任何负数都不会使和变大，因此应该将当前的 count 重置为0

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