LRU缓存

请你设计并实现一个满足LRU(最近最少使用)缓存约束的数据结构。

实现LRUCache 类：

• LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存
• int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。
• void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。

函数get和put必须以O(1)的平均时间复杂度运行。

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10^5
• 最多调用2 * 10^5次get和put

146.LRU缓存

虽然我还没学操作系统但是听说这个常考就先写了

要O(1)的时间复杂度捏，那就只能用unordered_map了捏（抠鼻屎

由于存在一个内容上浮（最近使用的节点到最前面）和尾部内容删除的需求，所以考虑双向链表。双向链表很容易写的，自己写一个就好了。

关于节点的查询，可以用哈希表来实现。哈希表的键为数据的键；键对应的值为对应节点。这样方便根据key得到节点，从而对节点进行相关操作。至于哈希表就不自己写了，柿子还是得挑软的捏

双端队列加个虚拟头尾指针比较方便操作，比如插入头部啦，删除尾部元素啦。

好像写的时候没有废太大力气，花最久时间应该在put函数那个地方，各个操作之间的顺序有点弄混的。应该先看有没有已经存在key对应的节点，有的话就改一下值上浮节点，没有的话就新增节点，再判断是否溢出。我最开始是先判断再加了，写的有点混乱也不知道脑子里面是装了什么屎

好像也没什么了，主要就是哈希+双向链表

struct DeLinkedListNode{
    DeLinkedListNode* pre;
    DeLinkedListNode* next;
    int val;
    int key;
    DeLinkedListNode(int key = 0, int val = 0): val(val), key(key), pre(nullptr), next(nullptr){};
    DeLinkedListNode(int key, int val, DeLinkedListNode* pre, DeLinkedListNode* next): val(val), key(key), pre(pre), next(next){};
};

class LRUCache {
    int capacity;
    int curr;
    DeLinkedListNode* head;
    DeLinkedListNode* tail;
    unordered_map<int, DeLinkedListNode*> keyNode;
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        curr = 0;
        head = new DeLinkedListNode();
        tail = new DeLinkedListNode();
        head->next = tail;
        tail->pre = head;
    }
    
    int get(int key) {
        if(keyNode.find(key) != keyNode.end()){
            moveToHead(keyNode[key]);
            return keyNode[key]->val;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(keyNode.find(key) != keyNode.end()){
            keyNode[key]->val = value;
            moveToHead(keyNode[key]);
            return;
        }
        DeLinkedListNode* node = new DeLinkedListNode(key, value);
        moveToHead(node);
        curr++;        
        if(curr > capacity){
            removeLast();
            curr--;
        }        
        keyNode[key] = node;
    }

    void moveToHead(DeLinkedListNode* node){
        if(node->pre && node->next){
            DeLinkedListNode* pre = node->pre;
            DeLinkedListNode* next = node->next;
            pre->next = next;
            next->pre = pre;
        }
        DeLinkedListNode* first = head->next;
        head->next = node;
        node->pre = head;
        node->next = first;
        first->pre = node;
    }

    void removeNode(DeLinkedListNode* node){
        DeLinkedListNode* preNode = node->pre;
        DeLinkedListNode* nextNode = node->next;
        preNode->next = nextNode;
        nextNode->pre = preNode;
        keyNode.erase(node->key);
        delete node;
    }

    void removeLast(){
        if(curr == 0){
            return;
        }
        DeLinkedListNode* last = tail->pre;
        removeNode(last);
    }
};

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