链接
知识
理论基础
什么是贪心
贪心算法的本质是找到每个阶段的局部最优，从而去推导全局最优。
例如：
- 10张面值不同的钞票，如何取能取到总数最多的钱？每次取面额最大的钞票即可，这就是局部最优。取10次后拿到最多的钱，就是全局最优。这是贪心的思路。
- 背包最大承重是n。有一系列物品，其重量和价值各不相同，问这个背包能装的最大价值是多少？这需要用动态规划的思路来解决。
贪心的两个极端
贪心的题目要么太简短，要么太难。
贪心的套路
不像二叉树或者回溯算法的套路，贪心是没有套路的。部分较难的贪心题目，做过了才知道怎么做，否则完全想不到。非要说有套路，就是要想清楚每个阶段的局部最优，能否由局部最优推出全局最优。怎么由局部最优推出全局最优，也没有固定的思考方式。不需要做数学证明（数学证明的常用方法是数学归纳法和反证法），浪费时间。面试时，只要想到局部最优，可以推出全局最优，没有明显的反例，就已经可以试试，面试官不会要求严谨的数学证明。文字版讲解中有解决贪心算法的四个步骤，但实际做题时无法严格遵循四个步骤，实操性不强。
455.分发饼干
376.摆动序列
53.最大子序和
初次尝试
455.分发饼干
本题我的思路是，找出s数组的最大值，然后看g数组中有几个数小于等于s数组中的最大值，即为结果。我写了如下的代码，但只通过了23/25个测试样例：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
if (s.size() == 0) return 0;
sort(s.begin(), s.end());
int max = s[s.size() - 1];
int res = 0;
for (int i = 0; i < g.size(); i ++ )
if (g[i] <= max)
res ++ ;
if (s.size() <= res) return s.size();
return res;
}
};
直接看代码随想录的讲解吧。
376.摆动序列
53.最大子序和
实现
455.分发饼干
例子：
胃g: 1, 2, 7, 10
饼s: 1, 3, 5, 9
输出：3
策略：尽量用大饼干去喂胃口大的孩子，这样就可以充分利用饼干。
代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// 对两个数组进行排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int res = 0;
int index = s.size() - 1; // 饼干的index
// 优先用大饼干喂胃口大的小孩，因此倒序遍历
for (int i = g.size() - 1; i >= 0; i -- ) {
// 饼干成功投喂后，再向前遍历小孩数组，否则不能向前
if (index >= 0 && s[index] >= g[i]) {
res ++ ;
index -- ;
}
}
return res;
一定要外层循环遍历胃口，内层循环遍历饼干。如果外层循环遍历饼干，内层循环遍历胃口，拿上面的例子模拟就知道不可行。拿外层循环遍历饼干，内层循环遍历胃口，代码为：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// 对两个数组进行排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int res = 0;
int index = g.size() - 1;
for (int i = s.size() - 1; i >= 0; i -- ) {
if (index >= 0 && s[i] >= g[index]) {
res ++ ;
index -- ;
}
}
return res;
对于上面的例子，上述写法返回值为0。核心在于，要尝试去喂饱胃口大的孩子，而我们无法确保最大的饼干一定能喂饱胃口最大的孩子，如果最大的饼干无法喂饱胃口最大的孩子，那么上述写法的返回值恒为0。
另一种思路：尽量用小饼干去满足胃口小的孩子，这样可以充分利用小饼干。
376.摆动序列
53.最大子序和
心得与备忘录
455.分发饼干
- 一定要外层循环遍历胃口，内层循环遍历饼干。
- 内存循环用if判断而不用while循环，因为要一个小孩一个小孩地喂过去。
- 两种思路：先去满足大胃口的孩子，先去使用小饼干。两种思路遍历的顺序不同。