模拟+哈希表+双向链表
思路
见: https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
代码
struct linknode//定义了一个链表结点结构体
{
int key,value;
linknode *prev;
linknode *next;
linknode():key(0),value(0),prev(nullptr),next(nullptr){}
linknode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
};
class LRUCache {
private:
unordered_map<int,linknode*> cache;
linknode* head;
linknode* tail;
int size;//记录实际大小
int capacity;//记录容量
public:
LRUCache(int _capacity):capacity(_capacity),size(0) {
head = new linknode();
tail = new linknode();
head->next=tail;
tail->prev=head;
}
int get(int key) {
if(!cache.count(key))
return -1;
linknode* node=cache[key];
movetohead(node);
return node->value;
}
void put(int key, int value) {
if(!cache.count(key))
{
linknode* node =new linknode(key,value);
cache[key]=node;
addtohead(node);
size++;
if(size>capacity)
{
linknode* removed = removetail();
cache.erase(removed->key);
delete removed;
size--;
}
}
else
{
linknode* node=cache[key];
node->value=value;
movetohead(node);
}
}
void addtohead(linknode* node)
{
node->prev=head;
node->next=head->next;
head->next->prev=node;
head->next=node;
}
void removenode(linknode* node)
{
node->next->prev=node->prev;
node->prev->next=node->next;
}
void movetohead(linknode* node)
{
removenode(node);
addtohead(node);
}
linknode* removetail()
{
linknode* node=tail->prev;
removenode(node);
return node;
}
};