DAY27|贪心算法Part01|LeetCode:455.分发饼干、376. 摆动序列、53. 最大子序和

贪心算法

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

        贪心算法并没有固定的套路，最难想的就在于如何通过局部最优去推出全局最优。在做一个题目的时候，靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

        那么什么时候可以使用贪心算法呢？刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

LeetCode:455.分发饼干

力扣代码链接

文字讲解：LeetCode:455.分发饼干

视频讲解：贪心算法，你想先喂哪个小孩？

基本思路

        要求每个孩子最多只能喂一块饼干，那么就不能造成饼干尺寸的浪费，做到物尽其用，大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

        此时我们就可以利用贪心策略，先对饼干尺寸和小孩的胃口值进行排序，从后向前遍历小孩数组，然后用大饼干去投喂胃口大的小孩，并统计出能满足的小孩的数量。

        注意：上面的方法中，我们选择先遍历小孩数组，然后再去遍历饼干，为什么我们没有先遍历饼干，然后在遍历小孩呢？看了下面的图，其实就不难看出，由于index指向胃口值，只有满足条件才会移动，如果我们先遍历饼干，那么就会因为一直无法找到能满足胃口值为10的小孩而导致所有的饼干都无法匹配。

C++代码

// 版本一
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1; // 饼干数组的下标
        int result = 0;
        for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口
            if (index >= 0 && s[index] >= g[i]) { // 遍历饼干
                result++;
                index--;
            }
        }
        return result;
    }
};

LeetCode:376. 摆动序列

力扣代码链接

文字讲解：LeetCode:376. 摆动序列

视频讲解：贪心算法，寻找摆动有细节！

基本思路

        本题要求通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。以示例2为例：

        实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）。这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点。

        这里我们可以定义prediff和curdiff，用来计算当前下标i所对应的元素的前后波动情况。这个题目最难想清楚的就是所出现的三种情况：

1. 情况一：上下坡中有平坡
2. 情况二：数组首尾两端
3. 情况三：单调坡中有平坡

情况一：上下坡中有平坡

        例如 [1,2,2,2,1]这样的数组，它的摇摆序列长度是多少呢？ 其实是长度是 3，也就是我们在删除的时候 要不删除左面的三个 2，要不就删除右边的三个 2。为了统一规则我们可以删除左边三个2，那么 当 prediff = 0 && curdiff < 0 也要记录一个峰值。

        所以我们记录峰值的条件应该是： (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)。

情况二：数组首尾两端

        题目中说了，如果只有两个不同的元素，那摆动序列也是 2。因为我们在计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]）的时候，至少需要三个数字才能计算，而数组只有两个数字。对于数组[2,5]来讲，假设数组为[2, 5, 5]。这样就有了prediff = 0，curdiff=3。

        针对上述情况可以设置result 初始为 1（默认最右面有一个峰值），此时 curDiff > 0 && preDiff <= 0，那么 result++（计算了左面的峰值），最后得到的 result 就是 2（峰值个数为 2 即摆动序列长度为 2）。

// 版本一
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 0; i < nums.size() - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            // 出现峰值
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
            }
            preDiff = curDiff;
        }
        return result;
    }
};

        如果只考虑这两种情况，那么提交会提示报错，表示我们还有情况没有考虑到。

情况三：单调坡度有平坡

        这种情况很容易被忽略，如果在一个单调坡度上有平坡，例如[1,2,2,2,3,4]，如图：

        图中，我们可以看出，版本一的代码在三个地方记录峰值，但其实结果因为是 2，因为 单调中的平坡 不能算峰值（即摆动）。之所以版本一会出问题，是因为我们实时更新了 prediff。那么我们应该什么时候更新 prediff 呢？我们只需要在这个坡度摆动变化的时候，更新 prediff 就行，这样 prediff 在单调区间有平坡的时候就不会发生变化，造成我们的误判。

C++代码

// 版本二
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int curDiff = 0; // 当前一对差值
        int preDiff = 0; // 前一对差值
        int result = 1;  // 记录峰值个数，序列默认序列最右边有一个峰值
        for (int i = 0; i < nums.size() - 1; i++) {
            curDiff = nums[i + 1] - nums[i];
            // 出现峰值
            if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
                result++;
                preDiff = curDiff; // 注意这里，只在摆动变化的时候更新prediff
            }
        }
        return result;
    }
};

LeetCode:53. 最大子序和

力扣代码链接

文字讲解：LeetCode:53. 最大子序和

视频讲解：贪心算法的巧妙需要慢慢体会！

基本思路

        很容易想到的是暴力解法，使用两层for循环，第一层设置起始位置，而第二层可以遍历数组，寻求最大和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) { // 设置起始位置
            count = 0;
            for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
                count += nums[j];
                result = count > result ? count : result;
            }
        }
        return result;
    }
};

        但是这种方法所耗费的时间很多，很容易会超时。

而我们使用贪心算法，可以先设置一个结果值，result = INT_MIN，然后开始遍历整个数组，很容易想到的是如果一个数组的存在正数，那么最大和数组的起始位置一定正数，那么我们遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。

        并且一旦count大于当前记录的最大值，我们就及时记录下来。

if (count > result) result = count;

C++代码

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

原文地址：https://blog.csdn.net/ning1437589742/article/details/143706608

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！