力扣刷题-热题100题-第35题（c++、python）

146. LRU 缓存 - 力扣（LeetCode）https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-100-liked

双向链表+哈希表

内置函数

对于c++有list可以充当双向链表，unordered_map充当哈希表；python有OrderedDict可以直接继承得到双向链表和哈希表，以此可以直接实现get与put操作；

在get操作里面，查看哈希表是否存在，若没有则返回-1，有则返回哈希表指向的地址

在put操作里面，查看哈希表是否存在，若没有则新建并插入哈希表与双向链表；若有，则把对应value刷新并移动至头部。

//c++
class LRUCache 
{
private:int capacity;list<pair<int,int>> cache;unordered_map<int,list<pair<int,int>>::iterator> key_map;public:LRUCache(int capacity) : capacity(capacity){}int get(int key){auto it=key_map.find(key);if(it==key_map.end())   return -1;cache.splice(cache.begin(),cache,it->second);return it->second->second;}void put(int key,int value){auto it=key_map.find(key);if(it!=key_map.end()){it->second->second=value;cache.splice(cache.begin(),cache,it->second);return;}if(cache.size()==capacity){auto last=cache.back();key_map.erase(last.first);cache.pop_back();}cache.emplace_front(key,value);key_map[key]=cache.begin();}
};#python
class LRUCache(collections.OrderedDict):def __init__(self, capacity: int):super().__init__()self.capacity=capacitydef get(self, key: int) -> int:if key not in self:return -1self.move_to_end(key)return self[key]def put(self, key: int, value: int) -> None:if key in self:self.move_to_end(key)self[key]=valueif len(self)>self.capacity:self.popitem(last=False)

创建数据结构

不用内置函数的话，自己构造数据结构表示双向链表与哈希表，然后对增加节点，删除节点，将节点移到最前面，删除最久未使用节点进行函数构造使用，方法是一样的，但这个会更加底层一点。

//c++
struct D
{int key,value;D* prev;D* next;D():key(0),value(0),prev(nullptr),next(nullptr){}D(int a,int b):key(a),value(b),prev(nullptr),next(nullptr){}
};
class LRUCache
{private:unordered_map<int,D*> cache;D* head;D* tail;int size;int capacity;public:LRUCache(int c):capacity(c),size(0){head=new D();tail=new D();head->next=tail;tail->prev=head;}void ath(D* a){a->prev=head;a->next=head->next;head->next->prev=a;head->next=a;}void rn(D* a){a->prev->next=a->next;a->next->prev=a->prev;}void mth(D* a){rn(a);ath(a);}D* mt(){D* a=tail->prev;rn(a);return a;}int get(int key){if(!cache.count(key))   return -1;D* a=cache[key];mth(a);return a->value;}void put(int key,int value){if(cache.count(key)){D* a=cache[key];a->value=value;mth(a);return;}D* a=new D(key,value);cache[key]=a;ath(a);size++;if(size>capacity){D* a=mt();cache.erase(a->key);size--;delete a;}}
};#python
class D:def __init__(self, key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=Noneclass LRUCache():def __init__(self,capacity:int):self.cache=dict()self.head=D()self.tail=D()self.head.next=self.tailself.tail.prev=self.headself.capacity=capacityself.size=0def rn(self,node):node.prev.next=node.nextnode.next.prev=node.prevdef ath(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef mth(self,node):self.rn(node)self.ath(node)def rt(self):node=self.tail.prevself.rn(node)return nodedef get(self, key: int) -> int:if key not in self.cache:return -1a=self.cache[key]self.mth(a)return a.valuedef put(self, key: int, value: int) -> None:if key in self.cache:a=self.cache[key]a.value=valueself.mth(a)returna=D(key,value) self.cache[key]=aself.ath(a)self.size+=1if self.size>self.capacity:a=self.rt()self.cache.pop(a.key)self.size-=1