LRU Cache--leetcode

原題リンク:https://oj.leetcode.com/problems/lru-cache/
オペレーティングシステムにおけるリソース管理アルゴリズムを設計するために使用されるデータ構造、すなわちLRUアルゴリズム.総合的な問題に偏っている.
方法:ハッシュテーブル+両端チェーンテーブル
考え方:一方、LRU Cacheアルゴリズムはノードに迅速にアクセスできることを要求しているので、ハッシュテーブルや配列を使用することを容易に考えます.一方、このアルゴリズムは、容量上限に達したときに、最も長い間アクセスしていないデータノードを削除することを要求する.これは、設計されたデータ構造が迅速な挿入と削除を満たす必要があります.配列が要求に達していないことは明らかです.チェーンテーブルにはこの効果があります.ハッシュ・テーブルの迅速なアクセスとチェーン・テーブルの挿入削除の利点を備えたデータ構造を設計できます.すなわち,ハッシュテーブル+両端チェーンテーブルの形式を用いて,その内部アルゴリズムgetとsetを設計する.高速アクセスを実現し、ハッシュ・テーブルで実現できます.クイック挿入削除では、各キー値をチェーンテーブルの位置(反復器)に対応させてハッシュテーブルに格納できます.これにより、キー値が存在する位置をすばやく見つけて削除できます.
複雑度解析:時間複雑度はO(1)を実現し,空間的にhashtableと両端チェーンテーブルを用いた.空間交換時間の典型に属する.

struct Node  
{  
    int value;  
    list<int>::iterator iter;  
    Node(int value, list<int>::iterator iter)  
    {  
        this->value = value;  
        this->iter = iter;  
    }  
};  
class LRUCache{
public:
    LRUCache(int capacity) {
        this->capacity=capacity;
    }
    
    int get(int key) {
        if(0<mp.count(key))
        {
            moveToEnd(key);
            return mp[key]->value;
        }
        return -1;
    }
    
    void set(int key, int value) {
        if(0<mp.count(key)){
            mp[key]->value=value;
            moveToEnd(key);
        }
        else if(mp.size()<capacity)
        {
            l.push_back(key);
            mp[key]=new Node(value,--l.end());
        }
        else
        {
            int delKey=l.front();
            l.pop_front();
            mp.erase(delKey);
            l.push_back(key);
            mp[key]=new Node(value,--l.end());
        }
    }
    void moveToEnd(int key)
    {
        list<int>::iterator iter=mp[key]->iter;
        l.erase(iter);
        l.push_back(key);
        mp[key]->iter=--l.end();
    }
private:
    map<int,Node*> mp;
    list<int> l;
    int capacity;
};

これはプログラミングだけでなく、オペレーティングシステム、リソース管理などの知識にも関連する良い総合問題です.ある同級生がアリに会ったときに聞かれたが、この問題はなかなかいいようだ.