LRU 缓存结构 （c++ 哈希双链表实现）

LRU 缓存结构

题目描述：

设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能

• set(key, value)：将记录(key, value)插入该结构
• get(key)：返回key对应的value值

[要求]

1. set和get方法的时间复杂度为O(1)
2. 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
3. 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。

若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案

示例1
输入

[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

输出

[1,-1]

说明

第一次操作后：最常使用的记录为(“1”, 1)
第二次操作后：最常使用的记录为(“2”, 2)，(“1”, 1)变为最不常用的
第三次操作后：最常使用的记录为(“3”, 2)，(“1”, 1)还是最不常用的
第四次操作后：最常用的记录为(“1”, 1)，(“2”, 2)变为最不常用的
第五次操作后：大小超过了3，所以移除此时最不常使用的记录(“2”, 2)，加入记录(“4”, 4)，并且为最常使用的记录，然后(“3”, 2)变为最不常使用的记录

备注:

1 ≤ K ≤ N ≤ 1 0 5 1 \leq K \leq N \leq 10^5 1≤K≤N≤105
− 2 × 1 0 9 ≤ x , y ≤ 2 × 1 0 9 -2 \times 10^9 \leq x,y \leq 2 \times 10^9 −2×109≤x,y≤2×109

题解：

开始初始化一个head节点与一个tail节点，方便以后插入节点和删除节点，中间放置操作的节点。

1. [1,1,1] 当我们遇到第一个set方法的时候 就需要插入到head 和tail 之间，
   

2. [1,2,2] 这时我们需要将新节点插入到head与node(1,1)之间。
   

3. [1,3,2] 添加到head后面；
   

4. [2,1] 发现已经有key=1对应的节点；则把Node(1,1)移动到head后面；
   

5. [1,4,4] 这时候发现节点的数量已经达到内存上限，则需要把最不常用的节点Node(2,2)删除，把新节点插入到head后面；
   

6. [2,2] 这时候查找节点发现没有，则返回-1；

代码：

#include <unordered_map>
 
struct DListNode{ 
    int key, val;
    DListNode* pre;
    DListNode* next;
    DListNode(int k, int v): key(k), val(v), pre(nullptr), next(nullptr){ };
};
 
 
class Solution { 
private:
    int size = 0;
    DListNode* head;
    DListNode* tail;
    unordered_map<int, DListNode*> mp;
 
public:
    /** * lru design * @param operators int整型vector<vector<>> the ops * @param k int整型 the k * @return int整型vector */
    vector<int> LRU(vector<vector<int> >& operators, int k) { 
        // write code here
        if(k < 1) return { };
        this->size = k;
        this->head = new DListNode(0,0);
        this->tail = new DListNode(0,0);
        this->head->next = this->tail;
        this->tail->pre = this->head;
 
        if(operators.size() == 0) return { };
 
        vector<int> res;
 
        for(vector<int> op : operators){ 
            if(op[0] == 1) { 
                set(op[1], op[2]);
            }
            else if(op[0] == 2){ 
                int value = get(op[1]);
                res.push_back(value);
            }
        }
        return res;
    }
 
    void set(int key, int val){ 
        if(mp.find(key) == mp.end()){  // hashmap 中没找到
            DListNode* node = new DListNode(key, val);
            mp[key] = node;
            if(this->size <= 0){ 
                removeLast();
            }
            else{ 
                this->size--;
            }
            insertFirst(node);
        }
        else{   // hashmap 中已经有了，也就是链表里也已经有了
            mp[key]->val = val;
            moveToHead(mp[key]);
        }
    }
 
 
    int get(int key){ 
        int ret = -1;
        if(mp.find(key) != mp.end()){ 
            ret = mp[key]->val;
            moveToHead(mp[key]);
        }
        return ret;
    }
 
    void moveToHead(DListNode* node){ 
        if(node->pre == this->head) return;
        node->pre->next = node->next;
        node->next->pre = node->pre;
        insertFirst(node);
    }
 
 
    void removeLast(){ 
        mp.erase(this->tail->pre->key);
        this->tail->pre->pre->next = this->tail; // remove the last node in dlist
        this->tail->pre = this->tail->pre->pre;
    }
 
    void insertFirst(DListNode* node){ 
        node->pre = this->head;
        node->next = this->head->next;
        this->head->next->pre = node;
        this->head->next = node;
    }
 
};