代码随想录算法训练营第三十四天|860.柠檬水找零、406.根据身高重建队列、452.用最少数量的箭引爆气球

860.柠檬水找零

思路：这道题难点在于给出20的时候，应该分几种情况去找零！

class Solution {
   
public:
    bool lemonadeChange(vector<int>& bills) {
   
        int count_5=0;
        int count_10=0;
        int leave=0;
        for(int i=0;i<bills.size();i++)
        {
   
            if(bills[i]-leave>5)
            {
   
                return false;
            }
            if(bills[i]==5)
            {
   
                leave+=5;
                count_5++;
            }
            else if(bills[i]==10)
            {
   
                if(count_5==0)
                {
   
                    return false;
                }
                leave+=5;
                count_10++;
                count_5--;
            }
            else
            {
   
                if(count_5==0)
                {
   
                    return false;
                }
                if(count_10==0&&count_5<3)
                {
   
                    return false;
                }
                leave+=5;
                if(count_10!=0)
                {
   
                    count_10--;
                    count_5--;
                }
                else
                {
   
                    count_5-=3;
                }
            }
        }
        return true;
    }
};

406.根据身高重建队列

思路：这道题最开始一点思路都没有，应该怎么样去排序，先按照身高排序，那么某个位置的元素，保证其前面的元素的身高参数一定是大于其本身的，根据其第二个参数插入在对应的位置！

class Solution {
   
public:
    static bool cmp(vector<int>&a,vector<int>&b)
    {
   
        if(a[0]==b[0]) return a[1]<b[1];
        else return a[0]>b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
   
        vector<vector<int>> queue;
        sort(people.begin(),people.end(),cmp);
        for(int i=0;i<people.size();i++)
        {
   
            int position=people[i][1];
            queue.insert(queue.begin()+position,people[i]);
        }
        return queue;
    }
};

采用链接结构：

class Solution {
   
public:
    static bool cmp(vector<int>&a,vector<int>&b)
    {
   
        if(a[0]==b[0]) return a[1]<b[1];
        else return a[0]>b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
   
        list<vector<int>> queue;
        sort(people.begin(),people.end(),cmp);
        for(int i=0;i<people.size();i++)
        {
   
            int position=people[i][1];
            auto it=queue.begin();
            while(position--)
            {
   
                it++;
            }
            queue.insert(it,people[i]);
        }
        return vector<vector<int>>(queue.begin(),queue.end());
    }
};

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

思路：找到重叠的区间，首先按照左边临界值或者右边临界值排序！若两个区间重叠一部分，保存这两个区间的右端点一定要是小的那一个，这样读取下一个时候，不会错过下一个小区间。假如更新更大的那一个，那么可能下一个区间与大的重合，但是与小的不重合，这个时候小的那一个就不会被击中，这样就出现问题了！

class Solution {
   
public:
    static bool cmp(vector<int>& a,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 result=1;
        for(int i=1;i<points.size();i++)
        {
   
            if(points[i][0]>points[i-1][1])
            {
   
                result++;
            }
            else
            {
   
                points[i][1]=min(points[i][1],points[i-1][1]);
            }
        }
        return result;
    }
};