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