最も最近使用されていない（LRU）キャッシュを実装する

回答: # LRU キャッシュの実装（ハッシュマップ + 双方向連結リストを使用） # - ハッシュマップ（dict）はキー -> ノードへの O(1) アクセスを提供します # - 双方向連結リストは使用順序を維持します: 最も最近使われたものが head の直後、最も古く使われたものが tail の直前 # - キーがアクセスまたは更新されると、そのノードを head に移動します # - 容量を超えた場合、tail のノード (LRU) を削除し、そのキーをマップから削除します class _Node: """キーと値を保持する双方向連結リストのノード。""" 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): """指定された容量で LRUCache を初期化します。 容量が 0 以下の場合は、実質的にキャッシュを使用不可に（get は -1 を返し、put は何もしない）とします。 """ self.capacity = max(0, int(capacity)) self.cache = {} # key -> _Node # エッジチェックを避けるための head と tail のセントネルノード self.head = _Node() # Most recently used comes right after head self.tail = _Node() # Least recently used is right before tail self.head.next = self.tail self.tail.prev = self.head self.size = 0 # 内部ヘルパー: ノードを head の直後に追加（最近使用されたことを示す） def _add_node(self, node: _Node) -> None: node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node # 内部ヘルパー: 連結リストから既存のノードを削除 def _remove_node(self, node: _Node) -> None: prev = node.prev nxt = node.next if prev: prev.next = nxt if nxt: nxt.prev = prev node.prev = node.next = None # 内部ヘルパー: 既存のノードを head に移動（最も最近使用された） def _move_to_head(self, node: _Node) -> None: self._remove_node(node) self._add_node(node) # 内部ヘルパー: 最も最近使われていないノード（tail の直前）を取り出す def _pop_tail(self) -> _Node: node = self.tail.prev if node is self.head: return None self._remove_node(node) return node def get(self, key: int) -> int: """キーが存在する場合に関連する値を返します。存在しない場合は -1 を返します。 アクセスはそのキーを最近使用されたものとしてマークします。 平均時間 O(1)。 """ if self.capacity == 0: return -1 node = self.cache.get(key) if not node: return -1 # アクセスされたノードを head に移動（最近使用） self._move_to_head(node) return node.value def put(self, key: int, value: int) -> None: """キーと値を挿入または更新します。容量を超えた場合は LRU を削除します。 平均時間 O(1)。 """ if self.capacity == 0: return node = self.cache.get(key) if node: # 更新して最近使用としてマーク node.value = value self._move_to_head(node) else: # 新しいノードを挿入 new_node = _Node(key, value) self.cache[key] = new_node self._add_node(new_node) self.size += 1 if self.size > self.capacity: # 最も最近使われていないノードを削除 tail_node = self._pop_tail() if tail_node: del self.cache[tail_node.key] self.size -= 1 # 与えられたテストシーケンスでの実装のデモンストレーション if __name__ == "__main__": cache = LRUCache(2) cache.put(1, 10) cache.put(2, 20) print(cache.get(1)) # 期待される出力: 10 cache.put(3, 30) # Evicts key 2 print(cache.get(2)) # 期待される出力: -1 cache.put(4, 40) # Evicts key 1 print(cache.get(1)) # 期待される出力: -1 print(cache.get(3)) # 期待される出力: 30 print(cache.get(4)) # 期待される出力: 40

```python class Node: """キーと値のペアを格納し順序を維持するための双方向連結リストのノード。""" def __init__(self, key, value): self.key = key self.value = value self.prev = None self.next = None class LRUCache: """ハッシュマップと双方向連結リストを使用して Least Recently Used (LRU) キャッシュを実装します。""" def __init__(self, capacity: int): """指定された容量でLRUCacheを初期化します。""" self.capacity = capacity self.cache = {} # ハッシュマップ: key -> Node self.head = Node(0, 0) # ダミーのヘッドノード self.tail = Node(0, 0) # ダミーのテールノード self.head.next = self.tail self.tail.prev = self.head def _remove_node(self, node): """双方向連結リストからノードを削除します。""" prev_node = node.prev next_node = node.next prev_node.next = next_node next_node.prev = prev_node def _add_to_head(self, node): """ノードを双方向連結リストの先頭（最新使用）に追加します。""" node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def get(self, key: int) -> int: """キーの値を取得し、それを最近使用されたものとしてマークします。キーが見つからない場合は -1 を返します。""" if key in self.cache: node = self.cache[key] # アクセスされたノードを先頭（最新使用）に移動 self._remove_node(node) self._add_to_head(node) return node.value return -1 def put(self, key: int, value: int) -> None: """キーと値のペアを挿入または更新します。容量に達した場合は LRU（最も使用されていない）アイテムを追い出します。""" if self.capacity == 0: return if key in self.cache: # 既存のキーを更新 node = self.cache[key] node.value = value # 最近使用されたため先頭へ移動 self._remove_node(node) self._add_to_head(node) else: # 新しいキーを挿入 if len(self.cache) >= self.capacity: # 最も最近使用されていないアイテムを追い出す（tailの直前のノード） lru_node = self.tail.prev self._remove_node(lru_node) del self.cache[lru_node.key] new_node = Node(key, value) self.cache[key] = new_node self._add_to_head(new_node) # 実装をテストシーケンスで示す: cache = LRUCache(2) print("挿入中 (1, 10)") cache.put(1, 10) print("挿入中 (2, 20)") cache.put(2, 20) print("キー 1 を取得:") print(cache.get(1)) # 期待される出力: 10 print("挿入中 (3, 30)") cache.put(3, 30) # キー 2 を追い出す print("キー 2 を取得:") print(cache.get(2)) # 期待される出力: -1 print("挿入中 (4, 40)") cache.put(4, 40) # キー 1 を追い出す print("キー 1 を取得:") print(cache.get(1)) # 期待される出力: -1 print("キー 3 を取得:") print(cache.get(3)) # 期待される出力: 30 print("キー 4 を取得:") print(cache.get(4)) # 期待される出力: 40 ```