C++, two array solution.


  • 11

    Use vector<int> to store free list and use vector<bool> to check if the number is in free list.
    all functions take O(1) except initialization.
    ...

    vector<int> freeList;
    vector<bool> freeHT;
    int index, count;
    
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers) : index(0), count(maxNumbers), freeList(maxNumbers), freeHT(maxNumbers, true){
        for (int i = 0; i < maxNumbers; ++i) {
            freeList[i] = i;
        }
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        int n = -1;
        if (index < count) {
            n = freeList[index++];
            freeHT[n] = false;
        }
        return n;
    }
    
    /** Check if a number is available or not. */
    bool check(int number) {
        if (number < 0 || number >= count) {
            return false;
        }
        return freeHT[number];
    }
    
    /** Recycle or release a number. */
    void release(int number) {
        if (number < 0 || number >= count || freeHT[number]) {
            return;
        }
        freeList[--index] = number;
        freeHT[number] = true;
    }

  • 1
    Z

    I like the trick of freeList[--index] = number;
    That is neat!


  • 1
    Y

    Nice solution. The only thing I don't like is O(n) space. I think the we are suppose to use a link list of currently available chunks, e.g, [1, 5]->[9, 18]->[20,100]...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.