代码随想录Day31

Day 31 贪心算法 Part01

今日任务

• 455.分发饼干
• 376. 摆动序列
• 53. 最大子序和

代码实现

455.分发饼干

	//自己想的，虽然看着不让代码随想录给出的解法简洁，但是理论是一样的
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int startIndex = 0;
        for (int k : g) {
            for (int j = startIndex; j < s.length; j++) {
                if (s[j] >= k) {
                    count++;
                    startIndex = j + 1;
                    break;
                }
            }

        }
        return count;
    }
	//代码随想录解法，优先把大饼干分给胃口大的人
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int startIndex = s.length - 1;
        for (int i = g.length - 1; i >= 0; i--) {
            if (startIndex >= 0 && s[startIndex] >= g[i]) {
                count++;
                startIndex--;

            }
        }
        return count;
    }

376. 摆动序列

    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 3) return nums.length;
        int preDiff = 0;
        int curDiff = 0;
        int count = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
                count++;
            }
            if (curDiff != 0) {
                preDiff = curDiff;
            }
        }

        return count;

    }

53. 最大子序和

    public int maxSubArray(int[] nums) {
        int count = 0;
        int result = Integer.MIN_VALUE;
        for (int num : nums) {
            count+=num;
            if (count < 0) {
                count = 0;
            }
            if (count > result) {
                result = count;
            }
        }
        return result;
    }

今日总结

1. 除了第一道题一看就有思路，后边的题完全想不出来，也想不出贪心是什么个贪心法，只能看题解，有点像一开始做二叉树的感觉。
2. 能用贪心做的是否都能用动态规划实现？
3. 今天大亏，昨天和今天中午都想的清仓，睡一觉就忘了