860. 柠檬水找零
https://leetcode.cn/problems/lemonade-change/
分情况讨论：
用five 、ten 、twenty 3个变量记录零钱的情况，每次看能否找零。
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)
{
if(five==0)
return false;
five--;
ten++;
}
if(bills[i] == 20)
{
if(ten>0&&five>0)
{
ten--;five--;
twenty++;
}
else if (five>=3)
{
five = five-3;
twenty++;
}
else
return false;
}
}
return true;
}
};
406. 根据身高重建队列
https://leetcode.cn/problems/queue-reconstruction-by-height/
从两个维度考虑问题，身高和排名
先按身高进行排序，然后根据排名插入指定位置。
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> > result;
for(int i=0;i<people.size();i++)
{
int k = people[i][1];
result.insert(result.begin()+k, people[i]);
}
return result;
}
};
由于vector插入操作，当插入的元素大于当前的大小时，会申请两倍的大小进行扩容，然后复制过去。
而且插入操作的时间复杂度是n，因此整个的时间复杂度就是n平方了，再加上扩容拷贝的次数，不止n的平方了。
改成链表的写法：
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> > result;
for(int i=0;i<people.size();i++)
{
int k = people[i][1];
list<vector<int>>::iterator iter = result.begin();
while(k--)
{
iter++;
}
result.insert(iter, people[i]);
}
return vector<vector<int>> (result.begin(), result.end());
}
};
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
算法思想：
关键是如何判断两个气球是否重叠：使用当前气球的左边界与上一个气球的右边界比较。
如果判断连续的气球是否重叠：更新当前气球的边界为当前气球右边界与上一个气球的右边界最小值。
class Solution {
private:
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];
}
public:
int findMinArrowShots(vector<vector<int>>& points) {
//对数组进行排序
sort(points.begin(), points.end(), cmp);
int count = 1;
for(int i=1;i<points.size();i++)
{
if(points[i][0]>points[i-1][1]) //当前气球的左边界和上一个气球的右边界进行比较，看有没有重合
count++;
else
{
points[i][1] = min(points[i][1], points[i-1][1]); //更新右边界为二者中小的部分
}
}
return count;
}
};
