Design Phone Directory - Thiết kế danh bạ điện thoại

Thiết kế một danh bạ điện thoại hỗ trợ các thao tác:

• get(): cấp phát một số chưa được gán.
• check(number): kiểm tra số có khả dụng không.
• release(number): giải phóng/trả lại số.

Khởi tạo với maxNumbers số (0 đến maxNumbers-1).

Giải thuật

Sử dụng hàng đợi available lưu các số trống, và tập hợp used lưu các số đang dùng. get() lấy từ hàng đợi, check() tra trong tập hợp, release() trả về hàng đợi nếu số đang được dùng.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class PhoneDirectory {
public:
    set<int> used;
    queue<int> available;
    int N;

    PhoneDirectory(int maxNumbers) {
        N = maxNumbers;
        for (int i = 0; i < N; i++)
            available.push(i);
    }

    int get() {
        if (available.empty()) return -1;
        int x = available.front();
        used.insert(x);
        available.pop();
        return x;
    }

    bool check(int number) {
        if (number >= N || number < 0) return false;
        return used.find(number) == used.end();
    }

    void release(int number) {
        if (check(number)) return;
        used.erase(number);
        available.push(number);
    }
};

int main() {
    PhoneDirectory ob(3);
    cout << ob.get() << endl;   // 0
    cout << ob.get() << endl;   // 1
    cout << ob.check(2) << endl; // 1 (true)
    cout << ob.get() << endl;   // 2
    cout << ob.check(2) << endl; // 0 (false)
    ob.release(2);
    cout << ob.check(2) << endl; // 1 (true)
    return 0;
}

Đầu vào

ob.get(); ob.get(); ob.check(2); ob.get(); ob.check(2); ob.release(2); ob.check(2);

Đầu ra

0 1 1 2 0 1