【算法刷题day31】Leetcode：455. 分发饼干、376. 摆动序列、53. 最大子数组和

草稿图网站
java的Deque

Leetcode 455. 分发饼干

题目：455. 分发饼干
解析：代码随想录解析

解题思路

从大到小遍历所有的饼干，找到胃口最大的孩子吃掉它。循环，直到没有孩子的胃口小于等于当前的饼干，或者饼干吃完了。

代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int res = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int child = g.length - 1;
        for (int cookie = s.length - 1; cookie >= 0; cookie--) {
            while (child >= 0) {
                if (g[child] <= s[cookie]) {
                    res++;
                    child--;
                    break;
                }
                child--;
            }
        }
        return res;

    }
}

//换个遍历方式，也是让胃口大的孩子，先吃掉大饼干
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int res = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int cookie = s.length - 1;
        for (int child = g.length - 1; child >= 0; child--) {
            if (cookie >= 0 && g[child] <= s[cookie]) {
                    res++;
                    cookie--;
            }
        }
        return res;

    }
}

总结

Leetcode 376. 摆动序列

题目：376. 摆动序列
解析：代码随想录解析

解题思路

仅当有波动的时候更新lastDiff和res++

代码

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

总结

暂无

Leetcode 53. 最大子数组和

题目：53. 最大子数组和
解析：代码随想录解析

解题思路

curSum >= 0的时候，对区间和都是有收益的。当curSum<0的时候，只有负收益，所以重新启动。

代码

class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        int curSum = 0;
        for (int i = 0; i < nums.length; i++) {
            curSum += nums[i];
            if (curSum > res) {
                res = curSum;
            }
            if (curSum < 0) curSum = 0;
        }
        return res;
    }
}

总结

暂无