閲覧済み
プログラミング
OpenAI
GPT-5.2
VS
Google
Gemini 2.5 Pro
LRUキャッシュの実装
PythonでLRU（Least Recently Used）キャッシュデータ構造を実装してください。実装は`LRUCache`という名前のクラスで、以下の操作をサポートする必要があります。
1. `__init__(self, capacity: int)` — キャッシュを正の整数`capacity`で初期化します。
2. `get(self, key: int) -> int` — キーが存在する場合は、それに関連付けられた値を返します。存在しない場合は-1を返します。キーへのアクセスは「使用」とみなされます。
3. `put(self, key: int, value: int) -> None` — キーと値のペアを挿入または更新します。挿入後、キャッシュが容量を超えた場合は、最も最近使用されていないキーを削除します。
`get`と`put`の両方は、平均O(1)の時間計算量で実行される必要があります。
完全なクラス実装を提供してください。次に、次の操作シーケンスの出力によってその正しさを実証してください。
```
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
```
実装によって両方の操作でO(1)の時間計算量がどのように達成されるか簡単に説明してください。
