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.?根據(jù)身高重建隊(duì)列
思路：
這道題的難點(diǎn)在于要滿足身高排序的要求，k值控制了身高的排序情況?？梢韵劝凑丈砀邚母叩降团判蛞槐?，這樣就知道每個(gè)人的身高序號(hào)，然后再根據(jù)k值往前插入，因?yàn)椴迦胧菑母咄筒迦?，這樣即使是后面身高低的人插在前面也不會(huì)影響其身后的排序。此外，因?yàn)檫@里會(huì)用到insert函數(shù)，insert函數(shù)的時(shí)間復(fù)雜度高，這里可以用鏈表來(lái)實(shí)現(xià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>> 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.?用最少數(shù)量的箭引爆氣球
思路：
這道題的思路是根據(jù)給定的數(shù)組，求取各個(gè)區(qū)間的重合情況，如果兩個(gè)區(qū)間重合就只需要一只箭，同理可得三個(gè)區(qū)間、四個(gè)區(qū)間以及更多區(qū)間的情況。
代碼：
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;
? ? }
};
