LeetCode 146. LRU 缓存

LeetCode 146. LRU 缓存

思路：

使用双向链表和哈希表来维护LRU机制，如果没有这个结点就把它插入到链表头部，同时哈希表中也加入这个点，如果有这个结点则修改value，同时移动到链表的头部，表示最近一次使用，如果在插入的时候超过了capacity，则把链表尾部的结点删除，让出位置插入新的结点，表示很久未使用的结点被删除。

代码：

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

    }*L,*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;
        auto p = hash[key];
        //删除节点 把结点移动到链表的头部
        remove(p);
        insert(p);
        return p->value;
    }
    
    void put(int key, int value) {
        if(hash.count(key)){
            auto p = hash[key];
            p->value = value;
            remove(p);
            insert(p);
        }
        else{
            //超过容量
            if(n == hash.size()){
                auto p = R->left;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            //创建新的结点
            auto p = new Node(key,value);
            hash[key] = p;
            insert(p);
        }
    }

    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;
    }
};

/**
 * 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);
 */