前言
今天搬砖不狠，明天地位不稳，早安，打工人
一、柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false
一开始我是这么想的，五块就收下，十块就找回五块，二十也找钱，然后用哈希记录，负数就退出，但是失败了hhh
看了题解发现了最关键的一个点是：局部最优是和五块、十块关系不大，二十块关系很大，给二十找零可以用一个10，一个5或者三个5，但是5是宝贵的，可以找钱给10和20，所以优先使用十块找零。
class Solution { public: bool lemonadeChange(vector<int>& bills) { int five=0,ten=0,twenty=0; for(int i=0;i<bills.size();i++) { if(bills[i]==5) //五块收下 { five++; } if(bills[i]==10) //十块收下 { ten++; if(five>=1) //五块找零 { five--; } else { return false; } } if(bills[i]==20) { if(ten>0&&five>0) //先找一个10和一个5 { ten--; five--; } else if(five>=3) //没有就给三个5 { five-=3; } else //什么都没有是吧，没有就g { return false; } } } return true; } };
二、根据身高重建队列
排序是为了，让第二个元素相同的可以由高到低排，然后找到第二个元素插入。
class Solution { public: static bool cmp(const vector<int>& a, const 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>> que; for (int i = 0; i < people.size(); i++) { int position = people[i][1]; //记录前面比自己高的人有多少个 que.insert(que.begin() + position, people[i]); //算好插入位置，插入 } return que; } };
三、用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数
class Solution { public: static bool cmp(vector<int>&a,vector<int>&b) { return a[1]<b[1]; } int findMinArrowShots(vector<vector<int>>& points) { int sum=1; sort(points.begin(),points.end(),cmp); //用右边界从小到大排序 for(int i=0;i<points.size()-1;i++) { if(points[i][1]<points[i+1][0]) //如果够不着直接+1 { sum++; } else { points[i+1][1]=min(points[i][1],points[i+1][1]); //更新下一个的右边界 } } return sum; } };
总结
排序要找好。从局部最优推到全局最优，1、5块最有用。2、找到一个维度先排好，再插入。3、边界，区间问题。
