题解 | 设计LRU缓存结构

#include <type_traits>
struct Node{
    int key;
    int val;
    Node* prev;
    Node* next;
    Node(int k,int v):key(k),val(v),prev(nullptr),next(nullptr){};
};
class Solution {
public:
int capacity;
int size;
Node* head=nullptr;
Node* tail=nullptr;
unordered_map<int,Node*> cache;

 Solution(int capacity){
 // write code here
  this->capacity=capacity;
  size=0;
  head=new Node(0,0);
  tail=new Node(0,0);
  head->next=tail;
  tail->prev=head;
 }
 void addToHead(Node* node)
 {
    node->prev=head;
    node->next=head->next;
    head->next->prev=node;
    head->next=node;
 }
 void removeNode(Node* node)
 {
    node->prev->next=node->next;
    node->next->prev=node->prev;
 }
 void moveToHead(Node* node)
 {
    removeNode(node);//先断开，删除此时的节点
    addToHead(node);//把它放到头部
 }
 Node* removeTail()
 {
    Node* last=tail->prev;
    removeNode(last);
    return last;
 }
 int get(int key) {
 // write code here
  if(cache.count(key))
  {
    moveToHead(cache[key]);
    return cache[key]->val;
  }
  else 
  {
    return -1;
  }
 }
 
 void set(int key, int value){
 // write code here
    if(cache.count(key))
    {
      cache[key]->val=value;
      moveToHead(cache[key]);
    }
    else 
    {
      Node* newNode = new Node(key,value);
      cache[key]=newNode;
      addToHead(newNode);
      size++;
      if(size>capacity)
      {
        Node* last=removeTail();
        cache.erase(last->key);
        delete last;
        size--;
      }
    }
 }
};

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