LRU Cache

容量 capacity の LRU（最近最も使われていない）キャッシュを設計せよ。

get(key): key が存在すれば値を返し、なければ -1 を返す。
put(key, value): キーが存在すれば値を更新、なければ挿入する。容量超過時は最も長く使われていないキーを削除する。

どちらの操作も $O(1)$ の平均時間計算量で動かせ。

Example 1:

Input: ["LRUCache","put","put","get","put","get","put","get","get","get"]
       [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output: [null,null,null,1,null,-1,null,-1,3,4]

Constraints:

$1 \leq \text{capacity} \leq 3000$
$0 \leq \text{key} \leq 10^4$
$0 \leq \text{value} \leq 10^5$

使用した概念Hash Table

アプローチ

思考

Python の OrderedDict は挿入順を保持し move_to_end で末尾に移動できる
末尾が最近使用、先頭が最古として扱う

実装

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.cap = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

Time Space