### 使用 Python 实现双向解析的三种算法 #### 方法一：标准求解【队列+字典】 此方法利用了队列先进先出的特点以及字典快速查找的优势来实现 LRU 缓存机制。每当有新的数据加入缓存时，如果超过了设定的最大容量，则移除最早进入的数据项。 ```python from collections import deque class LRUCache: def __init__(self, capacity: int): self.cache = {} self.queue = deque() self.capacity = capacity def get(self, key: int) -> int: if key not in self.cache: return -1 value = self.cache[key][0] index = self.cache[key][1] del self.queue[index] self.queue.append(key) new_index = len(self.queue)-1 self.cache[key] = (value, new_index) return value def put(self, key: int, value: int) -> None: if key in self.cache: old_value, _ = self.cache.pop(key) try: self.queue.remove(key) except ValueError: pass elif len(self.cache) >= self.capacity and self.queue: oldest_key = self.queue.popleft() self.cache.pop(oldest_key, None) self.queue.append(key) self.cache[key] = (value, len(self.queue)-1) ``` 这种方法虽然可以工作，但是效率较低，在频繁操作下性能会受到影响[^1]。 #### 方法二：改进版一【有序字典】 Python 中 `collections.OrderedDict` 提供了一种更高效的方式来管理键值对顺序，使得最近使用的元素总是在最后面，而最久未被访问过的则位于前面。当超出限定大小时可以直接删除第一个元素即可完成淘汰策略。 ```python from collections import OrderedDict class LRUCache(OrderedDict): def __init__(self, capacity: int): super().__init__() self.capacity = capacity def get(self, key: int) -> int: if key not in self: return -1 value = self[key] self.move_to_end(key) return value def put(self, key: int, value: int) -> None: if key in self: self.move_to_end(key) self[key] = value if len(self) > self.capacity: oldest = next(iter(self)) del self[oldest] ``` 这种方式不仅简化了代码逻辑而且提高了执行速度。 #### 方法三：改进版二【双向链表+字典】 通过构建自定义类模拟双向链接列表结构，并配合哈希映射存储节点位置信息，可以在 O(1) 时间复杂度内完成插入、查询和更新等基本功能。对于大规模数据处理场景特别适用。 ```python class DLinkedNode(): def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.size = 0 self.capacity = capacity self.cache = dict() # 创建虚拟头部和尾部结点 self.head = DLinkedNode() self.tail = DLinkedNode() self.head.next = self.tail self.tail.prev = self.head def add_node(self, node:DLinkedNode)->None: """总是添加到双向链表头部""" node.prev=self.head node.next=self