LeetCode 146. LRU缓存机制(哈希+双链表实现)
原题链接
中等
作者:
我要出去乱说
,
2021-07-26 00:56:49
,
所有人可见
,
阅读 324
class LRUCache {
public:
struct Node //定义双链表结构体
{
int key, val;
Node *left, *right;
Node(int _key, int _val):key(_key), val(_val), left(nullptr), right(nullptr){}
}*L, *R;
unordered_map<int, Node*> hash;
int n;
LRUCache(int capacity) {
n = capacity;
L = new Node(-1, -1), R = new Node(-1, -1);
L->right = R, R->left = L; //初始化时头尾指针之间为空
}
void remove(Node* p) //删除指定节点
{
p->right->left = p->left; //当前节点右侧的左指针指向该节点的左侧
p->left->right = p->right; //节点左侧的右指针指向该节点的右侧
}
void insert(Node* p) //将一个新节点插入到L节点和第一个节点之间
{
p->right = L->right;
p->left = L;
L->right->left = p;
L->right = p;
}
int get(int key) {
if (hash.find(key) == hash.end()) return -1; //所查节点不存在的情况
auto p = hash[key]; //若存在,取出该节点并添加到链表首部
remove(p);
insert(p);
return p->val;
}
void put(int key, int value) {
if (hash.find(key) != hash.end()) //如果插入的值已经存在,则更新
{
auto p = hash[key];
p->val = value;
remove(p);
insert(p);
}
else //爆容量只会发生在插入时
{
if (hash.size() == n)
{
auto p = R->left; //要删除的节点位于R节点的左侧
remove(p); //从链表中删除节点
hash.erase(p->key); //从哈希表中删除节点
delete p; //从内存中删除节点
}
auto p = new Node(key, value);
hash[key] = p;
insert(p);
}
}
};