LeetCode刷题笔记【26】：贪心算法专题-4（柠檬水找零、根据身高重建队列、用最少数量的箭引爆气球）

前置知识

参考前文

参考文章：
LeetCode刷题笔记【23】：贪心算法专题-1（分发饼干、摆动序列、最大子序和）
LeetCode刷题笔记【24】：贪心算法专题-2（买卖股票的最佳时机II、跳跃游戏、跳跃游戏II）
LeetCode刷题笔记【25】：贪心算法专题-3（K次取反后最大化的数组和、加油站、分发糖果）

860.柠檬水找零

题目描述

LeetCode链接：https://leetcode.cn/problems/lemonade-change/description/

解题思路

思路: 用vector<int> counter(3,0)来记录5, 10, 20元钞票的数量;
如果顾客正好给5$,‘counter[0]++‘;如果顾客给的钱‘m>5‘$, target = m-5;
m=15, m=5的时候分类讨论即可;
当发现counter[0]<0时返回false;
最后返回true

代码

class Solution {
public:bool lemonadeChange(vector<int>& bills) {vector<int> counter(3,0);for(int m : bills){int target = m-5;if(target==0){//1 顾客直接给5$counter[0]++;}else if(target==5){//2 顾客给10$counter[1]++;counter[0]--;}else if(target==15){//3 顾客给20$if(counter[1]>=1){//3.1 有10$counter[2]++;counter[1]--;counter[0]--;}else{//3.2 没有10$counter[2]++;counter[0] -= 3;}}if(counter[0]<0 || counter[1]<0)return false;}return true;}
};

406.根据身高重建队列

题目描述

LeetCode链接：https://leetcode.cn/problems/queue-reconstruction-by-height/description/

解题思路

先按照身高, 进行从大到小排列, 身高相同的人根据k, 从小到大排列;
然后从排列后的people数组中依次提取person, 加入ans;
加入时直接通过k, 选择空位插入;

感觉似乎有些玄学, 如果一定要总结的话, 应该着眼于sort之后插入的环节:
每次插入的这个P都是未插入的person里面最高的, 相比于已经排好队的人, 是更矮的, 所以只要从前往后数k个, 直接插入即可.

代码

class Solution {
public:vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(), people.end(),[](vector<int>& a, vector<int>& b){return (a[0]>b[0]) || (a[0]==b[0] && a[1]<b[1]);});vector<vector<int>> ans;for(vector<int> person : people){ans.insert(ans.begin()+person[1], person);}return ans;}
};

452. 用最少数量的箭引爆气球

题目描述

LeetCode链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

踩坑-进行模拟

思路: 创建一个unordered_map<int,int> counter, 记录从x坐标垂直向上看, 有多少个气球
每次都选择气球最多的那个x坐标发射一支箭, 然后看击破哪些气球, 更新counter
直到气球被打完
思考了一下, 还是用vector<int> counter吧, 先遍历一下points, 求一下x轴最大值

class Solution {
private:vector<int> refreshX(vector<vector<int>>& points, int maxX){vector<int> counter(maxX+1, 0);for(vector<int> point : points){for(int x=point[0]; x<=point[1]; ++x){counter[x]++;}}return counter;}
public:int findMinArrowShots(vector<vector<int>>& points) {if(points.size()==0)return 0;else if(points.size()==1)return 1;int maxX=INT_MIN;for(vector<int> point : points){maxX = max(maxX, point[1]);}vector<int> counter = refreshX(points, maxX);// for(int i=0; i<counter.size(); ++i){//     cout << i << ":" << counter[i] << " " << endl;// }int ans=0;while(!points.empty()){ans ++;// 没有跳出, 那么本轮一定要射出一箭// 寻找本轮需要在哪个位置(shootingX)射箭int shootingX=0, shootingNum=INT_MIN;for(int i=1; i<counter.size(); ++i){if(counter[i] > shootingNum){shootingNum = counter[i];shootingX = i;}}for(int i=0; i<points.size(); ++i){points.erase(remove_if(points.begin(), points.end(), [shootingX](vector<int> p){return p[0]<=shootingX && p[1]>=shootingX;}), points.end());}counter = refreshX(points, maxX);}return ans;}
};

以上写法没问题, 但是没有考虑区间为负的情况
这样的话咱们还是用unordered_map吧

class Solution {
private:map<int,int> refreshX(vector<vector<int>>& points){map<int,int> counter;for(vector<int> point : points){for(int x=point[0]; x<=point[1]; ++x){counter[x]++;}}return counter;}
public:int findMinArrowShots(vector<vector<int>>& points) {if(points.size()==0)return 0;else if(points.size()==1)return 1;bool overlapping = false;for(int i=0; i<points.size()-1; ++i){if(points[i][1]>=points[i+1][0])overlapping=true;}if(overlapping==false)return points.size();map<int,int> counter = refreshX(points);int ans=0;while(!points.empty()){ans ++;// 没有跳出, 那么本轮一定要射出一箭// 寻找本轮需要在哪个位置(shootingX)射箭// cout << "此时的counter情况是: " ;// for(auto& pair : counter){//     cout << pair.first << ":" << pair.second << " " ;// }// cout << endl;int shootingX=0, shootingNum=INT_MIN;for(auto& pair : counter){if(pair.second > shootingNum){shootingNum = pair.second;shootingX = pair.first;}}// cout << "shootingX= " << shootingX << endl;for(int i=0; i<points.size(); ++i){points.erase(remove_if(points.begin(), points.end(), [shootingX](vector<int> p){return p[0]<=shootingX && p[1]>=shootingX;}), points.end());}counter = refreshX(points);}return ans;}
};

正确思路的贪心

以上想法很好, 也可以通过大部分案例, 就是每次射爆最多的气球;
但是对于测试用例[[9,17],[4,12],[4,8],[4,8],[7,13],[3,4],[7,12],[9,15]]而言
你先从x=8/9/10处射箭(最开始时这三点重叠气球最多), 之后就需要再射2箭
但是如果第一箭先x=4处射, 那么之后只用射1箭

所以转变思路:
① 先用左区间为index, sort points
② 依次从第二个气球i开始遍历, 不断更新"重叠的一组气球";
如果气球i和i-1没有重叠, 那么ans++;
否则就更新i的右边界为i和i-1的最小右边结(which means是"这一组重叠气球的右边界")

class Solution{
public:int findMinArrowShots(vector<vector<int>>& points){if(points.empty())return 0;sort(points.begin(), points.end(), [](vector<int>& a, vector<int>&b){return a[0] < b[0];});int ans=1;for(int i=1; i<points.size(); ++i){if(points[i][0] > points[i-1][1]){ans ++;}else{points[i][1] = min(points[i][1], points[i-1][1]);}}return ans;}
};

总结

贪心真的防不胜防, 波云诡谲, 难以捉摸;
今天第三题本来以为自己已经找到正确的贪心思路了(每次都捡能打掉最多气球的点射箭), 然而并不是;
所以个人其实认为将这些乱七八糟的东西都归到"贪心算法"中进行分类, 某种程度上并不是很严谨合理.
做的过程中多看看题解, 学习参考为主吧, 别硬磕, 伤身劳心费神.

本文参考：
柠檬水找零
根据身高重建队列
用最少数量的箭引爆气球