算法刷题记录 Day30

算法刷题记录 Day30

Date: 2024.03.26

lc 452. 用最少的箭引爆游戏

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b){
        if(a[0] != b[0])
            return a[0] < b[0];     //升序
        else{
            return a[1] < b[1]; //start相同，选择更短的那个气球
        }
    }

    int findMinArrowShots(vector<vector<int>>& points) {
        // 按每个气球的x_start排序，直到遍历到的气球的x_start大于当前气球的x_end为止，该气球作为当前气球
        sort(points.begin(), points.end(), cmp);
        //int cur_start = points[0][0];
        int cur_end = points[0][1];
        int count = 1;
        for(auto& point: points){
            if(point[0] <= cur_end){
                cur_end = min(cur_end, point[1]);
            }
            else{
                cur_end = point[1];
                count++;
            }
        }
        return count;
    }
};

lc 135. 分发糖果

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();

        // 先每人一颗，然后从前往后分一遍，比前一个值大的数，多分一颗；
        // 然后再从后往前分一遍，若大的数当前的糖果数相等或小于，则再变为加1；
        vector<int> count(n, 1);
        for(int i=1; i<n; i++){
            if(ratings[i] > ratings[i-1] && count[i] <= count[i-1])
                count[i] = count[i-1] + 1;
        }

        for(int i=n-2; i>=0; i--){
            if(ratings[i] > ratings[i+1] && count[i] <= count[i+1])
                count[i] = count[i+1] + 1;
        }

        int res = 0;
        for(auto& x: count){
            res += x;
        }
        return res;
    }
};

lc 406. 根据身高重建队列

// 优化:按身高从大到小排序，则可以直接按索引插入

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b){
        if(a[0] != b[0])
            return a[0] < b[0];    
        else{
            return a[1] > b[1]; //值相同，按降序排序
        }
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        vector<vector<int>> res(people.size(), vector<int>(2, -1));
        // 先按h_i从小到大排序，再h_i相等时按k_i插空。插空时k_i的值代表了所有未被插
        // 空的位置中的第几个。
        sort(people.begin(), people.end(), cmp);  //按值升序

        for(auto& x: people){
            // 每次，遍历到第k个空格处，插入即可
            int idx = x[1] + 1;
            int i=0;
            while(idx && i<people.size()){
                if(res[i][0] == -1){
                    idx--;
                    i++;
                }
                else{
                    i++;
                }
            }
            i = i-1;
            res[i] = x;
        }
        return res;
    }
};

lc 860. 柠檬水找零

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int count_5 = 0;
        int count_10 = 0;
        for(auto& bill: bills){
            if(bill == 5)
                count_5++;
            else if(bill == 10){
                if(count_5 == 0)
                    return false;
                count_10++;
                count_5--;
            }
            else{
                if(count_10 == 0){
                    if(count_5 <3)
                        return false;
                    else{
                        count_5 -= 3;
                    }
                }
                else{
                    if(count_5 < 1)
                        return false;
                    else{
                        count_5--;
                        count_10--;
                    }
                }
            }

        }
        return true;
    }
};

原文地址：https://blog.csdn.net/qq_45542288/article/details/137224897

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！