代码随想录day26 Java版

今天开始刷贪心算法，新手保护期中爽得一批

455.分发饼干

先把两个数组排序，采用先满足胃口小的孩子，饼干数组无条件向后扫描，能满足孩子后再向后扫描胃口数组

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

376. 摆动序列

从头开始扫描，记录前一个和当前的差值，使用左闭右开区间处理平峰，满足一个加一个

class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length <= 1) return nums.length;int count = 1, pre = 0, cur = 0;for (int i = 1; i < nums.length; i++) {cur = nums[i] - nums[i - 1];if ((cur > 0 && pre <= 0) || (cur < 0 && pre >= 0)) {count++;pre = cur;}}return count;}
}

53. 最大子序和

贪心点在于舍弃掉小于0的部分，代码上使用acc作为累加器，小于等于0的时候重置

class Solution {public int maxSubArray(int[] nums) {if (nums.length == 1) return nums[0];int sum = Integer.MIN_VALUE,acc=0;for (int i = 0; i < nums.length; i++) {acc += nums[i];sum = Math.max(sum,acc);if (acc <= 0) acc = 0;}return sum;}
}