题目:
//构建双向链表的节点结构(要有两个构造函数)
struct Node{
int key, val;
Node* pre;
Node* next;
Node():key(0), val(0), pre(nullptr), next(nullptr) {}
Node(int _key, int _val): key(_key), val(_val), pre(nullptr), next(nullptr) {}
};
class LRUCache {
private:
//哈希表存放key和节点的映射
unordered_map<int, Node*> m;
Node* head;
Node* tail;
int capacity, size;
public:
//LRU构造函数中,设定capacity和size(当前容量)、创建伪头、尾节点并相连
LRUCache(int _capacity) : capacity(_capacity), size(0){
head = new Node();
tail = new Node();
head->next = tail;
tail->pre = head;
}
//取值:如果表里没有这个key,返回-1;如果有,更新节点值,并将其移动至头部
int get(int key) {
if(!m.count(key)) return -1;
Node* node = m[key];
remove(node);
add(node);
return node->val;
}
//放值:如果表里找到,更新值并移动到头部;如果没找到,执行插入操作,插入前先判断是否溢出容量,是的话移除尾部节点,还要将其从表里删除,当前容量减一,然后将新节点加入头部、表、容量加一
void put(int key, int value) {
if(m.count(key)){
Node* node = m[key];
node->val = value;
remove(node);
add(node);
}else{
Node* node = new Node(key, value);
if(size==capacity){
Node* del = tail->pre;
m.erase(del->key);
remove(del);
size--;
}
add(node);
size++;
m[key] = node;
}
}
//删除节点
void remove(Node* node){
node->pre->next = node->next;
node->next->pre = node->pre;
}
//将节点移动至头结点
void add(Node* node){
node->next = head->next;
node->pre = head;
head->next->pre = node;
head->next = node;
}
};
参考视频:LeetCode 每日一题146. LRU 缓存 | 手写图解版思路 + 代码讲解
标签:node,Node,pre,缓存,int,C++,next,LRU,key From: https://www.cnblogs.com/fly-smart/p/18057645