【フォーカス】LeetCode146。LRUキャッシュ
Focus Leetcode 146 Lru Cache
1.ソリューション1
このブログは以下から複製されています： http://www.cnblogs.com/grandyang/p/4587511.html
この質問により、LRUバッファーを実装できます。 LRUは、Least Recent Usedの略で、最も最近使用されていないことを意味します。次に、このバッファーには、getとputの2つの主要なメンバー関数があります。 get関数は、キーを入力して値を取得する機能です。正常に取得されると、ペア（key、value）は、バッファー内で最も一般的に使用される位置（top）に上昇します。キーが存在しない場合は、-1を返します。 put関数は、新しいペア（key、value）を挿入します。キーが元のバッファに存在する場合は、元のキーを削除して、新しいキーをバッファの上に挿入する必要があります。存在しない場合は、直接上に挿入してください。新しい値を追加した後でバッファが容量を超えた場合は、最も使用頻度の低い値である一番下の値を削除する必要があります。特定の実装では、cap、l、mの3つのプライベート変数が必要です。ここで、capはキャッシュの容量、lはキャッシュの内容のリスト、mはハッシュテーブル、キー値とアイテムです。キャッシュのが保存されます。イテレータ間のマッピングにより、O（1）時間でターゲットアイテムを見つけることができます。
次に、getとputがどのように実装されているかを見て、getは比較的単純です。指定されたキーが存在する場合は、mで見つけ、このアイテムを一番上に移動し、戻り値がない場合は-1を返します。つまり、mで指定されたキーも探しています。存在する場合は、元のアイテムを削除し、上部に新しいアイテムを挿入して、オーバーフローするかどうかを判断します。オーバーフローした場合は、一番下のアイテム（最も使用頻度の低いアイテム）を削除します。コードは次のように表示されます。
class LRUCache{ public: LRUCache(int capacity) { cap = capacity } int get(int key) { auto it = m.find(key) if (it == m.end()) return -1 l.splice(l.begin(), l, it->second)//Move the element pointed to by it->second iterator to the beginning of l return it->second->second } 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 (m.size() > cap) { int k = l.rbegin()->first l.pop_back() m.erase(k) } } private: int cap listint , int>> l unordered_map<int, listint , int>>::iterator> m }2. C ++のリストのsplice（）関数
c ++でのリストのスプライス関数の使用法に関するリファレンスリンク： http://www.cplusplus.com/reference/list/list/splice/
サンプルコード：
// splicing lists #include #include int main () { std::list<int> mylist1, mylist2 std::list<int>::iterator it // set some initial values: for (int i=1 i<=4 ++i) mylist1.push_back(i) // mylist1: 1 2 3 4 for (int i=1 i<=3 ++i) mylist2.push_back(i*10) // mylist2: 10 20 30 it = mylist1.begin() ++it // points to 2 mylist1.splice (it, mylist2) // mylist1: 1 10 20 30 2 3 4 // mylist2 (empty) // 'it' still points to 2 (the 5th element) mylist2.splice (mylist2.begin(),mylist1, it) // mylist1: 1 10 20 30 3 4 // mylist2: 2 // 'it' is now invalid. it = mylist1.begin() std::advance(it,3) // 'it' points now to 30 mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end()) // mylist1: 30 3 4 1 10 20 std::cout << 'mylist1 contains:' for (it=mylist1.begin() it!=mylist1.end() ++it) std::cout << ' ' << *it std::cout << '
' std::cout << 'mylist2 contains:' for (it=mylist2.begin() it!=mylist2.end() ++it) std::cout << ' ' << *it std::cout << '
' return 0 } Output: mylist1 contains: 30 3 4 1 10 20 mylist2 contains: 2