C++ link list solution


  • 0
    Y

    I saw many posts using O(maxNumbers) space. Here I offer a link list approach that consumes less space. The idea is simple: maintaining a link list of available chunks, e.g., [0,9]->[15,19]->[21,100]...

    class Record {
    public:
        Record(int b, int e) { beg = b; end = e; next = NULL; }
        int beg, end;   // available numbers [beg, end]
        Record *next;
    };
    
    class PhoneDirectory {
    public:
        /** Initialize your data structure here
            @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
        PhoneDirectory(int maxNumbers) {
            if (maxNumbers < 1) head = NULL;
            else head = new Record(0, maxNumbers - 1);
        }
        
        /** Provide a number which is not assigned to anyone.
            @return - Return an available number. Return -1 if none is available. */
        int get() {
            if (!head) return -1;
            int res = head->beg;
            if (++head->beg > head->end) {
                Record *tmp = head->next;
                delete head;
                head = tmp;
            }
            return res;
        }
        
        /** Check if a number is available or not. */
        bool check(int number) {
            Record *p = head;
            while (p) {
                if (number >= p->beg && number <= p->end) return true;
                else if (number < p->beg) break;
                p = p->next;
            }
            return false;
        }
        
        /** Recycle or release a number. */
        void release(int number) {
            Record *p = head, *pre = NULL, *next;
            while (p) {
                next = p->next;
                
                if (number < p->beg - 1) {
                    break;
                }
                else if (number == p->beg - 1) {
                    p->beg--;
                    return;
                }
                else if (number >= p->beg && number <= p->end) {
                    return;  // this number has not been assigned yet
                }
                else if (number == p->end + 1) {
                    p->end++;
                    if (next && p->end == next->beg) {
                        p->end = next->end;
                        p->next = next->next;
                        delete next;
                    }
                    return;
                }
                else {
                    pre = p;
                    p = next;
                }
            }
            
            Record *node = new Record(number, number);  // need a new node
            node->next = p;
            
            if (!pre) head = node;
            else pre->next = node;
        }
        
    private:
        Record *head;
    };
    

Log in to reply
 

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