题解 | #设计LRU缓存结构#

class Solution {
public:
    struct Node
    {
        int key,val;
        Node *left,*right;
        Node(int _key,int _val):key(_key),val(_val),left(NULL),right(NULL){}
    }*L,*R;
    Solution(){ //初始化
        L=new Node(-1,-1);
        R=new Node(-1,-1);
        L->right=R;
        R->left=L;
    }
    vector<int>res;
    unordered_map<int,Node*>hash;//哈希表来快速查找
    int n;//总容量
    void insert(Node *p)//插入一页
    {
        p->right=L->right;
        L->right->left=p;
        L->right=p;
        p->left=L;
    }
    void remove(Node *p)//删除
    {
        p->left->right=p->right;
        p->right->left=p->left;
    }
    void get(int key)
    {
        if(hash.count(key)==0)
        {
            res.push_back(-1);
            return;
        }
        auto p=hash[key];
        remove(p);
        insert(p);
        res.push_back(p->val);
    }
    void set(int key,int value)
    {
        //如果有了，那就修改值
        if(hash.count(key))
        {
            auto p=hash[key];
            p->val=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);
        }

    }
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        n=k;
        for(int i=0;i<operators.size();i++)
        {
            if(operators[i][0]==1)
                set(operators[i][1],operators[i][2]);
            else 
                get(operators[i][1]);
        }
        return res;
    }
};