Leetcode_20 天编程能力基础_day17

要没了。

1845. Seat Reservation Manager

Analysis

题目的意思很直接，从 reverse 函数的功能来看，就是最小堆的出堆操作了。所以，这个题是要构造最小堆。

Code

堆的功能可以直接用优先队列来完成。
C++ 的优先队列默认是大根堆，如果要用小根堆就得写成priority_queue<int, vector<int>, greater<int>> q;，其中第二个参数就是优先队列的底层数据结构，而第三个参数表示值越小越优先，对应的less<int>则表示值越大越优先。

class SeatManager {
    priority_queue<int, vector<int>, greater<int>> q;
public:
    SeatManager(int n) {
        for(int i = 1; i <= n; i++) {
            q.push(i);
        }
    }
    
    int reserve() {
        int tmp = q.top();
        q.pop();
        return tmp;
    }
    
    void unreserve(int seatNumber) {
        q.push(seatNumber);
    }
};

860. Lemonade Change

Analysis

默认的找钱规则是能找大的尽量找大的，所以这是一个跟贪心相关的问题。用 2 个变量来记录能被找出去的 5 块和 10 块的数目，模拟找钱。如果顾客给了 20 块，此时有两种找钱方法，但是得按照规则来进行。一旦某个变量为负了，说明没办法正确找零。

Code

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

Summary

第一个题如果要是自己写堆，估计挺废劲的😂。
第二个题还 WA 了一次，有点亏...

---