72ms C++ solution using hashtable and double linked list.


  • 0
    B
    struct LinkedListNode{
        int key;
        int value;
        LinkedListNode * prev, * next;
        LinkedListNode(int k, int v, LinkedListNode * p, LinkedListNode * n):key(k), value(v), prev(p), next(n){}
    };
    class LRUCache{
    private:
        int capacity;
        int size;
        LinkedListNode * head;
        LinkedListNode * tail;
        unordered_map<int, LinkedListNode*> mapping;
    public:
        LRUCache(int _capacity) {
            capacity = _capacity;
            size = 0;
            head = new LinkedListNode(0, 0, nullptr, nullptr);
            tail = head;
        }
        ~LRUCache(){
            delete head;
        }
        int get(int key) {
            auto iter = mapping.find(key);
            if(iter != mapping.end()){
                moveToHead(iter->second);
                return iter->second->value;
            }
            return -1;
        }
        
        void set(int key, int value) {
            auto iter = mapping.find(key);
            if(iter != mapping.end()){
                moveToHead(iter->second);
                iter->second->value = value;
            }else{
                auto newNode = new LinkedListNode(key, value, nullptr, nullptr);
                if(size>=capacity) deleteTail();
                ++size;
                
                if(head==tail) tail = newNode;
                
                newNode->next = head->next;
                if(head->next)head->next->prev = newNode;
                newNode->prev = head;
                head->next = newNode;
                mapping[key] = newNode;
            }
        }
        void moveToHead(LinkedListNode * node){
            if(node == head->next) return;
            if(node == tail){
                tail = tail->prev;
                tail->next = nullptr;
            }
            
            node->prev->next = node->next;
            if(node->next) node->next->prev = node->prev;
            
            node->next = head->next;
            node->prev = head;
            head->next->prev = node;
            head->next = node;
        }
        void deleteTail(){
            --size;
            mapping.erase(tail->key);
            tail = tail->prev;
            delete tail->next;
            tail->next = nullptr;
        }
    };

Log in to reply
 

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