LeetCode 455 分发饼干

这题排序后双指针即可。若s[j]>=g[i]，两者都往后移，否则只有j能往后移。

贪心思想体现在对于每块饼干最大限度地被胃口最接近的孩子分到，达到利用率最高。

代码如下：

class Solution {public int findContentChildren(int[] g, int[] s) {for (int i = 0; i < g.length-1; i++) {for (int j = 0; j < g.length - 1 - i; j++) {if (g[j] > g[j+1]) {int temp = g[j+1];g[j+1] = g[j];g[j] = temp;}}}for (int i = 0; i < s.length-1; i++) {for (int j = 0; j < s.length - 1 - i; j++) {if (s[j] > s[j+1]) {int temp = s[j+1];s[j+1] = s[j];s[j] = temp;}}}int num = 0;int i = 0, j = 0;while (i < g.length && j < s.length) {if (g[i] <= s[j]) {i++; j++;num++;} else {j++;}}return num;}
}

java里的排序函数还不太熟悉，先还是用冒泡吧。

LeetCode 376 摆动序列

这题看的题解，随着下标增长，主要记录波峰波谷数目，其中波峰波谷其实是加在一起的，不够最后看大小判断最大的那个序列最后一段是波峰还是波谷。

代码如下：

class Solution {public int wiggleMaxLength(int[] nums) {int n = nums.length;if (n < 2) {return n;}int up = 1, down = 1;for (int i = 1; i < n; i++) {if (nums[i] > nums[i - 1]) {up = down + 1;} else if (nums[i] < nums[i - 1]) {down = up + 1;}}return Math.max(up, down);}
}

这种解法相对于消减法在0,0,0这个测试用例上要更容易处理一点。

LeetCode 53 最大子数组和

这题其实满简单，就是要每一步先用记录和的变量sum记录这一路过来加上的数值，但是如果它已经比当前值小了，就直接将它的值变成当前值。贪心也就是贪在这里。用局部状态简化全局推导，同时用一个max变量，每一次循环和它进行比较，及时记录下最大值。

这里采用一种技巧：将sum和max赋值成nums[0]，之后循环下标从1开始，这样可以避免一些问题，比如元素值可能是负数。

代码如下：

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