章丘环保网站建设 中企动力,云南人才招聘网,淘宝做问卷的网站,网络营销机构官方网站文章目录 前置知识860.柠檬水找零题目描述解题思路代码 406.根据身高重建队列题目描述解题思路代码 452. 用最少数量的箭引爆气球题目描述踩坑-进行模拟正确思路的贪心 总结 前置知识
参考前文 参考文章#xff1a; LeetCode刷题笔记【23】#xff1a;贪心算法专题-1#x… 文章目录 前置知识860.柠檬水找零题目描述解题思路代码 406.根据身高重建队列题目描述解题思路代码 452. 用最少数量的箭引爆气球题目描述踩坑-进行模拟正确思路的贪心 总结 前置知识
参考前文 参考文章 LeetCode刷题笔记【23】贪心算法专题-1分发饼干、摆动序列、最大子序和 LeetCode刷题笔记【24】贪心算法专题-2买卖股票的最佳时机II、跳跃游戏、跳跃游戏II LeetCode刷题笔记【25】贪心算法专题-3K次取反后最大化的数组和、加油站、分发糖果 860.柠檬水找零
题目描述 LeetCode链接https://leetcode.cn/problems/lemonade-change/description/ 解题思路
思路: 用vectorint counter(3,0)来记录5, 10, 20元钞票的数量; 如果顾客正好给5 , ‘ c o u n t e r [ 0 ] ‘ ; 如果顾客给的钱 ‘ m 5 ‘ , counter[0]; 如果顾客给的钱m5 ,‘counter[0]‘;如果顾客给的钱‘m5‘, target m-5; m15, m5的时候分类讨论即可; 当发现counter[0]0时返回false; 最后返回true
代码
class Solution {
public:bool lemonadeChange(vectorint bills) {vectorint counter(3,0);for(int m : bills){int target m-5;if(target0){//1 顾客直接给5$counter[0];}else if(target5){//2 顾客给10$counter[1];counter[0]--;}else if(target15){//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:vectorvectorint reconstructQueue(vectorvectorint people) {sort(people.begin(), people.end(),[](vectorint a, vectorint b){return (a[0]b[0]) || (a[0]b[0] a[1]b[1]);});vectorvectorint ans;for(vectorint 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_mapint,int counter, 记录从x坐标垂直向上看, 有多少个气球 每次都选择气球最多的那个x坐标发射一支箭, 然后看击破哪些气球, 更新counter 直到气球被打完 思考了一下, 还是用vectorint counter吧, 先遍历一下points, 求一下x轴最大值
class Solution {
private:vectorint refreshX(vectorvectorint points, int maxX){vectorint counter(maxX1, 0);for(vectorint point : points){for(int xpoint[0]; xpoint[1]; x){counter[x];}}return counter;}
public:int findMinArrowShots(vectorvectorint points) {if(points.size()0)return 0;else if(points.size()1)return 1;int maxXINT_MIN;for(vectorint point : points){maxX max(maxX, point[1]);}vectorint counter refreshX(points, maxX);// for(int i0; icounter.size(); i){// cout i : counter[i] endl;// }int ans0;while(!points.empty()){ans ;// 没有跳出, 那么本轮一定要射出一箭// 寻找本轮需要在哪个位置(shootingX)射箭int shootingX0, shootingNumINT_MIN;for(int i1; icounter.size(); i){if(counter[i] shootingNum){shootingNum counter[i];shootingX i;}}for(int i0; ipoints.size(); i){points.erase(remove_if(points.begin(), points.end(), [shootingX](vectorint p){return p[0]shootingX p[1]shootingX;}), points.end());}counter refreshX(points, maxX);}return ans;}
};以上写法没问题, 但是没有考虑区间为负的情况 这样的话咱们还是用unordered_map吧
class Solution {
private:mapint,int refreshX(vectorvectorint points){mapint,int counter;for(vectorint point : points){for(int xpoint[0]; xpoint[1]; x){counter[x];}}return counter;}
public:int findMinArrowShots(vectorvectorint points) {if(points.size()0)return 0;else if(points.size()1)return 1;bool overlapping false;for(int i0; ipoints.size()-1; i){if(points[i][1]points[i1][0])overlappingtrue;}if(overlappingfalse)return points.size();mapint,int counter refreshX(points);int ans0;while(!points.empty()){ans ;// 没有跳出, 那么本轮一定要射出一箭// 寻找本轮需要在哪个位置(shootingX)射箭// cout 此时的counter情况是: ;// for(auto pair : counter){// cout pair.first : pair.second ;// }// cout endl;int shootingX0, shootingNumINT_MIN;for(auto pair : counter){if(pair.second shootingNum){shootingNum pair.second;shootingX pair.first;}}// cout shootingX shootingX endl;for(int i0; ipoints.size(); i){points.erase(remove_if(points.begin(), points.end(), [shootingX](vectorint 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]]而言 你先从x8/9/10处射箭(最开始时这三点重叠气球最多), 之后就需要再射2箭 但是如果第一箭先x4处射, 那么之后只用射1箭
所以转变思路: ① 先用左区间为index, sort points ② 依次从第二个气球i开始遍历, 不断更新重叠的一组气球; 如果气球i和i-1没有重叠, 那么ans; 否则就更新i的右边界为i和i-1的最小右边结(which means是这一组重叠气球的右边界)
class Solution{
public:int findMinArrowShots(vectorvectorint points){if(points.empty())return 0;sort(points.begin(), points.end(), [](vectorint a, vectorintb){return a[0] b[0];});int ans1;for(int i1; ipoints.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;}
};总结
贪心真的防不胜防, 波云诡谲, 难以捉摸; 今天第三题本来以为自己已经找到正确的贪心思路了(每次都捡能打掉最多气球的点射箭), 然而并不是; 所以个人其实认为将这些乱七八糟的东西都归到贪心算法中进行分类, 某种程度上并不是很严谨合理. 做的过程中多看看题解, 学习参考为主吧, 别硬磕, 伤身劳心费神. 本文参考 柠檬水找零 根据身高重建队列 用最少数量的箭引爆气球
