代码随想录Day31 | 贪心算法 455.分发饼干 376. 摆动序列 53. 最大子序和
- 贪心算法
- 455.分发饼干
- 376.摆动序列
- 53.最大子序和
贪心算法
局部最佳 --> 全局最佳
刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心
455.分发饼干
文档讲解:代码随想录
视频讲解: 贪心算法,你想先喂哪个小孩?| LeetCode:455.分发饼干
状态
局部最优:有两种思考方式,最大的饼干喂饱最大胃口 或则 最小的饼干去喂饱最小的胃口,其实道理都是一样的
但是遍历的是饼干还是胃口就有区别了。
先满足最大的,需要通过胃口的遍历来控制饼干的移动。
先满足最小的,需要通过饼干的遍历来控制胃口的移动。
由于需要从最小开始或则最大开始所以需要对两个数组排序。排序之后,对于当前的饼干最大值去寻找满足条件的最大胃口,然后移动两个指针直到一个指针走完了其所属的数组
//对于满足
//优先满足能够满足的最大胃口的孩子
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int res = 0;
if(g.size() == 0 || s.size() == 0)
{
return res;
}
//对孩子的胃口排序
sort(g.begin(),g.end());
//对饼干的大小排序
sort(s.begin(),s.end());
//对s从大到小,去考察g中的大小
int i = s.size()-1;
//遍历胃口,当有胃口合适的计数
for(int j = g.size()-1;j>=0;j--)
{
if(i>=0 && g[j] <= s[i])
{
res++;
i--;
}
}
return res;
}
};
376.摆动序列
文档讲解:代码随想录
视频讲解: 贪心算法,寻找摆动有细节!| LeetCode:376.摆动序列
状态
局部最优:删除单调走向上的节点,或者平坡的节点 --> 保留峰和谷
情况一:上下坡中有平坡
情况二:数组首尾两端
情况三: 单调坡中有平坡
pre应当在更新坡度时才改变,即放到if语句里面,否则实时更新pre那么,平坡会消除单调性,导致判断失误
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() <= 1)
{
return nums.size();
}
int res = 1;
//当前的差值
int cur = 0;
//前一步的差值
int pre = 0;
for(int i = 0;i<nums.size()-1;i++)
{
cur = nums[i+1] - nums[i];
if(cur < 0 && pre >= 0)
{
res++;
pre = cur;
}
if(cur > 0 && pre <= 0)
{
res++;
pre = cur;
}
}
return res;
}
};
53.最大子序和
文档讲解:代码随想录
视频讲解: 贪心算法的巧妙需要慢慢体会!LeetCode:53. 最大子序和
状态
局部最优:当当前和计算为负数时,就需要放弃,因为其会导致下一个连续和变小。
代码随想录中这个关于是负数还是和为负数更新位置的解释很清晰
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//记录返回和
int res = INT_MIN;
//记录当前序列和
int cur = 0;
for(int i = 0;i<nums.size();i++)
{
//记录当前下标以及之前的和
cur += nums[i];
if(cur > res)
{
res = cur;
}
//如果和为负数,那么清空cur相当于从下一个数再重新开始计算
if(cur < 0)
{
cur = 0;
}
}
return res;
}
};