Leetcode-146: LRU cache

subject

Topic linking

Please design and implement a meeting LRU ( Recently at least use ) cache Constrained data structure .
Realization LRUCache class ：

• LRUCache(int capacity) With Positive integer As capacity capacity initialization LRU cache
• int get(int key) If the keyword key In the cache , The value of the keyword is returned , Otherwise return to -1 .
• void put(int key, int value) If the keyword key Already exist , Change its data value value ; If it doesn't exist , Then insert the group into the cache key-value . If the insert operation causes the number of keywords to exceed capacity , Should be Eviction The longest unused keyword .

function get and put Must be O(1) The average time complexity of running .

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); //  The cache is  {1=1}
lRUCache.put(2, 2); //  The cache is  {1=1, 2=2}
lRUCache.get(1);    //  return  1
lRUCache.put(3, 3); //  This operation causes the keyword to  2  To void , The cache is  {1=1, 3=3}
lRUCache.get(2);    //  return  -1 ( Not found )
lRUCache.put(4, 4); //  This operation causes the keyword to  1  To void , The cache is  {4=4, 3=3}
lRUCache.get(1);    //  return  -1 ( Not found )
lRUCache.get(3);    //  return  3
lRUCache.get(4);    //  return  4

Problem solving

Method 1 ： Double linked list + Hash

struct Node{
    
    int key,value;
    Node* left;
    Node* right;
    Node(int _key,int _value):key(_key),value(_value),left(nullptr),right(nullptr){
    }
};

class LRUCache {
    
public:
    Node* L;
    Node* R;
    int n;
    unordered_map<int,Node*> hash;

    LRUCache(int capacity) {
    
        n=capacity;
        L=new Node(-1,-1);
        R=new Node(-1,-1);
        L->right=R;
        R->left=L;
    }
    
    int get(int key) {
    
        if(hash.count(key)==0) return -1;
        Node* p=hash[key];
        remove(p);
        insert(p);
        return p->value;
    }
    
    void put(int key, int value) {
    
        if(hash.count(key)){
    // If key There is , Then modify the corresponding value
            Node* p=hash[key];
            p->value=value;
            remove(p);
            insert(p);
        }else{
    
            if(hash.size()==n){
    // If the cache is full , Delete the rightmost node of the double linked list 
                Node* p=R->left;
                remove(p);
                hash.erase(p->key);// Update hash table 
                delete p;
            }
            // Insert a new node 
            Node* p=new Node(key,value);
            hash[key]=p;
            insert(p);
        }
    }
    void remove(Node* p){
    
        p->right->left=p->left;
        p->left->right=p->right;
    }
    void insert(Node* p){
    
        p->right=L->right;
        L->right->left=p;
        L->right=p;
        p->left=L;
    }
};