贪心算法理论基础
题目分类大纲如下：
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
什么时候选择贪心算法？
贪心算法并没有固定的套路。所以唯一的难点就是如何通过局部最优，推出整体最优。
对于局部->全局，找不到反例，可以试一下贪心算法。
贪心一般解题步骤
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解 这个四步其实过于理论化了，我们平时在做贪心类的题目时，如果按照这四步去思考，真是有点“鸡肋”。
做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。
455.分发饼干
思路
是贪心，也是简单的模拟题目
混乱的点在于边界条件判断不清，这很不好。
题解
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int res = 0;
int j = g.size()-1;
for(int i = s.size()-1;i>=0;i--)
{
if(j<0)break;
while(j>=0 && g[j]>s[i])j--;
if(j>=0 && g[j]<=s[i])
{
res++;
j--;
}
}
return res;
}
};
376. 摆动序列
思路
也不知道和贪心有什么关系，看了题解知道计算折线，稀里糊涂的把条件都过了。
注意的点：
- 起始位置折线的判断
- 理解代码如何跳过相同点
- 牢牢记住
res = 折线+1,转化问题
题解
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() == 1)return 1;
int pre = 0;//保存前一状态
int res = 0;//折线数量
for(int i = 0;i<nums.size()-1;i++)
{
//开头不相等就是折线
if(pre == 0 && nums[i+1]!=nums[i])res++;
//pre与cur不相等就是折线
if(pre>0 && nums[i+1]-nums[i]<0)res++;
else if(pre<0 && nums[i+1]-nums[i]>0)res++;
//pre保存前一状态
if(nums[i+1]-nums[i]<0)pre = -1;
else if(nums[i+1]-nums[i]>0)pre = 1;
} //结果为节点，是折线+1
return ++res;
}
};
53. 最大子序和
思路
题目关键：
如果当前sum为正，那么保留sum，因为如果后面有大的加上大的肯定更大
如果当前sum为负，那么舍去sum，因为一定让后面变小
注意：与max的比较时刻都要进行，因为可能nums数组中都是负数，即使要舍去也要留一个最大（做题时忽略了这一点）。
贪心搜索如下：
题解
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//贪婪之♥
int max = INT_MIN;
int sum = 0;
for(int i = 0;i<nums.size();i++)
{
sum += nums[i];
if(sum>max)max = sum;//注意判断时机
if(sum<0)sum = 0;
}
return max;
}
};