C++ 代码

/*
 * @lc app=leetcode.cn id=146 lang=cpp
 *
 * [146] LRU缓存机制
 */

// @lc code=start
class LRUCache {
    private:
       struct Node{

           int val;
           Node* pre;
           Node* next;
       };
public:    

    //首先我们需要一个hash表
    unordered_map<int,Node*> datas;
    Node*head;
    Node*tail;
    int capa;
    LRUCache(int capacity) {
        assert(capacity>0);
        capa=capacity;
        head=nullptr;
        tail=nullptr;
    }
    void update(Node* cur){
    if(!cur){return ;}
       //更新头结点
       if(cur==head){
           return ;
       }
       if(cur==tail){
           //尾节点没有了
           tail=cur->pre;

       }else{


       Node*pre=cur->pre;
       Node*next=cur->next;
       pre->next=cur->next;
       next->pre=pre;
       }
       head->pre=cur;
       cur->next=head;
       head=cur;
       return ;
    }
    int get(int key) {
        cout<<datas.size()<<endl;
        if(datas.count(key)==0){
            return -1;
        }
        int val=datas[key]->val;
        update(datas[key]);
        return val;
    }

    void put(int key, int value) {
        if(datas.size()==capa){
            //需要进行扩容处理
            update(tail);
        }
        if(datas.count(key)>0){
            datas[key]->val=value;
            update(datas[key]);
            return ;
        }
        Node* data=new Node();
        data->val=value;
        if(!head){
            tail=head=data;
        }
        data->next=head;
        head->pre=data;
        head=data;
        datas[key]=data;
    }
};

/**
 * 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);
 */
// @lc code=end