代码随想录算法训练营第三十五天|860.柠檬水找零、406.根据

860.柠檬水找零

分三种情况：

5、10、20 

如果是5直接找零 10判断有没有5元 20的话优先找10，没有再用5找零

boollemonadeChange(vector<int>&bills){intfive=0,ten=0,twenty=0;for(intbill:bills){// 情况一if(bill==5)five++;// 情况二if(bill==10){if(five<=0)returnfalse;ten++;five--;}// 情况三if(bill==20){// 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着if(five>0&&ten>0){five--;ten--;twenty++;// 其实这行代码可以删了，因为记录20已经没有意义了，不会用20来找零}elseif(five>=3){five-=3;twenty++;// 同理，这行代码也可以删了}elsereturnfalse;}}returntrue;}

406.根据身高重建队列 

遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度

按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

staticboolcmp(constvector<int>&a,constvector<int>&b){if(a[0]==b[0])returna[1]<b[1];returna[0]>b[0];}vector<vector<int>>reconstructQueue(vector<vector<int>>&people){sort(people.begin(),people.end(),cmp);vector<vector<int>>que;for(inti=0;i<people.size();i++){intposition=people[i][1];que.insert(que.begin()+position,people[i]);}returnque;}

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

局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

intfindMinArrowShots(vector<vector<int>>&points){if(points.size()==0)return0;sort(points.begin(),points.end(),cmp);intresult=1;// points 不为空至少需要一支箭for(inti=1;i<points.size();i++){if(points[i][0]>points[i-1][1]){// 气球i和气球i-1不挨着，注意这里不是>=result++;// 需要一支箭}else{// 气球i和气球i-1挨着points[i][1]=min(points[i-1][1],points[i][1]);// 更新重叠气球最小右边界}}returnresult;}