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

#include <type_traits>
class Solution {
public:
    struct Node{
        int key,value;
        Node *pre,*next;
        Node(int k,int v):key(k),value(v),pre(nullptr),next(nullptr){}
    };
    unordered_map<int,Node*>mp;
    Node* l,*r;
    int n;
 Solution(int capacity){
 // write code here
 n=capacity;
 l=new Node(-1,0);
 r=new Node(0,0);
 l->next=r;
 r->pre=l;
 }
 
 int get(int key) {
 // write code here
 if(mp.count(key)){
    Node* node=mp[key];
    remove(node);
    headnode(node->key,node->value);
    return node->value;
 }else{
    return -1;
 }
 }

 void set(int key, int value){
 // write code here
 if(mp.count(key)){
    Node* node=mp[key];
    remove(node);
    headnode(key,value);
 }else{
    if(mp.size()==n){
        Node* node1=l->next;
        remove(node1);
        headnode(key,value);
    }else{
        headnode(key,value);
    }
 }
 }
 void remove(Node* node){
    Node* prev=node->pre;
    Node* nxt=node->next;

    prev->next=nxt;
    nxt->pre=prev;
    mp.erase(node->key);
 }

 void headnode(int key,int value){
    Node* prev=r->pre;
    Node* new_node=new Node(key,value);
    prev->next=new_node;
    new_node->next=r;

    r->pre=new_node;
    new_node->pre=prev;

    mp[new_node->key]=new_node;

 }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */