860. 柠檬水找零
思路：
本题的思路是如果收到5，则直接收下，如果是10，则至少需要一张5，如果是20，则需要一张10和一张5或者直接是三张5，以上条件不满足就可以返回false。
代码：
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five=0,ten=0;
for(int i:bills)
{
if(i==5) five++;
if(i==10)
{
if(five==0)
{
return false;
}
five--;
ten++;
}
if(i==20)
{
if(five>=1&&ten>=1)
{
five--;
ten--;
}else if(five>=3)
{
five-=3;
}else{
return false;
}
}
}
return true;
}
};
406. 根据身高重建队列
思路：
这道题的难点在于要满足身高排序的要求，k值控制了身高的排序情况。可以先按照身高从高到低排序一遍，这样就知道每个人的身高序号，然后再根据k值往前插入，因为插入是从高往低插入，这样即使是后面身高低的人插在前面也不会影响其身后的排序。此外，因为这里会用到insert函数，insert函数的时间复杂度高，这里可以用链表来实现插入。
代码：
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);
list<vector<int>> res;
for(int i=0;i<people.size();i++)
{
int pos=people[i][1];
std::list<vector<int>>::iterator it=res.begin();
while(pos--)
{
it++;
}
res.insert(it,people[i]);
}
return vector<vector<int>>(res.begin(),res.end());
}
};
452. 用最少数量的箭引爆气球
思路：
这道题的思路是根据给定的数组，求取各个区间的重合情况，如果两个区间重合就只需要一只箭，同理可得三个区间、四个区间以及更多区间的情况。
代码：
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
if(points.size()==0) return 0;
sort(points.begin(),points.end(),cmp);
int res=1;
for(int i=1;i<points.size();i++)
{
if(points[i][0]>points[i-1][1])
{
res++;
}else
{
points[i][1]=min(points[i][1],points[i-1][1]);
}
}
return res;
}
};
