力扣hot100——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) 的平均时间复杂度运行。

解题思路：

根据lru特性，使用哈希表+双向链表

哈希表用于查找存储区中的节点信息

双向链表：存储整个节点，由于是最久未使用页面删除，可以使用使用双向列表，最近的存储到前面，这样慢慢的就会按使用频率2（时间）将节点存储起来，每次只需要将链尾删除就行；

class LRUCache {
    // 经典实现；数据结构采用 双向链表+哈希表
    // 加入新节点就加到头，表示最新
    // 删除时就删除尾节点，就是很久不用的
    
// 双向链表结构
struct DlistNode{
    int key,val; 
    DlistNode *pre,*next; // pre指向前一个节点，next 指向后一个节点
    DlistNode() : key(-1),val(-1),pre(nullptr),next(nullptr) {}// 默认构造
    DlistNode(int _key,int _val) : key(_key),val(_val),pre(nullptr),next(nullptr) {} // 输入数据构造
};
private:
    unordered_map<int,DlistNode*> LRU_map; 
    DlistNode* head; // 头
    DlistNode* tail; // 尾
    int cap_limit; // 内存限制
public:
    LRUCache(int capacity) {
        cap_limit = capacity;
        LRU_map.clear();
        // 声明一个哑节点；用于建立后面的节点链表
        head = new DlistNode();
        tail = new DlistNode();
        head->next = tail;
        tail->next = head;
    }
    
    int get(int key) {  // 如果有再次使用则要放到最前面，再次启用
        if(LRU_map.count(key)){
            int newval = LRU_map[key]->val;
            delNode(key);
            addNode(key,newval);
            return newval;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(LRU_map.count(key)){
            delNode(key);
            addNode(key,value);
        }
        else{
            if(LRU_map.size() == cap_limit){
                delNode(tail->pre->key);  // 满了之后将最久未用的删除
                addNode(key,value);
            }
            else{
                addNode(key,value);
            }
        }
    }

    // 增加节点 (头插)
    void addNode(int key,int val){
        if(LRU_map.count(key)){  // 已经存在不增加节点
            return;
        }
        DlistNode *cur = new DlistNode(key,val);
        // 头插入 
        cur->next = head->next;
        head->next->pre = cur;
        cur->pre = head;
        head->next = cur;

        // 哈希表插入
        LRU_map[key] = cur;
    }

    // 删除节点
    void delNode(int key){
        if(!LRU_map.count(key)){  // 已经存在不增加节点
            return;
        }
        DlistNode *cur = LRU_map[key]; // 找到要删除的节点
        LRU_map.erase(key); // 删除哈希表中这个间
        
        DlistNode *front = cur->pre, *back = cur->next;
        front->next = back;
        back->pre = front;
        cur->pre = nullptr;
        cur->next = nullptr;
    }

};

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