[LeetCode] 146.LRUキャッシュメカニズム

146 Lru Cache Mechanism

タイトル説明

廃棄データ構造を使用して、LRU（最近使用されていない）キャッシュメカニズムを設計および実装します。

以下をサポートする必要があります。データを取得し、データを書き込んで配置します。

Get data get（key）-キー（key）がキャッシュに存在する場合、キーの取得値（常に正）、それ以外の場合は-1。
データの書き込みput（key、value）-キーが存在しない場合、データ値が書き込まれます。キャッシュ容量の制限に達すると、新しいデータを書き込む前に、最も使用頻度の低いデータ値を削除して、新しいデータ値のためのスペースを確保する必要があります。

要件：O（1）時間計算量で両方の操作を実行できるかどうか。

例：

LRUCache cache = new LRUCache (2 / * buffer size * /) cache.put(1, 1) cache.put(2, 2) cache.get (1) // Returns 1 cache.put (3, 3) // This operation will cause invalid key 2 cache.get (2) // returns -1 (not found) cache.put (4, 4) // This operation will cause an invalid key cache.get (1) // returns -1 (not found) cache.get (3) // Returns 3 cache.get (4) // returns 4

考え

また、unordered_mapイテレータを使用して、キーと値のキーと値のペアの要素の二重リンクリストであるリストを実装します。キー要素はunordered_mapキー入力データですが、上記の位置にあるリスト内のキー値の場合は、削除要素を直接消去するのは簡単です。

コード

class LRUCache { public: LRUCache(int capacity):cap(capacity) { } int get(int key) { auto it = m.find(key) if (it == m.end()) return -1 int val = it->second->second l.erase(it->second) l.push_front(make_pair(key, val)) m[key] = l.begin() return val } void put(int key, int value) { auto it = m.find(key) if(it!=m.end()){ l.erase(it->second) } l.push_front(make_pair(key,value)) m[key] = l.begin() if(l.size()>cap){ int tmp = l.back().first m.erase(tmp) l.pop_back() } } private: unordered_map ::iterator> m list l int cap } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity) * int param_1 = obj.get(key) * obj.put(key,value) */