Loading...

プレビュー

全42ステップ中13ステップのみ表示

ログインして全て見る

LRUキャッシュ

中級

LRU Cache

最も長く使われていない項目を削除するキャッシュの実装

📊 計算量

区分	計算量
最良	O(1)
平均	O(1)
最悪	O(1)
空間	O(capacity)

🏷️ Tags

ハッシュマップ双方向リストキャッシュ

📋 問題

LRUキャッシュ

LRU（Least Recently Used）キャッシュを実装してください。キャッシュは正の整数capacityで初期化され、get(key)とput(key, value)操作をサポートします。満杯のキャッシュに新しい項目を追加する際は、最も長く使われていない項目を削除する必要があります。

1/42

Loading...

📱スマホアプリ管理者!

📱 スマホの最近使ったアプリを思い出して！ • アプリを開く → リストの最前面へ • メモリ不足時 → 最も古いアプリを終了 • 特定アプリへアクセス → 名前で即検索これがLRUキャッシュです！

🔒

LRUキャッシュ

問題説明

LRU（Least Recently Used）キャッシュを実装してください。キャッシュは正の整数capacityで初期化され、get(key)とput(key, value)操作をサポートします。満杯のキャッシュに新しい項目を追加する際は、最も長く使われていない項目を削除する必要があります。

入力

capacity: キャッシュ容量、operations: 操作リスト ['put(key,value)', 'get(key)']

出力

各get操作の結果（見つからない場合は-1）

制約条件

•1 <= capacity <= 3000
•get、put関数はO(1)時間で動作する必要がある

例

例 1

入力

capacity = 3
put("A", 1)
put("B", 2)
put("C", 3)
get("A")
put("D", 4)

出力

get("A") → 1
캐시 상태: D, A, B (C 제거됨)

説明

Aを取得するとAが最近使用として更新されます。Dを追加する際、容量超過で最も古いCが削除されます。

LRUキャッシュ | AlgoNote