算法打卡 Day34（贪心算法）-分发饼干 + 摆动序列 + 最大子序和

理论基础

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

贪心算法没有固定的套路，其是常识性推导 + 举反例。

其一般的解题步骤可以分为四步：

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

Leetcode 455-分发饼干

题目描述

https://leetcode.cn/problems/assign-cookies/description/

解题思路

这道题的思路可以是尽量用较小的饼干满足胃口较小的孩子的需求，在分发饼干前，需要对胃口值和饼干尺寸进行排序。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int result = 0;sort(g.begin(), g.end());sort(s.begin(),s.end());int cIndex = 0;for (int i =0; i <s.size(); i++){if (cIndex<g.size() && s[i]>=g[cIndex]){cIndex++; result++;}}return result;}
};

类似题目

2410-运动员和训练师的最大匹配数

https://leetcode.cn/problems/maximum-matching-of-players-with-trainers/description/

class Solution {
public:int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {sort(players.begin(),players.end());sort(trainers.begin(),trainers.end());int count = 0;int j = 0;for (int i = 0; i < trainers.size();i++){if (j < players.size() && trainers[i]>=players[j]){j++; count++;}}return count;}
};

Leetcode 376-摆动序列

题目描述

https://leetcode.cn/problems/wiggle-subsequence/description/

解题思路

寻找摆动序列可以寻找序列中的转折点，可以通过画图清楚的描述出来。

我们通过 prediff 和 curdiff 记录当前数字前和后的坡度值，从而比较当前值是否为转折点

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int curdiff = 0;int prediff = 0;int count = 1;if (nums.size()==1) return count;for (int i = 0; i < nums.size()-1;i++){curdiff = nums[i+1]- nums[i];if (curdiff > 0 && prediff <= 0 || curdiff < 0 && prediff >= 0){count++;prediff = curdiff;}}return count;}
};

Leetcode 53-最大子序和

题目描述

https://leetcode.cn/problems/subsets-ii/description/

解题思路

遍历整个数组，判断是否要继续进行累计还是重新开始的规则是，判断累加和是否为正数，只有当累加和不小于 0 时，继续进行累计才可以保证不拖累后续的数字

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT_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;}
};