Day31题目

LeetCode455.分发饼干

核心思想：将两个数组排序，计算饼干遍历完能有几个大于需求的个数

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0 ;
        int j = 0;
        int count = 0 ;
        while(i < g.length && j < s.length){
            if(s[j]>=g[i]){
                count++;
                j++;
                i++;
            }else{
            	// 如果当前最小的饼干满足不了最小需求，就增加饼干大小
                j++;
            }
        }
        return count ;
    }
}

LeetCode376.摆动序列：前一个增加后一个就要减少

核心思想：看数组峰值的个数即可，最后的长度是峰值的个数加一

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1) return nums.length;
        int result = 0;
        // 记录一下上一个是增加还是减少
        int preDiff = 0;
        int curDiff = 0;
        for(int i  = 0 ; i < nums.length-1 ; i ++ ){
            curDiff = nums[i+1] - nums[i];
            // 只要前一个和现在这个不一样就行
            if((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0) ){
                result ++;
                preDiff = curDiff;
            }
        }
        return result+1;
    }
}

LeetCode53.最大连续子数列和

核心思想：有好几种方法完成，使用数组维护从第一个数到目前这个数的所有子序列的和的最大值（动态规划），遍历

// 这里给出一个不用维护的办法：两年前自己写的。耗时最短，挺佩服当时没有模板刷题的自己
class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        for(int i = 0 ; i < nums.length ; i ++){
            if(nums[i] >= max){
                max = nums[i];
            }
        }
        int count = 0 ;
        for(int i = 0 ; i < nums.length ; i ++){
            count = count + nums[i];
            if(count > 0){
                if(count > max){
                    max = count;
                }
            }else{
            	// 如果前面的数的和小于0，那么自身的值就是目前最大
                count = 0;
            }
        }
        return max;
    }
}