Title Description
Using the data structure you have mastered, design and implement an LRU (least recently used) caching mechanism. Implement LRUCache class:
LRUCache(int capacity) initializes LRU cache with positive integer as capacity
int get(int key): if the keyword key exists in the cache, the value of the keyword is returned; otherwise, - 1 is returned.
void put(int key, int value) if the keyword already exists, change its data value; If the keyword does not exist, insert the group keyword value. When the cache capacity reaches the maximum, it should delete the longest unused data value before writing new data, so as to make room for new data values.

Advanced: can you complete these two operations within O(1) time complexity?

Example:
input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
output
[null, null, null, 1, null, -1, null, -1, 3, 4]

explain
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // Cache is {1 = 1}
lRUCache.put(2, 2); // Cache is {1 = 1, 2 = 2}
lRUCache.get(1); // Return 1
lRUCache.put(3, 3); // This operation will invalidate keyword 2. The cache is {1 = 1, 3 = 3}
lRUCache.get(2); // Return - 1 (not found)
lRUCache.put(4, 4); // This operation will invalidate keyword 1, and the cache is {4 = 4, 3 = 3}
lRUCache.get(1); // Return - 1 (not found)
lRUCache.get(3); // Return 3
lRUCache.get(4); // Return 4

Tsinghua operating system video

Due to the high time complexity of out and in stack, double linked list is used to store pages and hash table is used to save key value pairs.

• When inserting a new page, you need to judge whether the page exists in the double linked list. If it exists, delete the page and insert it into the front of the linked list. When inserting, the double linked list exceeds the size of the cache given by the cache, you need to delete the last page, delete the last page in the double linked list, and delete the corresponding key value pair in the hash table.
• When accessing a page, if the page does not exist, return - 1. If the page exists, you need to return the value of the page. Note that after accessing the page, you need to delete the page and put it at the front of the double linked list. Because visiting a page means that the page has also been manipulated.

class LRUCache {
public:
    struct Node{
        int key,val;
        Node *left,*right;
        Node(int _key,int _val):key(_key),val(_val),left(NULL),right(NULL){}
    }*L,*R;
    unordered_map<int,Node*> hash;
    int n;
    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1,-1),R = new Node(-1,-1);
        L->right=R,R->left=L;
    }
    void remove(Node *p)
    {
        p->left->right=p->right;
        p->right->left=p->left;    
    }
    void insert(Node *p)
    {
        p->right=L->right;
        p->left=L;
        L->right->left=p;
        L->right=p;
    }

    int get(int key) {
        if(hash.count(key)==0) return -1;
        auto p = hash[key];
        remove(p);
        insert(p);
        return p->val;
    }
    
    void put(int key, int value) {
        if(hash.count(key))
        {
            auto p = hash[key];
            p->val=value;
            remove(p);
            insert(p);
        }
        else 
        {
            if(hash.size()==n) 
            {
                auto p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            auto p = new Node(key,value);
            hash[key]=p;
            insert(p);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */