leetcode

代码随想录计划

Day 27–贪心算法

贪心算法其实就是没有什么规律可言，所以了解贪心算法 就了解它没有规律的本质就够了。

而贪心算法的本质就是选择每一阶段的局部最优解，从而达到全局最优

不用花心思去研究其规律， 没有思路就立刻看题解。

基本贪心的题目 有两个极端，要不就是特简单，要不就是死活想不出来。

学完贪心之后再去看动态规划，就会了解贪心和动规的区别。

分发饼干

455. 分发饼干 - 力扣（LeetCode）

自己代码：

class Solution {
    //局部最优的思想：每次挑选胃口最小的孩子,给最小尺寸的饼干
    public int findContentChildren(int[] g, int[] s) {
        if(s.length == 0) return 0;
        int count = 0;
        Arrays.sort(g);
        Arrays.sort(s);
        for(int i = 0,j = 0;i<g.length&&j<s.length;j++){
            if(s[j]>=g[i]){
                count++;
                i++;
            }
        }
        return count; 
    }
}

和题解答案一样

题解中有两种版本的答案，其实思想都是尽可能的达到大饼干给大胃口的孩子小饼干给小胃口的孩子。

所以代码也有两种，从小饼干小胃口开始遍历，或者从大胃口大饼干开始遍历。

时间复杂度都是O(nlogn)，排序的最优时间复杂度。

下面给出大胃口大饼干的写法

class Solution {
    // 思路2：优先考虑胃口，先喂饱大胃口
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;
        // 遍历胃口
        for (int index = g.length - 1; index >= 0; index--) {
            if(start >= 0 && g[index] <= s[start]) {
                start--;
                count++;
            }
        }
        return count;
    }
}

摆动序列

摆动序列

二刷注意

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;
    }
}

最大子数组和

最大子数组和

这道题目之前就做过，一开始想的是滑动窗口，后来看了眼提示发现是动态规划

如果是求最大连续子数组的长度或者子数组就是使用滑动窗口了。

这里最关键的是Math.max(nums[i],count+nums[i])当前位置的最大子序列和，一定是之前位置的最大子序列和加上当前位置的值，然后和当前位置值求最大。想到这里后面代码就都好写了。

class Solution {
    public int maxSubArray(int[] nums) {
        int count = 0;
        int max = nums[0];
        for(int i = 0;i<nums.length;i++){
            count = Math.max(nums[i],count+nums[i]);
            if(count > max) max = count;
        }
        return max;

    }
}

贪心算法的代码:

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for (int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置）
            if (count <= 0){
                count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
            }
        }
       return sum;
    }
}