题解 | #LRU Cache#

#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;

class LRUCache
{
private:
    struct LRUNode                                      //使用双向链表+哈希表组合实现LRU
    {
        int key, val;
        LRUNode* pre;
        LRUNode* next;
        LRUNode(int k, int v) : key(k), val(v){
            pre = nullptr;
            next = nullptr;
        }
    };
    int capacity;
    int num = 0;
    unordered_map<int, LRUNode*> LRUHashMap;
    LRUNode* head;
    LRUNode* tail;

    void DeleteKey(LRUNode* node ,int k)
    {
        --num;
        node -> pre -> next = node -> next;
        node -> next -> pre = node -> pre;
        delete node;
        LRUHashMap.erase(k);
    }

    void InsertKey(LRUNode* node, int k)                  //每次插入都在列尾
    {
        ++num;
        node -> pre = tail -> pre;
        node -> next = tail;

        tail -> pre = node;
        node -> pre -> next = node;
        
        LRUHashMap[k] = node;
    }
public:
    LRUCache(int cap)
    {
        capacity = cap;
        head = new LRUNode(-1, -1);
        tail = new LRUNode(-1, -1);
        head -> next = tail;
        tail -> pre = head;
    }

    int get(int key)
    {
        if(!LRUHashMap.count(key))
        return -1;
        LRUNode* node1 = LRUHashMap[key];
        int val = node1 -> val;
        DeleteKey(node1, key);
        LRUNode* node2;
        node2 = new LRUNode(key, val);
        InsertKey(node2, key);
        return val;
    }

    void put(int key, int value)
    {
        if(capacity == 0)                            //容积为0时不参与put函数，防止列表越界
        return;
        if(LRUHashMap.count(key))
        {
            LRUNode* node1 = LRUHashMap[key];
            node1 -> val = value;
            return;
        }
        else if(num == capacity)
        {
            DeleteKey(head -> next, head -> next -> key);         //快要溢出时，删除列首节点
        }
        LRUNode* node2;
        node2 = new LRUNode(key, value);
        InsertKey(node2, key);
        return;
    }
};

int main() {
    int cap;
    cin >> cap;
    LRUCache MyLRUCache(cap);
    char fun;
    int key, value;
    while (cin >> fun) { 
        if(fun == 'p')
        {
            cin >> key >> value;
            MyLRUCache.put(key, value);
        }
        else if(fun == 'g')
        {
            cin >> key;
            int res = MyLRUCache.get(key);
            cout << res << endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")