1.LRU缓存机制https://leetcode-cn.com/problems/lru-cache/
拿到题目先想的是用字典，删除元素就想找是否有可以顺序删除字典元素的方法，但是好像没有
看了官方答案感觉有点高深，哈希表+双向链表
1 class DLinkedNode: 2 def __init__(self, key=0, value=0): 3 self.key = key 4 self.value = value 5 self.prev = None 6 self.next = None 7 8 9 class LRUCache: 10 11 def __init__(self, capacity: int): 12 self.cache = dict() 13 # 使用伪头部和伪尾部节点 14 self.head = DLinkedNode() 15 self.tail = DLinkedNode() 16 self.head.next = self.tail 17 self.tail.prev = self.head 18 self.capacity = capacity 19 self.size = 0 20 21 def get(self, key: int) -> int: 22 if key not in self.cache: 23 return -1 24 # 如果 key 存在，先通过哈希表定位，再移到头部 25 node = self.cache[key] 26 self.moveToHead(node) 27 return node.value 28 29 def put(self, key: int, value: int) -> None: 30 if key not in self.cache: 31 # 如果 key 不存在，创建一个新的节点 32 node = DLinkedNode(key, value) 33 # 添加进哈希表 34 self.cache[key] = node 35 # 添加至双向链表的头部 36 self.addToHead(node) 37 self.size += 1 38 if self.size > self.capacity: 39 # 如果超出容量，删除双向链表的尾部节点 40 removed = self.removeTail() 41 # 删除哈希表中对应的项 42 self.cache.pop(removed.key) 43 self.size -= 1 44 else: 45 # 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部 46 node = self.cache[key] 47 node.value = value 48 self.moveToHead(node) 49 50 def addToHead(self, node): 51 node.prev = self.head 52 node.next = self.head.next 53 self.head.next.prev = node 54 self.head.next = node 55 56 def removeNode(self, node): 57 node.prev.next = node.next 58 node.next.prev = node.prev 59 60 def moveToHead(self, node): 61 self.removeNode(node) 62 self.addToHead(node) 63 64 def removeTail(self): 65 node = self.tail.prev 66 self.removeNode(node) 67 return node