C++ 152ms AC solution using ListNode


  • 0
    A
    class LRUCache{
    private:
        // ListNode contains the values
        struct ListNode {
            int val;
            int key;
            ListNode *next;
            ListNode *prev;
            ListNode(int x, int y) : val(x), key(y), next(NULL), prev(NULL) {}
            
        };
        ListNode* MyDB = new ListNode(0,-1);
        ListNode* cur = MyDB;
        int MyDB_size;
        int MAX_size;
        void erase(ListNode* node){
            node->prev->next = node->next;
            if(node->next) node->next->prev = node->prev;
            if(cur == node) cur = node->prev;
        }
        void insert_v(int value, int key){
            cur->next = new ListNode(value, key);
            cur->next->prev = cur;
            cur = cur->next;
            m[key] = cur;
        }
        void insert_n(ListNode* node){
            cur->next = node;
            node->prev = cur;
            node->next = NULL;
            cur = cur->next;
            
        }
        // map contains key and where the address of the ListNode with value
        map<int, ListNode*> m;
        
    public:
        LRUCache(int capacity) {
            MAX_size = capacity;
            MyDB_size = 0;
        }
        
        int get(int key) {
            if(m.find(key) == m.end()) return -1;
            erase(m[key]);
            insert_n(m[key]);
            return m[key]->val;
        }
        
        void set(int key, int value) {
            if(get(key) != -1){
                m[key]->val = value;
            } else if(MyDB_size == MAX_size){
                int erase_key = MyDB->next->key;
                erase(MyDB->next);
                m.erase(erase_key);
                insert_v(value, key);
            } else{
                insert_v(value, key);
                MyDB_size++;
            }
        }
    };
    

Log in to reply
 

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