双非二本找工作前的准备day26

  学习目标：

每天复习代码随想录上的题目1-2道算法（时间充足可以继续）

今日碎碎念：

1）回溯篇完结，进入贪心专题，还剩下一个dp，过完准备二刷，以及刷剑指offer。

2）八股预计明天开始整理

力扣刷题

算法

力扣455：455. 分发饼干

解答思路：

        1）思路还是很直接的，就是排完序就贪心

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        int res = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int leng = g.length;
        int lens = s.length;
        int i = 0,j=0;
        while(i<leng && j<lens){
            if(g[i]<=s[j]){
                res++;
                i++;
                j++;
            }else{
                j++;
            }
        }
        return res;
    }
}

 力扣376：376. 摆动序列

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1) return nums.length; 
        //思路：我们选取极值,三种情况这里就不展开了
        int curDiff = 0;
        int preDiff = 0;
        // 记录峰值个数，序列默认序列最右边有一个峰值
        int res = 1;
        for(int i = 0;i<nums.length-1;i++){
            //计算当前差值
            curDiff = nums[i+1] - nums[i];
            //什么时候才要替换？
            //前：正/0，当前：负，前：负/0，当前：正
            if((preDiff>=0 && curDiff<0) || (preDiff<=0 && curDiff>0)){
                res++;
                preDiff = curDiff;
            } 
        }
        return res;
    }
}

 力扣53：53. 最大子数组和

class Solution {
    public int maxSubArray(int[] nums) {
        //这里我考虑使用dp做
        int len = nums.length;
        int[]dp = new int[len];
        //初始化:题目说了子数组最少包含一个元素
        dp[0] = nums[0];
        int res = dp[0];
        for(int i = 1;i<len;i++){
            //公式：当前位大，前面连续子数组的和＋当前位大
            dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}