image.png
原题链接：https://leetcode-cn.com/problems/lru-cache/
解题思路：
-
哈希+双向链表
image.png
python3代码
class ListNode:
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.hashmap = {}
# 新建两个节点 head 和 tail
self.head = ListNode()
self.tail = ListNode()
# 初始化链表为 head <-> tail
self.head.next = self.tail
self.tail.prev = self.head
def move_to_end(self, key):
node = self.hashmap[key] # 获取要移动的节点 head->1->2->3->tail 移动2到tail之前，变成 head->1->3->2->tail
node.prev.next = node.next # 1的next指向3
node.next.prev = node.prev # 3的prev指向1
# 连接2和tail
node.prev = self.tail.prev # 2的prev由1改为3
node.next = self.tail # 2的next改为tail
self.tail.prev.next = node # tail的prev=3 3的next指向2
self.tail.prev = node # tail的prev指向2
def get(self, key: int) -> int:
if key in self.hashmap: # 更新该key到链表末位
self.move_to_end(key)
res = self.hashmap.get(key, -1)
if res == -1:
return -1
else:
return res.value
def put(self, key: int, value: int) -> None:
if key in self.hashmap: # 已经在hashmap里
self.move_to_end(key)
self.hashmap[key].value = value # 更新同一个key的不同value
else:
if len(self.hashmap) == self.capacity:
# 去掉哈希表对应项
self.hashmap.pop(self.head.next.key)
# 去掉最久没有被访问过的节点，即头节点之后的节点
self.head.next = self.head.next.next
self.head.next.prev = self.head
# 如果不在的话就插入到尾节点前
new = ListNode(key, value)
self.hashmap[key] = new
new.prev = self.tail.prev
new.next = self.tail
self.tail.prev.next = new
self.tail.prev = new
