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

发布时间:2024年01月16日

题目:860.柠檬水找零

文章链接:代码随想录

视频链接:LeetCode:860.柠檬水找零

题目链接:力扣题目链接

图释:

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        unordered_map<int,int> change;
        for(int i=0; i<bills.size(); i++){
            // 情况一 5美元
            if(bills[i] == 5){
                change[5]++;
            }
            else if(bills[i] == 10){
                if(change[5] == 0){
                    return false;
                }
                change[5]--;
                change[10]++;
            }
            else if(bills[i] == 20){
                if(change[10]>0 && change[5]>0){
                    change[20]++;
                    change[10]--;
                    change[5]--;
                }
                else if(change[5]>=3){
                    change[5] = change[5]-3;
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }
};

题目:406.根据身高重建队列

文章链接:代码随想录

视频链接:LeetCode:406.根据身高重建队列

题目链接:力扣题目链接

图释:

class Solution {
public:
    // 就是说传进来两个参数,如果返回true则是按原来的顺序,如果返回false则是相反
    static bool cmp(const vector<int>& a, const vector<int>& b){
        if(a[0] == b[0]) return a[1] < b[1]; // a[7,0] b[7,1]  a[1]<b[1]正确,则返回true 原来顺序 
        return a[0] > b[0]; // a[7,1] b[5,0]  a[0]>b[0]  
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
       // 第一位从大到小排序,第二位从小到大排
       sort(people.begin(), people.end(), cmp);
       // 定义一个链表
       list<vector<int>> que; 
       for(int i=0; i<people.size(); i++){
           int position = people[i][1]; // 插入下标到position的位置
           std::list<vector<int>>::iterator it = que.begin(); //获取迭代器 
           while(position--){
               it++; // 位置减减,迭代器加加
           }
           que.insert(it,people[i]); // 插入
       }
       return vector<vector<int>>(que.begin(),que.end()); // 再赋值给vector数组
    }
};

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

文章链接:代码随想录

视频链接:LeetCode: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;
        int result = 1; //不为空,至少需要一支箭
        sort(points.begin(), points.end(), cmp);
        for(int i=1; i<points.size(); i++){
            // 上一个的右边界小于 当前的左边界
            if(points[i-1][1]<points[i][0]){
                result++; //
            }else{
                // 两个球重叠了,更新两个气球最小的右边界
                points[i][1] = min(points[i-1][1], points[i][1]);
            }
        }
        return result;
    }
};

文章来源:https://blog.csdn.net/m0_71413464/article/details/135625882
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。