代码随想录算法训练营第三十天

今天开始贪心专题的算法训练，用Carl的话使用贪心算法的问题一般遵循如下思路，想清楚局部最优，想清楚全局最优，感觉局部最优是可以推出全局最优，并想不出反例，那么就试一试贪心。(代码随想录)

LeetCode 455.分发饼干

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int index = s.length - 1;
        int num = 0;

        for (int i = g.length - 1; i >= 0; i--) {

            if (index < 0) {
                break;
            }

            if (s[index] >= g[i]) {
                num++;
                index--;
            }
        }
        return num;
    }
}

LeetCode 376.摆动序列

摆动序列还挺巧妙的，有很多细节需要注意，prevDiff的更新时机，平坡，etc.

class Solution {
    public int wiggleMaxLength(int[] nums) {
        
        // corner case, as described, if there are only 1 element return 1
        // if there are two elements and they are not equal, return 2
        if (nums.length == 1) {
            return 1;
        }else if (nums.length == 2) {
            if (nums[0] != nums[1]) {
                return 2;
            }
            return 1;
        }

        // result is initialized as 1, as the rightest one is always regarded as a waggle
        int result = 1;

        // 
        int prevDiff = 0;
        int curDiff = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            if (prevDiff >= 0 && curDiff < 0 || prevDiff <=0 && curDiff > 0) {
                result++;
                // update prevDiff only when a waggle is found, and recordsits direction
                prevDiff = curDiff;
            }
        }

        return result;
    }
}

LeetCode 53. 最大子数组和

贪心就贪心在，如果当前累计的值小于0，那么它对于全局的最大sum就是负贡献，就把它drop掉。

class Solution {
    public int maxSubArray(int[] nums) {

        int sum = Integer.MIN_VALUE;
        int temp = 0;

        for (int i = 0; i < nums.length; i++) {
            temp += nums[i];

            // do the comparasion first, and initialize sum to minimum to avoid no result recorded
            sum = temp > sum ? temp : sum;

            // temp is a temporaray record of local sum, if it is less than zero, then it makes no sense
            // to further sum
            if (temp < 0) {
                temp = 0;
            }
        }

        return sum;

    }
}