leetcode-设计LRU缓存结构-112
题目要求
思路
双链表+哈希表
代码实现
struct Node{int key, val;Node* next;Node* pre;Node(int _key, int _val): key(_key), val(_val), next(nullptr), pre(nullptr){}
};class Solution {
public:
unordered_map<int, Node*> hash;
Node* head;
Node* tail;
int cap;
int size;Solution(int capacity){size = 0;cap = capacity;head = nullptr;tail = nullptr;hash.clear();}void removetohead(Node* p)
{if(p == head)return;p->pre->next = p->next;if(p == tail)tail = p->pre;elsep->next->pre = p->pre;p->next = head;p->pre = nullptr;head->pre = p;head = p;return;
}int get(int key) {if(hash.find(key) == hash.end())return -1;removetohead(hash[key]);return hash[key]->val;}void set(int key, int val){if(hash.find(key) != hash.end()){hash[key]->val = val;removetohead(hash[key]);}else {if(size < cap) {Node* p = new Node(key, val);if(head == nullptr)head = tail = p;else {head->pre = p;p->next = head;head = p;}hash[key] = head;size++;}else{int k = tail->key;hash.erase(k);tail->key = key;tail->val = val;removetohead(tail);hash[key] = head;}}}
};