贪心算法其实就是没有什么规律可言。没有思路就立刻看题解。
基本贪心的题目有两个极端，要不就是特简单，要不就是死活想不出来。
贪心的本质：贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
什么时候用贪心
贪心算法并没有固定的套路。就是常识性推导加上举反例子。刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
贪心一般解题步骤
做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。
1、455分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。
我的思路：我想每个人在饼干里找离他最能饱饼干，把饼干排序，这样查找时快一些。测试了一下 21/25超时。结果应该是对的，但是超时。于是我把食量也排序，这样找过的饼干前面的就不看了，23/25超时还是超时。
代码随想录：人从后往前遍历找饼干。简便了很多。下图1是代码随想录的，从后往前只需看当前饼干能不能满足孩子胃口，不能那这个孩子就不用看了，往前的饼干也不可能满足。很经典。。图1是我的，从前往后，当前饼干不满足孩子胃口，但是后面的饼干更大，可能满足，我还得接着遍历饼干，时间复杂度更高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
vector<bool> used(s.size(),false);
std::sort(g.begin(),g.end());
std::sort(s.begin(),s.end());
int num = 0;
int lastj = 0;
for(int i =0;i<g.size();i++){
for(int j = lastj;j<s.size();j++){
if(s[j] < g[i])continue;
used[j] = true;
num++;
lastj = j+1;
break;
}
}
return num;
}
};
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
std::sort(g.begin(),g.end());
std::sort(s.begin(),s.end());
int num = 0;
for(int i = g.size()-1, j = s.size()-1;i>=0;i--){
if(j < 0 || s[j] < g[i])continue;
num++;
j--;
}
return num;
}
};
|
2、376摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
我的思路：没做出来。这题暂时不做了。贪心。
代码随想录：局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
int curDiff = 0;
int preDiff = 0;
int result = 1;
for (int i = 0; i < nums.size() - 1; i++) {
curDiff = nums[i + 1] - nums[i];
if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
preDiff = curDiff;
}
}
return result;
}
};
|
3、53最大子序和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
我的思路：没做出来。贪心真的想不到。只能用用回溯做。
代码随想录：局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。全局最优：选取最大“连续和”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums[i];
if (count > result) {
result = count;
}
if (count <= 0) count = 0;
}
return result;
}
};
|
