C++ O(1) Solution beats 83%


  • 0
    J
    
    struct Node{
      int key;
      int val;  
      Node* prev;
      Node* next;
      Node(int k = -1,int v = -1, Node* p = nullptr, Node* n = nullptr) : key{k},val{v},prev{p},next{n} {}
        
    };
    
    
    
    class LRUCache{
        
    private:
        int cap;
        int size;
        Node* head;
        Node* tail;
        unordered_map<int,Node*> map;
        void push_back(Node* node){
            size++;
            Node* cur = node;
            
            if(tail == nullptr)
                head = tail = cur;
            else {
                tail->next = cur;
                cur->prev = tail;
                tail = cur;
            }
        }
        
        void pop_front(){
            
            if(head == nullptr) return;
            
            size--;
            int key;
            if(head == tail){
                key = head->key;
                delete head;
                head = tail = nullptr;
            } else {
                Node* cur = head;
                key = cur->key;
                head = head->next;
                delete cur;
            }
            
            map.erase(key);
        }
        
        void move_to_back(Node* node){
            
            if(node == tail) return;
            if(head == node)
                head = head->next;
             else {
                node->prev->next = node->next;
                node->next->prev = node->prev;
            }
            tail->next = node;
            node->prev = tail;
            tail = node;
        }
        
        
    public:
        LRUCache(int capacity) {
            cap = capacity;
            size = 0;
            head = tail = nullptr;
        }
        
        int get(int key) {
        
            if(map.find(key) == map.end())
                return -1;
            
            Node* cur = map[key];
            move_to_back(cur);
            
            return cur->val;
        }
        
        void set(int key, int value) {
            
            if(get(key) == -1){
                Node* cur = new Node(key,value);
                if(size == cap)
                    pop_front();
                map[key] = cur;
                push_back(cur);
            } else 
                map[key]->val = value;
        }
    };
    

Log in to reply
 

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