代码随想录day31

贪心算法理论基础

什么是贪心

● 每一阶段都选择局部最优，从而达到全局最优

什么时候贪心

● 没有固定套路，想不到反例，就试试贪心

解题步骤

● 想清楚什么是局部最优，能不能推导出全局最优即可

455.分发饼干

● 力扣题目链接
● 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
● 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

思路

● 贪心算法，让大胃口的孩子先吃大饼干
● 先排序，然后遍历孩子，如果大饼干都不符合要求，那更小的一定不行了，这样好处理；如果遍历饼干，从大到小遍历，大孩子不够吃但小孩子可能够，因此不行
● 或者遍历饼干，从小遍历，如果小孩子都不行，那这块饼干一定不可以

代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int index = s.length - 1;
        for (int i = g.length - 1; i >= 0; i--) {
            if (index >= 0 && g[i] <= s[index]) {
                count++;
                index--;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

376. 摆动序列

● 力扣题目链接
● 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
● 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

思路

● 有个很巧妙的做法，遍历数组，如果前一个比后一个大，up就是down+1，反之反过来，最后计算最大值

代码

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int up = 1;
        int down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) up = down + 1;
            if (nums[i] < nums[i - 1]) down = up + 1;
        }
        return Math.max(up, down);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

53. 最大子序和

● 力扣题目链接
● 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路

● 从头开始遍历，每到一个数字，就加到sum上，然后更新max，一旦sum小于0，贪心直接向后看，sum置为0
● 多考虑好好想想，

代码

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(sum, max);
            if (sum < 0) {
                sum = 0;
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14