[leetcode] 146. LRU Cache解題レポート

タイトルリンク:https://leetcode.com/problems/lru-cache/
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:  get  and  set . get(key)  - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value)  - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
構想:この問題の大まかな構想は1つのhashテーブルで既存のkeyを保存し、それから別の線形容器でそのkey-value値を保存することであり、チェーンテーブルlistを選択することができる.ノードの位置を調整する必要があるため、チェーンテーブルはO(1)時間にノードの位置を移動することができ、配列はO(n)を必要とする. 
新しくsetリクエストが来たらhashテーブルを調べてみましょう
1.このキーが既に存在する場合、valueを更新し、リストのノード位置でチェーンテーブルのヘッダに移動する必要がある.
2.このkeyが存在しない場合は、hashテーブルとチェーンテーブルの両方にこの値を追加する必要があり、追加後にチェーンテーブルの長さが最大長を超える場合は、チェーンテーブルの末尾のノードを削除し、hashテーブルのレコードを削除する必要があります.
getリクエストが来た場合、keyがhashテーブルに存在する場合、このノードのチェーンテーブルにおける位置をチェーンテーブルのヘッダに移動する必要があるhashテーブルを先に調べる.そうでない場合は-1を返します.
もう1つの非常に重要な時間複雑度を低減する方法はhashにそのkeyをチェーンテーブルに対応するポインタを保存することであり、チェーンテーブルがノードを検索する時間複雑度がO(n)であることを知っているので、チェーンテーブルのヘッダにノードを移動する必要がある場合、チェーンテーブルでそのkeyが対応するノードを直接検索してから移動する.このような時間的複雑度はO(n)であるが、hashテーブルにそのkeyのチェーンテーブルにおける接点のポインタを記憶することで、O(1)の時間内にノードをチェーンテーブルのヘッダに移動することができる.
c++のstlライブラリは非常に豊富な関数を提供し、これらのものを把握するとコードの長さを大幅に減少させる.
コードは次のとおりです.

class LRUCache{
public:
    LRUCache(int capacity):n(capacity) {
    }
    
    int get(int key) {
        auto it = hash.find(key);
        if(hash.find(key) == hash.end())
            return -1;
        lt.splice(lt.begin(), lt, it->second);    
        return it->second->second;
    }
    
    void set(int key, int value) {
        auto it = hash.find(key);
        if(it != hash.end())
        {
            it->second->second = value;
            lt.splice(lt.begin(), lt, it->second);
            return;
        }
        lt.emplace_front(key, value);
        hash[key] = lt.begin();
        if(lt.size() > n)
        {
            hash.erase(lt.back().first);
            lt.pop_back();
        }
    }
private:
    unordered_map<int, list<pair<int,int>>::iterator> hash;
    list<pair<int, int>> lt;
    int n;
};

参照先:https://leetcode.com/discuss/61270/clean-short-standard-solution-writing-like-other-lengthy-ones