C++ solution with 2 linked list nodes and 1d array


  • 0
    T

    The idea is to maintain the released numbers with a linked list, and used 1d array to check if current number is available.
    get will return head node of the list and delete it afterward, if list is not null, otherwise will allocate a new number;
    release will insert a new node to the tail of the list

    typedef struct Recycled {
        int val;
        Recycled *next;
        Recycled(int v):val(v), next(NULL){}
    };
    class PhoneDirectory {
        int maxNum, curNum;
        Recycled *Head, *Tail; // store released number set
        bool *bUsed;   // check if available
    public:
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        PhoneDirectory(int maxNumbers):maxNum(maxNumbers), curNum(0) {
            Head = new Recycled(0), Tail = Head;
            bUsed = new bool[maxNumbers];
            memset(bUsed, 0, sizeof(bUsed));
        }
        ~PhoneDirectory() {
            delete []bUsed;
            while (Head) {
                Recycled *n = Head->next;
                delete Head; Head = n;
            }
        }
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        int get() {
            if (curNum == maxNum && Head->next == NULL)
                return -1;
            if (Head->next) {
                Recycled *n = Head->next;
                Head->next = n->next, bUsed[n->val] = true;
                if (n == Tail) Tail = Head; // list will be empty
                int v = n->val;
                delete n;
                return v;
            }
            bUsed[curNum] = true;
            return curNum++;
        }
        
        /** Check if a number is available or not. */
        bool check(int number) {
            return number >= 0 && number <= maxNum && !bUsed[number];
        }
        
        /** Recycle or release a number. */
        void release(int number) {
            if (number < 0 || number > maxNum || !bUsed[number])
                return;
                
            Tail->next = new Recycled(number);
            Tail = Tail->next;
            bUsed[number] = false;
        }
    };
    

Log in to reply
 

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