146. LRU 缓存
已解答
中等
相关标签
相关企业
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
class ListNode(object):
def __init__(self,key,val,next=None,prev=None):
self.val =val
self.key = key
self.next = next
self.prev = prev
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.head = ListNode(-1,-1,None,None)
self.tail = ListNode(-1,-1,None,None)
self.head.next=self.tail
self.tail.prev = self.head
self.num_nodes = 0
self.hashmap={}
# 应该是保存key ：node node里面是val
def remove_to_tail(self,rt):
rt.prev.next = rt.next
rt.next.prev = rt.prev
# 放到末尾，这里有点问题，应为删除的可能就是末尾
prev = self.tail.prev
prev.next = rt
rt.next = self.tail
self.tail.prev = rt
rt.prev = prev
def get(self, key):
"""
:type key: int
:rtype: int
"""
# 转移到链表的尾部
rt = self.hashmap.get(key,-1)
if rt==-1:
# 找不到的话，那就return -1
return -1
else:
# 能找到就找到并且放到末尾
# 删除原本的，然后放到末尾
# 如果是末尾的话，根本不用动
if rt==self.tail.prev:
return rt.val
else:
# 删除原本的
self.remove_to_tail(rt)
return rt.val
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if self.hashmap.get(key):
# print(1111111)
self.hashmap[key].val = value
# 然后放到tail去
rt = self.hashmap[key]
# 删除原本的
self.remove_to_tail(rt)
else:
temp = ListNode(key,value)
if self.num_nodes<self.capacity:
self.hashmap[key]=temp
prev = self.tail.prev
prev.next = temp
temp.next = self.tail
self.tail.prev = temp
temp.prev = prev
self.num_nodes+=1
else:
# >=cap,也就是需要我们来删除一个
# 删除头结点的下一个节点
dele = self.head.next
self.head.next = dele.next
dele.next.prev = self.head
# hashmap里面也要删除
# print(self.hashmap)
# print(dele.key)
del self.hashmap[dele.key]
# 删除之后加上最新的到为节点
self.hashmap[key]=temp
prev = self.tail.prev
prev.next = temp
temp.next = self.tail
self.tail.prev = temp
temp.prev = prev
# 如果input的是相同的key会覆盖掉，这个时候num_nodes-1
if key == dele.key:
self.num_nodes-=1
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
这里我们的思路是，放入需要o1那么直接的我们使用hashmap，key是key value是list节点，同时节点要存储key和value，因为要通过节点进行删除，如果只有value，那就无法再hashmap之中删除
根据LRU的规律我们选择双向链表，因为单向的没有prev和next，无法进行删除操作
需要对于LRU算法非常熟悉才行啊，比如说
插入的时候：
如果没到存储上限，那就直接放到最近使用
如果到达存储上限，那就删除掉最远的，放到最近使用
如果插入的是已经有的，那就把原本的换成现在的，并且放到最近使用
查询：
如果查询到了，把原本节点删除，新节点直接放到最近使用
一些细节：必须要有两个伪装节点head tail因为如果这两个不单独创建的话，删除的时候tail很可能被删除，不好写
