代码随想录算法训练营第二十七天-455分发饼干、376摆动序列、53最大子序和

• 前言
  状态：455AC、376、53 都需要看解析，感觉贪心上来都是一点思路都没有，可能题做的不够多。

• 更新

24-06-13 初始记录

初步题解

455 分发饼干

题目链接：(https://leetcode.cn/problems/assign-cookies)

属于小饼干优先。

public static void main(String[] args) {  
    int[] g = {10,9,8,7};  
    int[] s = {5,6,7,8};  
    System.out.println(findContentChildren(g, s));  
}  
  
  
/**  
 * 感觉上s从小排序，g从小排序。按序分配就行。  
 * @param g 孩子胃口  
 * @param s 饼干数  
 * @return 结果  
 */  
public static int findContentChildren(int[] g, int[] s) {  
    Arrays.sort(s);  
    Arrays.sort(g);  
  
    int count = 0;  
    for (int i = 0, j = 0; i < g.length && j < s.length; j++) {  
        if (g[i] <= s[j]) {  
            count++;  
            i++;  
        }  
    }  
    return count;  
}

376 摆动序列

题目链接：(https://leetcode.cn/problems/wiggle-subsequence)

没有思路。看了一点点解析，画图。把坡删了。（但是又忽略了单调坡的情况，具体题解在看解析部分）

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

53 最大子序和

题目链接：(https://leetcode.cn/problems/maximum-subarray)

没有思路。看了部分解析，说是连续和如果出现负数，直接抛弃，从下一个数开始。

// 思路是连续和为负，就直接抛弃连续和  
public int maxSubArray(int[] nums) {  
    int max = Integer.MIN_VALUE;  
    int sum = 0;  
  
    for (int num : nums) {  
        sum += num;  
        max = Math.max(sum, max);  
  
        if (sum < 0) {  
            sum = 0;  
        }  
    }  
  
    return max;  
}

看解析

455 分发饼干

解析：(https://programmercarl.com/0455.分发饼干.html)

有两种思路，大饼干优先满足胃口大的；小饼干优先满足胃口小的。

376 摆动序列

解析：(https://programmercarl.com/0376.摆动序列.html)

思路：

1. 怎样算有峰值 (preDiff >= 0 && curDiff < 0) || (preDiff <= 0 && curDiff > 0)

2. 数组首怎么计数：默认加上一个平节点，即 preDiff 为 0

3. 单调坡度有平坡：只在坡度进行更新的时候，才把前一个坡值进行记录

public int wiggleMaxLength(int[] nums) {  
    if (nums.length <= 1) {  
        return nums.length;  
    }  
  
    // 当前的差值  
    int curDiff = 0;  
    // 前一个坡的差值  
    int preDiff = 0;  
    int count = 1;  
  
    for (int i = 1; i < nums.length; i++) {  
        curDiff = nums[i] - nums[i - 1];  
  
        if ((preDiff >= 0  && curDiff < 0) || (preDiff <= 0 && curDiff > 0)) {  
            count++;  
            // 只有坡度更新才记录坡值  
            preDiff = curDiff;  
        }  
    }  
  
    return count;  
}

还有一个偷懒版本是先去重，再找坡。但是要循环两次，时间复杂度变高。

53 最大子序和

解析：(https://programmercarl.com/0053.最大子序和.html)