C++ Double Linked List Solution


  • 0
    B

    Use bool array for check function, and use double linked list for get, release functions.

    struct DoubleListNode {
    DoubleListNode* next;
    DoubleListNode* prev;
    int val;
    DoubleListNode(int x) : val(x), prev(NULL), next(NULL) {}
    };

    class PhoneDirectory {
    public:
    /** Initialize your data structure here
    @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers) {

        numbers = new bool[maxNumbers]();
        max = maxNumbers - 1;
        head = new DoubleListNode(-1);
        nxt = head;
        for (int i = maxNumbers - 1; i >= 0; i --)
        {
            nxt -> next = new DoubleListNode(i);
            nxt -> next -> prev = nxt;
            nxt = nxt -> next;
        }
        
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        
        int val = nxt -> val;
        if (val == -1)
            return -1;
        nxt = nxt -> prev;
        delete nxt->next;
        nxt-> next = NULL;
        numbers[val] = true;
        return val;
        
    }
    
    /** Check if a number is available or not. */
    bool check(int number) {
        if (number > max || numbers[number])
            return false;
            
        return true;
    }
    
    /** Recycle or release a number. */
    void release(int number) {
        
        if (numbers[number])
        {
            nxt -> next = new DoubleListNode(number);
            nxt -> next -> prev = nxt;
            nxt = nxt -> next;
            numbers[number] = false;
        }
    }
    

    private:
    bool* numbers;
    int max;
    DoubleListNode* head;
    DoubleListNode* nxt;
    };


  • 0
    B

    Sorry, I'm new to the posting format, somehow, only part of the codes gets displayed in the correct format.


Log in to reply
 

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