AC截图

题目

思路

可以构造一个双向链表，使用dummy作为哨向结点。

①定义结点

class Node{
public:int key;int value;Node* prev;Node* next;Node(int k=0,int v=0):key(k),value(v){}
};

LRUCache类

②定义参数列表

    int capacity;Node* dummy;unordered_map<int,Node*> key_to_node;

③删除节点

    void remove(Node *x){x->prev->next = x->next;x->next->prev = x->prev;}

④将结点置顶

对于插入节点，无论键值是否存在，都需要将该结点置顶，因为如果容量过载，LRU会删除最底部的结点。而该结点现在被访问，应该更新为最新的结点

    void push_front(Node *x){x->prev = dummy;x->next = dummy->next;x->prev->next = x;x->next->prev = x;}

⑤获取结点

如果键不存在，则返回空

如果键存在，则将该结点置顶（先删除，再放入顶部），然后返回结点

    Node* get_node(int key){auto it = key_to_node.find(key);if(it==key_to_node.end()){return NULL;}Node* node = it->second;remove(node);push_front(node);return node;}

⑥LRUCache初始化

    LRUCache(int capacity):capacity(capacity),dummy(new Node()) {dummy->prev = dummy;dummy->next = dummy;}

⑦获取结点

    int get(int key) {Node* node = get_node(key);return node?node->value:-1;}

⑧插入节点

如果键存在，则修改值

如果键不存在：

        以传入的键值构造新结点，更新unordered_map

        将新结点置顶

        判断容量是否过载：

                如果过载，删除最底部结点，更新unordered_map

    void put(int key, int value) {Node* node = get_node(key);if(node){node->value = value;return ;}key_to_node[key] = node = new Node(key,value);push_front(node);if(key_to_node.size()>capacity){Node* back_node = dummy->prev;key_to_node.erase(back_node->key);remove(back_node);delete back_node;}}

完整代码

class Node{
public:int key;int value;Node* prev;Node* next;Node(int k=0,int v=0):key(k),value(v){}
};class LRUCache {
private:int capacity;Node* dummy;unordered_map<int,Node*> key_to_node;void remove(Node *x){x->prev->next = x->next;x->next->prev = x->prev;}void push_front(Node *x){x->prev = dummy;x->next = dummy->next;x->prev->next = x;x->next->prev = x;}Node* get_node(int key){auto it = key_to_node.find(key);if(it==key_to_node.end()){return NULL;}Node* node = it->second;remove(node);push_front(node);return node;}public:LRUCache(int capacity):capacity(capacity),dummy(new Node()) {dummy->prev = dummy;dummy->next = dummy;}int get(int key) {Node* node = get_node(key);return node?node->value:-1;}void put(int key, int value) {Node* node = get_node(key);if(node){node->value = value;return ;}key_to_node[key] = node = new Node(key,value);push_front(node);if(key_to_node.size()>capacity){Node* back_node = dummy->prev;key_to_node.erase(back_node->key);remove(back_node);delete back_node;}}
};/*** 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);*/