[cpp] Solution 64ms(98.95%) with unordered_map and double-linked node, neat and easy readable code.


  • 0
    #include <iostream>
    #include <unordered_map>
    
    using namespace std;
    
    struct Node {
        int key;
        int value;
        Node* next;
        Node* prev;
        Node(int k, int v) : key(k), value(v), prev(NULL), next(NULL){}
    };
    
    class LRUCache{
        
    public:
        LRUCache(int capacity) :cp(capacity), cur(0), head(NULL), tail(NULL){ }
        
        int get(int key) {
            unordered_map<int, Node*>::const_iterator it = map.find(key);
            if(it != map.end()) {
                Node* node = it->second;
                moveNodeToHead(node);
                return node->value;
            }
            return -1;
        }
    
        void moveNodeToHead(Node* node) {
            if(node == head) {
                return;
            }
    
            if(node == tail) {
                tail = node->prev;
                node->prev->next = NULL;
            } else {
                node->prev->next = node->next;
                node->next->prev = node->prev;
            }
    
            node->next = head;
            head->prev = node;
            node->prev = NULL;
            head = node;
        }
    
        void set(int key, int value) {
            unordered_map<int, Node*>::const_iterator it = map.find(key);
            if(it != map.end()) {
                Node* node = it->second;
                node->value = value;
                moveNodeToHead(node);
            } else {
                if(cur >= cp) {
                    Node* tmp = tail;
                    map.erase(tmp->key);
                    if(tail->prev != NULL) {
                        tail = tail->prev;
                        tail->next = NULL;
                    }
                    delete tmp;
                } else {
                    cur++;
                }
    
                Node* node = new Node(key, value);
                node->next = head;
                if(head != NULL) {
                    head->prev = node;
                }
                head = node;
                if(cur == 1) {
                    tail = node;
                } 
                map[key] = node;
            }
        }
    
    private:
        Node* head;
        Node* tail;
        int cp;
        int cur;
        unordered_map<int, Node*> map;
    };
    

Log in to reply
 

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