【力扣100】146.LRU缓存

添加链接描述

class DLinkedNode: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 = DLinkedNode()self.tail = DLinkedNode()self.head.next = self.tailself.tail.prev = self.headself.capacity = capacityself.size = 0def get(self, key: int) -> int:if key not in self.cache:return -1# 如果 key 存在，先通过哈希表定位，再移到头部node = self.cache[key]self.moveToHead(node)return node.valuedef put(self, key: int, value: int) -> None:if key not in self.cache:# 如果 key 不存在，创建一个新的节点node = DLinkedNode(key, value)# 添加进哈希表self.cache[key] = node# 添加至双向链表的头部self.addToHead(node)self.size += 1if self.size > self.capacity:# 如果超出容量，删除双向链表的尾部节点removed = self.removeTail()# 删除哈希表中对应的项self.cache.pop(removed.key)self.size -= 1else:# 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部node = self.cache[key]node.value = valueself.moveToHead(node)def addToHead(self, node):node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef removeNode(self, node):node.prev.next = node.nextnode.next.prev = node.prevdef moveToHead(self, node):self.removeNode(node)self.addToHead(node)def removeTail(self):node = self.tail.prevself.removeNode(node)return node

思路：

1. 这道题的题目理解：

• 1）当使用get命令时，如果无，则返回-1；如果有则先在哈希表中查找这个值，返回值的同时，这个节点移到最前面（因为被访问过了，就排在前面）
• 2）当使用put命令时，先在哈希表里查找这个值，如果有，则把这个节点的值做更改，然后把这个节点放到前面；如果没有，则先在哈希表中添加这个节点，然后把这个节点放进链表中；同时这里要注意，控制链表的长度，如果大于指定长度，则把尾结点指向的值弹出，同时还要把弹出的节点从哈希表里删掉 self.cache.pop(removed.key)

2. 然后需要添加的四个函数：

• 添加指定值节点
• 删除指定值节点
• 指定值节点移到头部：先删除指定值，再添加指定值
• 超出长度后，删除尾结点节点这个函数需要返回值，因为要在哈希表中删除对应的键值对，这里也对应了为什么我在构建节点时需要把key和value都保存在节点里，因为哈希表删除需要给出**键**