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

#include <cfloat>
class Solution {
public:
 
 using Node = struct DL
 {
    int key;
    int val;
    struct DL* pre;
    struct DL* next;
 };

 unordered_map<int,Node*> map;
 int mSize,mCapacity;
 Node* head;
 Node* tail;

 Solution(int capacity){
 // write code here
     mCapacity=capacity;
     mSize=0;
     head=new Node;
     tail=new Node;
     head->pre=tail->next=nullptr;
     head->next=tail;
     tail->pre=head;
 }
 
 int get(int key) {
 // write code here
     if(map.count(key)==0)
         return -1;
    Node* tmp=map[key];
    int res=tmp->val;
    RemoveNode(tmp);
    AddTail(tmp);
    return res;
 }

 void AddTail(Node *n)
 {
    tail->pre->next=n;
    n->next=tail;
    n->pre=tail->pre;
    tail->pre=n;
 }

 void RemoveNode(Node* n)
 {
    n->pre->next=n->next;
    n->next->pre=n->pre;
 }

 void PopHead()
 {
    Node* tmp=head->next;
    head->next=head->next->next;
    head->next->pre=head;
    map.erase(tmp->key);
    delete tmp;
 }
 
 void set(int key, int value){
 // write code here

     if(map.count(key)>0)
     {
        map[key]->val=value;
        RemoveNode(map[key]);
        AddTail(map[key]);
     }
     else {
      Node* tmp=new Node();
      tmp->key=key;
      tmp->val=value;
      map[key]=tmp;
      AddTail(tmp);

     mSize++;
     if(mSize>mCapacity)
     {
        PopHead();
        mSize--;
     }

     }

 }
};

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