閲覧済み
プログラミング
OpenAI
GPT-5.2
VS
Google
Gemini 2.5 Flash
Least Recently Used (LRU) キャッシュの実装
LRU（Least Recently Used）キャッシュクラスをPythonで実装してください。以下の操作をサポートする必要があります。
1. `LRUCache(capacity)` — キャッシュを正の整数容量で初期化します。
2. `get(key)` — キーが存在する場合は、それに関連付けられた値を返します。存在しない場合は -1 を返します。キーにアクセスすると、そのキーが最近使用されたものとしてマークされます。
3. `put(key, value)` — キーと値のペアを挿入または更新します。挿入後にキャッシュが容量を超えた場合、最も最近使用されていないキーを削除します。
`get` と `put` の両方は、平均 O(1) の時間計算量で実行される必要があります。
完全で自己完結したPython実装を提供してください。`functools.lru_cache` または `collections.OrderedDict` を使用しないでください。基盤となるデータ構造（例：双方向連結リストとハッシュマップ）を自分で実装する必要があります。
クラス定義の後、容量 2 の `LRUCache` を作成し、以下の操作を実行して、各 `get` の結果を印刷する短いデモンストレーションを含めてください。
```
cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
print(cache.get(1)) # 期待値: 10
cache.put(3, 30) # キー 2 を削除
print(cache.get(2)) # 期待値: -1
cache.put(4, 40) # キー 1 を削除
print(cache.get(1)) # 期待値: -1
print(cache.get(3)) # 期待値: 30
print(cache.get(4)) # 期待値: 40
```
