代码随机化训练营第 23 天:贪婪算法 1
最编程
2024-05-11 17:43:37
...
贪心算法:选择每一个阶段的最优值从而达到一个全局最优
贪心算法的解题思路:
- 将问题分为若干个子问题
- 找出合适的贪心策略(核心)
- 求解每个子问题的最优解
- 将局部最优解堆叠成全局最优解
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摆动序列
摆动序列:如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。
贪心策略三种情况:
- 两端
- 出现平的情况
- 出现正负交替的情况
针对这三种情况,我们设置两个变量preDiff和curDiff=nums[i]-nums[i-1]分别用来存储当前的差值和前面那段的差值。
默认情况下val = 1(默认nums[0]端点参与),preDiff和curDiff都是为0,preDiff = curDiff的情况,找到转折点的时候,进行更新
- i = 1的情况:preDiff = 0 ,curDiff <0 是转折点,curDiff = 0不是转折点,curDiff>0是转折点
- i!=1的情况:preDiff>0,curDiff<0是转折点,curDiff<=0不是转折点
- 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;
}
};