前言
顾名思义,贪心算法或贪心思想采用贪心的策略,保证每次操作都是局部最优的,从而使最后得到的结果是全局最优的。
leetcode 455
因为饥饿度最小的孩子最容易吃饱,所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子,所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后,我们采取同样的策略,考虑剩下孩子里饥饿度最小的孩子,直到没有满足条件的饼干存在。
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int child=0,cookie=0;
while(child < g.size() && cookie < s.size()){
if( g[child] <= s[cookie]) ++child;
++cookie;
}
return child;
}
};
leetcode 135
把所有孩子的糖果数初始化为1;先从左往右遍历一遍,如果右边孩子的评分比左边的高,则右边孩子的糖果数更新为左边孩子的糖果数加1;再从右往左遍历一遍,如果左边孩子的评分比右边的高,且左边孩子当前的糖果数不大于右边孩子的糖果数,则左边孩子的糖果数更新为右边孩子的糖果数加1。通过这两次遍历,分配的糖果就可以满足题目要求了。这里的贪心策略即为,在每次遍历中,只考虑并更新相邻一侧的大小关系。
class Solution {
public:
int candy(vector<int>& ratings) {
int n=ratings.size();
if(n<2) return n;
vector<int> candy(n,1);
for(int i=0;i<n-1;++i){
if(ratings[i+1]>ratings[i]) candy[i+1]=candy[i]+1;
}
for(int i=n-1;i>0;--i){
if(ratings[i-1]>ratings[i]) candy[i-1]=max(candy[i-1],candy[i]+1);
}
return accumulate(candy.begin(),candy.end(),0);
}
};
其中std::accumulate可以很方便的求和
template<class InputIterator, class Type, class Fn2>
Type accumulate(
InputIterator _First, //第一个迭代的值
InputIterator _Last, //最后一个迭代的值
Type _Val, //累加初值
BinaryOperation _Binary_op
);
leetcode 435
在选择要保留区间时,区间的结尾十分重要:选择的区间结尾越小,余留给其它区间的空间就越大,就越能保留更多的区间。因此,我们采取的贪心策略为,优先保留结尾小且不相交的区间。
具体实现方法为,先把区间按照结尾的大小进行增序排序,每次选择结尾最小且和前一个选择的区间不重叠的区间。我们这里使用C++ 的Lambda,结合std::sort() 函数进行自定义排序。
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int n=intervals.size();
if(n<2) return 0;
sort(intervals.begin(),intervals.end(),[](vector<int> &a,vector<int> &b){
return a[1]<b[1];
});
int pre=intervals[0][1];
int count=0;
for(int i=1;i<n;++i){
if(intervals[i][0]<pre){
++count;
}else{
pre=intervals[i][1];
}
}
return count;
}
};
leetcode 605
贪心策略即为寻找连续的三个0,在边界处添两个0,方便处理。
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
flowerbed.insert(flowerbed.begin(),0);
flowerbed.insert(flowerbed.end(),0);
int len=flowerbed.size();
int count=0;
for(int i=1;i<len-1;i++){
if(!flowerbed[i-1]&& !flowerbed[i]&&!flowerbed[i+1])
{
flowerbed[i]=1;
count++;
}
}
return count>=n?true:false;
}
};
leetcode452
这道题和题目435 十分类似,但是稍有不同,最小的引爆气球的弓箭数统计的条件正好与435相反。
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
int n = points.size();
if (n<2) return n;
sort(points.begin(), points.end(), [](vector<int> a, vector<int> b) {
return a[1] < b[1];
});
int count = 1, pre = points[0][1];
for(int i=1;i<n;++i){
if(points[i][0]>pre){
++count;
pre=points[i][1];
}
}
return count;
}
};
leetcode 122
所有上涨交易日都买卖(赚到所有利润),所有下降交易日都不买卖(永不亏钱)。(真香!)
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
if(n<2) return 0;
int sum=0;
for(int i=0;i<n-1;++i){
if(prices[i+1]>prices[i]){
sum+=prices[i+1]-prices[i];
}
}
return sum;
}
};
leetcode 763
在处理数组前,统计一遍信息(如频率、个数、第一次出现位置、最后一次出现位置等)可以使题目难度大幅降低。
这里统计了数组中元素的最后一次出现的位置,因为只有小写字母,所以通过维护一个长度为26的数组实现。
贪心的策略为遍历过程中维护本片段中包含元素的最后一个位置,若最后位置不在更新,即本片段符合题目要求。
class Solution {
public:
vector<int> partitionLabels(string S) {
int last[26];
int length = S.size();
for (int i = 0; i < length; i++) {
last[S[i] - 'a'] = i;
}
vector<int> partition;
int start = 0, end = 0;
for (int i = 0; i < length; i++) {
end = max(end, last[S[i] - 'a']);
if (i == end) {
partition.push_back(end - start + 1);
start = end + 1;
}
}
return partition;
}
};