代码随想录训练营Day31:● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

理论基础

贪心基础

455.分发饼干

题目链接

https://leetcode.cn/problems/assign-cookies/description/

题目描述

思路

自己写的，因为没有事先对两个数组进行排序，所以出现了问题

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(s);
        Arrays.sort(g);
       ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < s.length; i++) {
            list.add(s[i]);
        }
        int count = 0;
        for (int i = 0; i < g.length; i++) {
            Iterator<Integer> iterator = list.iterator();
            while (iterator.hasNext()) {
                Integer integer = iterator.next();
                if (g[i] <= integer) {
                    count++;
                    iterator.remove();
                    break;
                }
            }
        }
        return count;
    }
}

1、

public static int findContentChildren(int[] g, int[] s) {
        //优先考虑大胃口，大饼干先喂饱大胃口
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length-1;
        for (int i = g.length-1; i >= 0;i--) {
            if(i>=0&&g[i]<=s[start]){
                start--;
                count++;
            }
        }
        return count;
}

2、

public static int findContentChildren(int[] g, int[] s) {
        
        //优先考虑饼干，小饼干先喂饱小胃口
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = 0;
        for (int i = 0; i < s.length&&start<g.length; i++) {
            if(s[i]>=g[start]){
                start++;
                count++;
            }
        }
        return count;
    }

376. 摆动序列

题目链接

https://leetcode.cn/problems/wiggle-subsequence/description/

题目描述

思路

有点小懵

class Solution {
    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];
            //如果当前差值和上一个差值为一正一负
            //等于0的情况表示初始时的preDiff
            if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
                count++;
                preDiff = curDiff;
            }
        }
        return count;
    }
}

53. 最大子序和

题目链接

https://leetcode.cn/problems/maximum-subarray/description/

题目描述

思路

//result 存放最后的结果
//count用来统计每次累加的结果
//遍历数组，如果和为负数了，就将前边的丢掉，从下一个重新开始计算
class Solution {
    public int maxSubArray(int[] nums) {
        int result = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            if(count>result) result = count;
            if(count<0) count = 0;
        }
        return result;
    }
}

这个代码太厉害了，就用了这几行！！！