代码随想录算法训练营第31天 | 贪心理论基础, 455.分发饼干, 376.摆动序列, 53.最大子序和

贪心理论基础

代码随想录链接

贪心的本质:由不断地取局部最优, 最终达到全局最优.

什么时候用贪心呢? 不好意思, 贪心不像回溯那样有固定的套路. 贪心的关键点在于通过不断地求解局部最优而达到整体最优的效果, 所以如果不能举出来局部最优影响最终的整体最优的反例, 则可以试试贪心算法.

贪心算法的一般的解题步骤: * 将问题分解为若干子问题 * 找出合适的贪心策略 * 求解每个问题的最优解 * 将局部最优解堆叠为全局最优解

455.分发饼干

代码随想录链接

题目

LeetCode-455.分发饼干

给定两个数组, 第一个数组表示孩子们的胃口, 第二个数组表示饼干们能满足的胃口的大小, 在每个孩子只能分得一块饼干的前提下, 求最多能满足几个孩子的胃口.

自己的想法

如果要满足最多的孩子, 应该从胃口最小的孩子开始, 依次取满足其胃口且最小的饼干, 这样能保证胃口小的孩子使用胃口小的饼干满足, 胃口大的孩子能够用较大的饼干满足.

题解

有两种写法, 首先是自己A出来的:

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        vector<bool> used(s.size(), false); // 表示饼干有没有被分配掉
        int satisfied = 0;                  // 满足的孩子的个数
        sort(g.begin(), g.end());           // 孩子的胃口大小以及饼干的大小都由小到大排序
        sort(s.begin(), s.end());
        for (int i = 0; i < g.size(); i++) {// 遍历每个孩子, 找适合他们的且最小的未被分配的饼干
            int sizeNeeded = g[i];
            for (int j = 0; j < s.size(); j++)
                if (s[j] >= sizeNeeded && !used[j]) {
                    used[j] = true;
                    satisfied++;
                    break;
                }
        }
        return satisfied;
    }
};

由于孩子们胃口大小和饼干大小都进行了排序, 所以当一个位置的饼干满足了一个胃口较小的孩子之后, 下一个进行满足的孩子应得到的饼干应该在上一个孩子得到的饼干的右侧, 所以可以将两层for循环简化为一层.双指针法

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int satisfied = 0;
        sort(g.begin(), g.end());   // 胃口大小和饼干大小都由小到大排序
        sort(s.begin(), s.end());
        int cookieIndex = 0;
        for (int i = 0; i < g.size(); i++) {
            int sizeNeeded = g[i];
            while (cookieIndex < s.size() && sizeNeeded > s[cookieIndex]) cookieIndex++;    // 移动饼干的指针到满足孩子胃口的第一个
            if (cookieIndex < s.size() && sizeNeeded <= s[cookieIndex]) {                 // 如果数据合法, 且饼干满足当前孩子的胃口, 则给予这个孩子, 饼干指针右移一位
                satisfied++;
                cookieIndex++;
            }
        }
        return satisfied;
    }
};

376.摆动序列

代码随想录链接

题目

LeetCode-376.摆动序列

给定一个数组, 求连续的两个数的差值是正负数交替的子序列最长的长度.

子序列在原数组中不要求一定连续.

自己的想法

先计算出来整个数组的两个数的差值, 作为一个数组, 然后再在这个数组里来找正负值交替的子序列, 最后看找出的正负值交替的子序列的最长长度.

题解

自己A出来的:

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        vector<int> diffs;
        if (nums.size() == 1) return true;
        int firstPositiveIndex = INT_MAX, firstNegativeIndex = INT_MAX;     // 标记在差值数组中最左侧的正值和负值的位置
        for (int i = 1; i < nums.size(); i++) { // 计算差值数组
            int diff = nums[i] - nums[i - 1];
            if (diff > 0) {
                firstPositiveIndex = min(i - 1, firstPositiveIndex);
            }
            if (diff < 0) {
                firstNegativeIndex = min(i - 1, firstNegativeIndex);
            }
            diffs.push_back(diff);
        }
        vector<int> pathPos;            // 找开头是正值的子序列
        int needPositive = true;
        for (int i = firstPositiveIndex; i < diffs.size(); i++) {
            if ((needPositive && diffs[i] > 0) || (!needPositive && diffs[i] < 0)) {    // 满足正负值交替时, 才推入序列
                pathPos.push_back(diffs[i]);
                needPositive = !needPositive;
            }
        }
        vector<int> pathNeg;            // 找开头是负值的子序列
        needPositive = false;
        for (int i = firstNegativeIndex; i < diffs.size(); i++) {
            if ((needPositive && diffs[i] > 0) || (!needPositive && diffs[i] < 0)) {    // 满足正负值交替时, 才推入序列
                pathNeg.push_back(diffs[i]);
                needPositive = !needPositive;
            }
        }

        return pathNeg.size() > pathPos.size() ? pathNeg.size() + 1 : pathPos.size() + 1;   // 返回较长的序列的长度, 因为上面计算的是差值序列, 对应到原数组的子序列的话, 长度要 + 1
    }
};

感觉上面这段代码如果非要从贪心的方面来说的话, 就是为了尽可能延长子序列的长度, 就尽可能地在左侧找子序列的下一个数字.

卡哥的方法只需要遍历一遍就行, 通过对比前一个差值和当前差值是否异号. 就能判断出来最长的长度.

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        int curDiff = 0;    // 当前差值
        int preDiff = 0;    // 上一个差值
        int result = 1;     // 最终结果, 起始值为1的原因和上面的写法中return那句后面+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++;               // 长度+1
                preDiff = curDiff;      // 更改差值标记
            }
            /**
             * 为什么preDiff要在上面的括号内进行更改, 而不是每一次都更改preDiff呢?
             * 因为我们最终的目的是求差值异号的子序列, 不异号的时候没有更改的必要, 相当于子序列中没有出现过跳过的这些数字.
             */
            // 
        }
        return result;
    }
};

贪心应该也是贪在试图在最左侧找符合条件的数字罢.

53.最大子序和

代码随想录链接

题目

LeetCode-53.最大子序和

给定一个整数数组, 找到其中和最大的连续子数组, 返回其和的值.

自己的想法

暴力法, 两个for循环

再说贪心, 局部最大, 并记录最大的连续和, 就能得到结果. 当当前的连续和下降到负数的时候, 重置连续和为0, 也就是变相更改了区间的左侧.

设另一个数result来保存结果, 并在当前连续和大于其时, 更新为当前连续和, 也是变相地更改了区间右侧.

题解

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0, result = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i]; // 计算当前区间的连续和
            result = max(sum, result);  // 若发现了更大的连续和, 则更新结果
            if (sum < 0) sum = 0;   // 若连续和小于0, 加上下一个数之后, 和只会比下一个数单独的序列更小, 所以应被舍弃
        }
        return result;
    }
};