贪心
一、算法解释
????????采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。
????????贪心算法问题需要满足的条件：
（1）最优子结构：规模较大的问题的解由规模较小的子问题的解组成，规模较大的问题的解只由其中一个规模较小的子问题的解决定；
（2）无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
（3）贪心选择性质：从局部最优解可以得到全局最优解。
二、经典问题?
1. 分配问题
455. Assign Cookies
455. 分发饼干
????????假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值?g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]?。如果 s[j]?>= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
贪心策略：给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干。
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int cnt = 0; //记录得到满足的孩子的数量
int child = 0,cookies = 0;
while(child<g.size() && cookies<s.size()){
if(g[child] <= s[cookies]){
cnt++;
child++;
}
cookies++;
}
return cnt;
}
135. Candy??
135. 分发糖果
????????n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目 。
贪心策略：左右各一次遍历，在每次遍历中，只考虑并更新相邻一侧的大小关系。
int candy(vector<int>& ratings) {
int size = ratings.size();
if(size < 2){
return size;
}
vector<int> num(size,1); //初始化每个孩子都分到一个糖果
for(int i=1;i<size;i++){
if(ratings[i] > ratings[i-1]){
num[i] = num[i-1] + 1;
}
}
for(int i=size-1;i>0;i--){
if(ratings[i-1] > ratings[i]){
num[i-1] = max(num[i]+1,num[i-1]);
}
}
return accumulate(num.begin(),num.end(),0); //accumulate：快速求和函数
}
2. 区间问题
435. Non-overlapping Intervals
435. 无重叠区间
????????给定一个区间的集合?intervals?，其中 intervals[i] = [starti, endi]?。返回 需要移除区间的最小数量，使剩余区间互不重叠?。
贪心策略：优先保留结尾小且不相交的区间。
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
int n = intervals.size();
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
return a[1] < b[1];
}
); //按照尾部区间大小排序
int removed = 0, prev = intervals[0][1];
for (int i = 1; i < n; ++i) {
if (intervals[i][0] < prev) {
++removed;
} else {
prev = intervals[i][1]; //更新prev
}
}
return removed;
}
三、巩固练习?
605. Can Place Flowers
605. 种花问题
????????假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组??flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数?n ，能否在不打破种植规则的情况下种入?n?朵花？能则返回 true ，不能则返回 false。
贪心策略：从左向右遍历花坛，能种就种。可以种花的条件是：
- 自己为空
- 左边为空 或者 自己是最左边
- 右边为空 或者 自己是最右边
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int cnt = 0; //记录花坛可以种多少花
for(int i=0;i<flowerbed.size();i++){
if(flowerbed[i]==0 && (i==0||flowerbed[i-1]==0) && (i==flowerbed.size()-1||flowerbed[i+1]==0)){
flowerbed[i] = 1;
cnt++;
}
}
return cnt >= n;
}
452. Minimum Number of Arrows to Burst Balloons
452. 用最少数量的箭引爆气球
????????有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组?points?，其中points[i] = [xstart, xend]?表示水平直径在?xstart?和?xend之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 ?xstart?≤ x ≤ xend，则该气球会被 引爆?。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数?。
贪心策略：寻找相交区间，让更多个气球重叠。
static bool cmp(const vector<int> &a,const vector<int> &b){
return a[1] < b[1];
}
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), cmp); //按照尾部区间大小排序
int num = 1, prev = points[0][1];
for (int i = 1; i < points.size(); ++i) {
if (points[i][0] > prev) {
num++;
prev = points[i][1]; //更新prev
}
}
return num;
}
763. Partition Labels
763. 划分字母区间
????????字符串?S?由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
贪心策略：区间每次刷新到最小的但是要全部包含同一字母的位置。
vector<int> partitionLabels(string s) {
vector<int> ans;
int num[26];
int start = 0,end = 0; //划分一个区间
for(int i=0;i<s.size();i++){
num[s[i]-'a'] = i; //记录每个字母最后的位置
}
for(int i=0;i<s.size();i++){
end = max(end,num[s[i]-'a']); //区间最小但要包含全部同一字母
if(i == end){ //区间搜索完毕
ans.push_back(end-start+1);
start = end + 1;
}
}
return ans;
}
122. Best Time to Buy and Sell Stock II
122. 买卖股票的最佳时机 II
????????给你一个整数数组 prices ，其中?prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候?最多?只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回你能获得的 最大 利润?。
贪心策略：在不限制交易次数的情况下，今天价格高于昨天价格即可出售，即求每天的正利润。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for(int i=1;i<prices.size();i++){
ans += max(0,prices[i]-prices[i-1]);
}
return ans;
}
};
406. 根据身高重建队列
406. Queue Reconstruction by Height
????????假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
????????请你重新构造并返回输入数组?people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
贪心策略：先排序，再插队。
- 首先将数组按身高排序
- 遍历数组 将 按?k?的值插入到?result 中对应的位置即可
- 返回结果?result 。
（一般这种数对，还涉及排序的，根据第一个元素正向排序，根据第二个元素反向排序，或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程。）
class Solution {
public:
static bool cmp(vector<int> a,vector<int> b){
if(a[0] == b[0])
return a[1]<b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(),people.end(),cmp);
vector<vector<int>> result;
for(int i=0;i<people.size();i++){
int index = people[i][1];
result.insert(result.begin() + index,people[i]);
}
return result;
}
};
665. 非递减数列
665. Non-decreasing Array
????????给你一个长度为?n?的整数数组?nums?，请你判断在 最多 改变?1 个元素的情况下，该数组能否变成一个非递减数列。
????????我们是这样定义一个非递减数列的：?对于数组中任意的?i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。
贪心策略：本题是要维持一个非递减的数列，所以遇到递减的情况时（nums[i] > nums[i + 1]），要么将前面的元素缩小，要么将后面的元素放大。问题是维持非递减的数列，那么我们需要尽可能的让前面的数字变小，然后寻找可以让前面数字变小的条件即可，其余的就让后面数字变大就好了。
我们可以?把 4 调小到 <= 2? 或者?把 2 调大到 4、5?，使数组有序。
我们可以?把 4 调小到 1、2? 或者?把 2 调大到 4、5?，使数组有序。
我们必须?把 2 调大到 4、5，才能使数组有序：我们不能把 4 调整为一个?<= 2?的数字，因为 4 前面的元素是 3。
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int cnt = 0;
for(int i=1;i<nums.size();i++){
if(nums[i] < nums[i-1]){
if(i==1 || nums[i]>=nums[i-2]){
nums[i-1] = nums[i];
}else{
nums[i] = nums[i-1];
}
cnt++;
}
}
return cnt<=1;
}
};
欢迎大家共同学习和纠正指教
|