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

目录

一、贪心算法理论基础

二、（leetcode 455）分发饼干

三、（leetcode 376）摆动序列

四、（leetcode 53）最大子序和

---

一、贪心算法理论基础

1.什么是贪心

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

2.贪心一般解题步骤

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

这个四步其实过于理论化了，我们平时在做贪心类的题目，做题的时候，只要想清楚局部最优是什么，如果推导出全局最优，其实就够了。

二、（leetcode 455）分发饼干

力扣题目链接

状态：已AC

解题思路是从胃口小的先开始满足

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // 贪心的思想，想要满足最多的孩子，就要先从胃口小的孩子开始
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = 0;
        for(int i = 0; i < s.size(); ++i){
            if(index < g.size() && g[index] <= s[i]){
                index++;
            }
        }
        return index;
    }
};

三、（leetcode 376）摆动序列

力扣题目链接

状态：没有思路。

这道题如果是在没有做过的情况下遇到，首先想到的方法（常规解法）应该是动态规划：

设 dp 状态dp[i][0]，表示考虑前 i 个数，第 i 个数作为山峰的摆动子序列的最长长度
设 dp 状态dp[i][1]，表示考虑前 i 个数，第 i 个数作为山谷的摆动子序列的最长长度
动态规划的初始状态：dp[0][0] = dp[0][1] = 1，转移方程：

dp[i][0] = max(dp[i][0], dp[j][1] + 1)，其中0 < j < i且nums[j] < nums[i]，表示将 nums[i]接到前面某个山谷后面，作为山峰。
dp[i][1] = max(dp[i][1], dp[j][0] + 1)，其中0 < j < i且nums[j] > nums[i]，表示将 nums[i]接到前面某个山峰后面，作为山谷。

class Solution {
public:
    int dp[1005][2];
    int wiggleMaxLength(vector<int>& nums) {
        memset(dp, 0, sizeof dp);
        dp[0][0] = dp[0][1] = 1;
        for (int i = 1; i < nums.size(); ++i) {
            dp[i][0] = dp[i][1] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);
            }
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);
            }
        }
        return max(dp[nums.size() - 1][0], dp[nums.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 res = 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)){
                res++;
                preDiff = curDiff;
            }
        }
        return res;
    }
};

四、（leetcode 53）最大子序和

力扣题目链接

状态：暴力解法超时。

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。全局最优：选取最大“连续和”

局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int count = 0;
        int len = nums.size();
        for(int i = 0; i < len; ++i){
            count += nums[i];
            if(count > res){
                res = count;
            }
            if(count <= 0) count = 0;
        }
        return res;
    }
};