回答:

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

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