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

class Solution {
public:

struct ListNode
{
    int key;int value;
    ListNode* prev;
    ListNode* next;
    ListNode():key(0),value(0),prev(nullptr),next(nullptr){};
    ListNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){};
};

struct myLRU
{
private: 
    int size;
    int capacity;
    ListNode* head;
    ListNode* tail;
    unordered_map<int,ListNode* > map;

public:
    myLRU(int k):capacity(k),size(0)
    {
        head=new ListNode();
        tail=new ListNode();
        head->next=tail;
        tail->prev=head;
        //size=0;
    }

    void addtohead(ListNode* node)
    {
        node->prev=head;
        node->next=head->next;
        head->next->prev=node;
        head->next=node;
    }
    void removenode(ListNode* node)
    {
        node->prev->next=node->next;
        node->next->prev=node->prev;
    }
    void movetohead(ListNode* node)
    {
        removenode(node);
        addtohead(node);
    }
    ListNode* removetail()
    {
        ListNode* node=tail->prev;
        removenode(node);
        return node;
    }

    int get(int key)
    {
        if(!map.count(key)){return -1;}
        //如果KEY存在，通过哈希表定位，然后移动到头部
        ListNode* node=map[key];
        movetohead(node);
        return node->value;
    }

    void put(int key,int value)
    {
        if(!map.count(key))
        {
            //如果key不存在，创建一个新的节点
            ListNode* node=new ListNode(key,value);
            //添加进哈希表
            map[key]=node;
            addtohead(node);
            size++;

            if(size>capacity)
            {
                //超出了容量，删除双向链表的尾部节点
                ListNode* removed=removetail();
                //删除哈希表中对应的项
                map.erase(removed->key);
                //防止内存泄漏 可有可无
                delete removed;
                size--;
            }

        }
        else
        {
            //如果key存在，先通过哈希表定位，再修改value，并移动到头部
            ListNode* node=map[key];
            node->value=value;
            movetohead(node);
        }
    }
};



vector<int> LRU(vector<vector<int> >& operators, int k) {
    // write code here
    vector<int> result;
    myLRU mylru(k);
    for(int i=0;i<operators.size();i++)
    {
        if(operators[i][0]==1)
        {
            mylru.put(operators[i][1], operators[i][2]);
        }
        else if(operators[i][0]==2)
        {
            int val=mylru.get(operators[i][1]);
            result.push_back(val);
        }
    }
    return result;
}

};