代码随想录训练营Day23:贪心算法1

本文主要是介绍代码随想录训练营Day23:贪心算法1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心算法：选择每一个阶段的最优值从而达到一个全局最优

贪心算法的解题思路：

1. 将问题分为若干个子问题
2. 找出合适的贪心策略（核心）
3. 求解每个子问题的最优解
4. 将局部最优解堆叠成全局最优解

1.455分发饼干

贪心思路：两种分配原则：1.将大的先分给胃口大的。2.将小的先分给胃口小的

我们以第一种为例，首先就是对其进行一个排序，由于这个里面每个最多只能分配一个，从右往左遍历，找到大的饼干对应的满足胃口的那个进行分配从而实现全局最优。

class Solution {
public://因为在这个题目里面每个人最多只能分配一个，所以我们需要来确定相应的分配原则//1.将大的分配给大的，第二种是小的分配给小的int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int m = g.size()-1;int n = s.size()-1;int sum = 0;for(int i = m;i>=0;i--){if(n>=0&&s[n]>=g[i]){n--;sum++;}}return sum;}
};

2.376摆动序列

摆动序列：如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。

贪心策略三种情况：

1. 两端
2. 出现平的情况
3. 出现正负交替的情况

针对这三种情况，我们设置两个变量preDiff和curDiff=nums[i]-nums[i-1]分别用来存储当前的差值和前面那段的差值。

默认情况下val = 1(默认nums[0]端点参与),preDiff和curDiff都是为0，preDiff = curDiff的情况，找到转折点的时候，进行更新

1. i = 1的情况：preDiff = 0 ,curDiff <0 是转折点，curDiff = 0不是转折点，curDiff>0是转折点
2. i!=1的情况：preDiff>0,curDiff<0是转折点，curDiff<=0不是转折点
3. i!=1的情况：preDiff<0,curDiff>0是转折点，curDiff>=0不是转折点

将上面的情况进行综合就得到了下面的判断条件。

class Solution {
public://此题的思路就是在于找到当中的转折点//转折点分为三种情况：1.两端，两端是默认有一个转折点//2.有坡的情况：此时我们需要记录前面的坡度的情况//3.没坡的情况int wiggleMaxLength(vector<int>& nums) {int maxseries = 0;int n = nums.size();int prediff = 0;//记录的是预先的设定int curdiff = 0;int val = 1;for(int i=1;i<n;i++){curdiff = nums[i] - nums[i-1]; if((prediff>=0&&curdiff<0)||(prediff<=0&& curdiff>0)){val++;prediff = curdiff;}}return val;}
};

3.53最大子序和

贪心策略：计算起点的时候，前面一段连续子序和的值一定是正数或者0.如果当前的累加和小于0，那么就舍弃，重新从0开始。

使用maxs计算最大的子序和。count计算当前的子序和。如果count<0,则将其设置为0代表前面的舍弃。

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();if(n==0)return 0;if(n == 1)return nums[0];int maxs = nums[0];int count = 0;for(int i=0;i<n;i++){count += nums[i];if(count>maxs)maxs = count;//更新最大值if(count<0){count = 0;//更新起始位置}}return maxs;}
};

这篇关于代码随想录训练营Day23:贪心算法1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---