04.04 贪心算法
贪心算法是一种改进的「分步解决算法」，其核心思想是：将求解过程分成「若干个步骤」，然后根据题意选择一种「度量标准」，每个步骤都应用「贪心原则」，选取当前状态下「最好 / 最优选择（局部最优解）」，并以此希望最后得出的结果也是「最好 / 最优结果（全局最优解）」。
换句话说，贪心算法不从整体最优上加以考虑，而是一步一步进行，每一步只以当前情况为基础，根据某个优化测度做出局部最优选择，从而省去了为找到最优解要穷举所有可能所必须耗费的大量时间。
- 贪⼼选择性质：指的是一个问题的全局最优解可以通过一系列局部最优解（贪心选择）来得到。
- 最优子结构：指的是一个问题的最优解包含其子问题的最优解。
分析
为了尽可能的满⾜更多的⼩孩，而且一块饼干不能掰成两半，所以我们应该尽量让胃口小的孩子吃小块饼干，这样胃口大的孩子才有大块饼干吃。
所以，从贪心算法的角度来考虑，我们应该按照孩子的胃口从小到大对数组进行排序，然后按照饼干的尺寸大小从小到大对数组 进行排序，并且对于每个孩子，应该选择满足这个孩子的胃口且尺寸最小的饼干。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int i = 0,j = 0;
int res = 0;
sort(g.begin(), g.end());
sort(s.begin(), s.end());
while(i < g.size() && j < s.size()){
if(g[i] <= s[j]){
res++;
i++;
j++;
}
else{
j++;
}
}
return res;
}
};
|
- 时间复杂度：排序，O(mlogm + nlogn)
- 空间复杂度：O(logm + logn)，排序的额外空间开销。
分析
这道题我们可以转换一下思路。原题要求保证移除区间最少，使得剩下的区间互不重叠。换个角度就是：「如何使得剩下互不重叠区间的数目最多」。那么答案就变为了：「总区间个数 - 不重叠区间的最多个数」。我们的问题也变成了求所有区间中不重叠区间的最多个数。
从贪心算法的角度来考虑，我们应该将区间按照结束时间排序。每次选择结束时间最早的区间，然后再在剩下的时间内选出最多的区间。
将区间集合按照结束坐标升序排列，然后维护两个变量，一个是当前不重叠区间的结束时间,另一个是不重叠区间的个数。初始情况下，结束坐标为第一个区间的结束坐标。
依次遍历每段区间。对于每段区间：如果end_pos <= interval[i][0]，说明不重叠，更新count和end_pos。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v){
return u[1] < v[1];}
);
int endPos = intervals[0][1];
int count = 1;
for(int i = 1; i < intervals.size(); i++){
if(endPos <= intervals[i][0]){
count++;
endPos = intervals[i][1];
}
}
return intervals.size() - count;
}
};
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)
分析
用一个变量记录现有的零钱，然后遍历每个顾客所能支付的钱。
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
| class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0;
int ten = 0;
for(int i = 0; i < bills.size(); i++){
switch(bills[i]){
case 5:
five++;
break;
case 10:
if(five > 0){
ten++;
five--;
}else{
return false;
}
break;
case 20:
if(five > 0 && ten > 0){
five--;
ten--;
}
else if(five >= 3){
five -= 3;
}
else{
return false;
}
break;
}
}
return true;
}
};
|
分析
「评分更高的孩子必须比他两侧相邻位置上的孩子分得更多的糖果」：可以看做为以下两种条件：
- 当
ratings[i] > ratings[i-1]时，第 i 个孩子的糖果数量比第i - 1个孩子的糖果数量多；
- 当
ratings[i] > ratings[i+1]时，第 i 个孩子的糖果数量比第i + 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
| class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> sweets(n, 1);
for(int i = 1; i < n; i++){
if(ratings[i] > ratings[i-1]){
sweets[i] = sweets[i-1] + 1;
}
}
for(int i = n-2; i >= 0; i--){
if(ratings[i] > ratings[i+1]){
sweets[i] = max(sweets[i], sweets[i+1] + 1);
}
}
int sum = 0;
for(int i = 0; i < n; i++){
sum += sweets[i];
}
return sum;
}
};
|
贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
bool canJump(vector<int>& nums) {
int maxLen = 0;
for(int i = 0; i < nums.size(); i++){
if(maxLen >= i && i + nums[i] > maxLen){
maxLen = i + nums[i];
}
}
return maxLen >= nums.size() - 1;
}
};
|
动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
for(int i = 1; i < n; i++){
if(dp[i-1] >= i){
dp[i] = max(dp[i-1], i + nums[i]);
}
else{
dp[i] = dp[i-1];
}
}
return dp[n-1] >= n-1;
}
};
|
分析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int jump(vector<int>& nums) {
int maxPos = 0, n = nums.size(), end = 0, step = 0;
for(int i = 0; i < n-1; i++){
if(maxPos >= i){
maxPos = max(maxPos, i + nums[i]);
if(i == end){
end = maxPos;
step++;
}
}
}
return step;
}
};
|
分析
利用贪心算法的思想，让最重的和最轻的人一起走。这样一只船就可以尽可能的带上两个人。
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
| class Solution {
public:
int numRescueBoats(vector<int>& people, int limit) {
int n = people.size();
int left = 0, right = n-1;
int res = 0;
sort(people.begin(), people.end());
while(left < right){
int cur = people[left] + people[right];
if(cur > limit){
res++;
right--;
}
else{
res++;
left++;
right--;
}
}
if(left == right){
res++;
}
return res;
}
};
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)
分析
将坐标按结束位置升序排序。对于第一个区间，假设弓箭射在其结束位置，往后依次遍历每个区间，如果弓箭的坐标小于区间的起始坐标，说明需要新的弓箭。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int n = points.size();
int res = 1;
sort(points.begin(), points.end(), [](const auto& u, const auto& v){
return u[1] < v[1];
});
int arrow = points[0][1];
for(int i = 1; i < n; i++){
if(arrow < points[i][0]){
res++;
arrow = points[i][1];
}
}
return res;
}
};
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)
分析
使用贪心算法，按每种箱子所能装单元数的降序排序。
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
| class Solution {
public:
int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {
int n = boxTypes.size();
sort(boxTypes.begin(), boxTypes.end(), [](const auto& u, const auto& v){
return u[1] > v[1];
});
int capacity = truckSize;
int res = 0;
for(int i = 0; i < n; i++){
if(boxTypes[i][0] >= capacity){
res += capacity * boxTypes[i][1];
capacity = 0;
break;
}
else{
res += boxTypes[i][0] * boxTypes[i][1];
capacity -= boxTypes[i][0];
}
}
return res;
}
};
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)