代码随想录day35 | 860.柠檬水找零 406. 根据身高重建队列 452. 用最少数量的箭引爆气球

7月前 0 7

860.柠檬水找零

思路

这道题看上去很复杂，其实只要把每种情况写下来，答案就已经解决了。
1.收到5
2.收到10
3.收到20

实现

点击查看代码

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

复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

406. 根据身高重建队列

题目|文章

思路

需要两次贪心算法，第一次对身高进行排序，第二次按照名次进行插入。
本体可以用列表进行插入，从而减少时间复杂度，因为vector的扩容会增加时间。

实现

点击查看代码

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>> que;
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            auto it = que.begin();
            while(position --) {
                it++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>> (que.begin(), que.end());
    }
};

####复杂度分析 * 时间复杂度：O(nlogn+n^n) * 空间复杂度：O(n)

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

题目|文章

思路

本题的思路在于使得一只箭尽可能射中更多的气球。
1.使气球按照起始位置进行排序。
2.判断之后气球的起始位置是否超过当前箭射中气球的末尾位置。
特殊情况是如果该气球的末尾位置小于当前箭射中气球的末尾位置，需要对末尾位置进行更新。

实现

class Solution {
public:
int findMinArrowShots(vector<vector
>& points) {

    sort(points.begin(), points.end());
    int count = 1;
    int end = points[0][1];
    for(int i = 1; i < points.size(); i++) {
        if(points[i][1] < end) {
            end = points[i][1];
        }
        if(points[i][0] > end) {
            ++count;
            end = points[i][1];
        }

    }
    return count;
}
bool static cmp(const vector<int>& a, const vector<int>& b) {
    return a[0] < b[0];
}

};