ページ置換アルゴリズムLRU実装--leetcode O(1)時間複雑度

転載作者:魚と海の出典:http://www.cnblogs.com/joannacode/p/5998949.html
leetcodeタイトルアドレス
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 put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(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.
Follow up: Could you do both operations in O(1) time complexity?
Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Subscribe to see which companies asked this question.
acコード
双方向チェーンテーブル+mapを採用(効率的なmapはunordered_mapにさらに利用可能)

データ構造設計

typedef struct node{
    int key;
    int val;
    struct node* pre;
    struct node* next;
    node(int _key = -1, int _val = -1)
    {
        key = _key;
        val = _val;
        pre = NULL;
        next = NULL;
    }
}DNode;

class LRUCache
{
public:

    LRUCache(int _capacity) {
        capacity = _capacity;
        size = 0;
        head = new DNode();
        tail = new DNode();
        head->next = tail;
        tail->pre = head;
        mp.clear();
    }

    int get(int key) {
        map<int,DNode*>::iterator it= mp.find(key);
        if(it == mp.end())  //   Cache     key，    -1
        {
            return -1; 
        }
        else
        {
            DNode* t =  it->second;
            //   t    ，   t       

            t->pre->next = t->next;
            t->next->pre = t->pre;


            t->pre = head;
            t->next = head->next;
            head->next = t;
            t->next->pre = t;

            return t->val;
        }  
    }

    void put(int key, int value) {
        map<int,DNode*>::iterator it= mp.find(key);
        if(it == mp.end())  //   Cache     key，    -1
        {

            if(size == capacity) //                 ，                        
            {
                //       
                DNode *tmp = tail->pre;
                tail->pre->pre->next = tail;           
                tail->pre = tmp->pre;

                mp.erase(tmp->key);
                delete tmp;
                size--;
            }

            //       head      map
            DNode *newNode = new DNode(key, value);

            newNode->pre = head;
            newNode->next = head->next;
            head->next = newNode;
            newNode->next->pre = newNode;

            mp[key] = newNode;// hashtable  key      

            size++;//     ++ 

        }else{ //   put     ，    value

            DNode* t =  it->second;
            //   t    ，   t       
            t->pre->next = t->next;
            t->next->pre = t->pre;

            t->val = value; //**

            t->pre = head;
            t->next = head->next;
            head->next = t;
            t->next->pre = t;

            return;
        }
    }

private:
    int capacity;
    int size;
    DNode* head; 
    DNode* tail;
    map<int,DNode*> mp;
};

ac2 (C++ list + map)
c++list自体が双方向チェーンテーブルであることを考慮するとlistを直接採用することができる(効率は悪いがacはできる)

class LRUCache
{
public:

    LRUCache(int _capacity) {
        capacity = _capacity;
        size = 0;
        cachelist.clear();
        mp.clear();
    }

    int get(int key) {
        map<int,pair<int,int>>::iterator it= mp.find(key);
        if(it == mp.end())  //   Cache     key，    -1
        {
            return -1; 
        }
        else
        {
            pair<int,int> t = it->second;
            pair<int,int> newPair(t.first, t.second);

            cachelist.remove(t);
            cachelist.push_front(newPair);

            return newPair.second;
        }  
    }

    void put(int key, int value) {
        map<int,pair<int,int>>::iterator it= mp.find(key);
        if(it == mp.end())  //   Cache     key，    -1
        {

            if(size == capacity) //                 ，                        
            {

                pair<int,int> tmp = cachelist.back();
                cachelist.pop_back();

                mp.erase(tmp.first);
                size--;
            }

            pair<int,int> newPair(key,value);
            cachelist.push_front(newPair);
            mp[key] = newPair;
            size++;//     ++ 

        }else{ //   put     ，    value

            pair<int,int> t = it->second;
            pair<int,int> newPair(key,value);

            cachelist.remove(t);
            cachelist.push_front(newPair);

            mp[t.first] = newPair;

            return;
        }
    }

private:
    int capacity;
    int size;
    listint,int>> cachelist;
    map<int, pair<int,int>> mp;
};

ac3
データ構造図の考え方に従ってコードを書くのは簡単です.

typedef struct node
{
    int key;
    int val;
    struct node* next;
    struct node* pre;
    node(int _key = -1, int _val = -1){
        key = _key;
        val = _val;
        next = NULL;
        pre = NULL;
    }
}Dnode;

class LRUCache {
public:

    int size;
    int cap;
    Dnode* head;
    Dnode* tail;
    map<int, Dnode*> mp;

    LRUCache(int capacity) {
        size = 0;
        cap =capacity;
        head = new Dnode;
        tail = new Dnode;

        head->next = tail;
        tail->pre = head;
    }

    int get(int key) {
        if(mp.count(key) == 0)
            return -1;

        Dnode*  oldPos = mp[key];
        int val = oldPos->val; //    val

        Dnode* oldpre = oldPos->pre;
        oldPos->next->pre = oldpre;
        oldpre->next = oldPos->next;

        delete oldPos;
        mp.erase(key);

        Dnode* newPos = new Dnode(key,val);

        head->next->pre = newPos;
        newPos->next = head->next;
        newPos->pre = head;
        head->next = newPos;

        mp[key] = newPos;

        return val;
    }

    void put(int key, int value) {
        if(cap <= 0)
            return;

        int storeVal = get(key);
        if(storeVal != -1)
        {
            head->next->val = value;
            mp[key]->val = value;

            return;
        }

        if(size == cap)
        {
            Dnode* delNode = tail->pre;
            int delKey = delNode->key;
            Dnode* delpre = tail->pre->pre;

            delpre->next = tail;
            tail->pre= delpre;

            delete delNode;
            mp.erase(delKey);
            size --;
        }

        Dnode* newPos = new Dnode(key,value);

        head->next->pre = newPos;
        newPos->next = head->next;
        newPos->pre = head;
        head->next = newPos;

        mp[key] = newPos;
        size ++;
    }
};

上のコードは、getメソッドを改善します(実行時間を少し最適化できます)

int get(int key) {
    if(mp.count(key) == 0)
        return -1;

    Dnode*  oldPos = mp[key];
    int val = oldPos->val; //    val

    Dnode* oldpre = oldPos->pre;
    oldPos->next->pre = oldpre;
    oldpre->next = oldPos->next;

    //delete oldPos;
    //mp.erase(key);

    //Dnode* newPos = new Dnode(key,val);
    Dnode* newPos = oldPos; //    

    head->next->pre = newPos;
    newPos->next = head->next;
    newPos->pre = head;
    head->next = newPos;

    mp[key] = newPos;//     

    return val;
}