leetcode LRU Cache

浏览数：26 / 时间：2015年06月20日

题目链接。实现一个数据结构用于LRU，最近最少使用，O(1)插入和删除。关于LRU的基本知识可参考here。

先推荐JustDoIT的。

下面是我自己实现的。

class LRUCache{
public:
//146LRU Least Recently Used
    int LRUsize;
    struct LRUNode
    {
        int key;
        int value;
        LRUNode *pre, *next;
        LRUNode(int x, int y): key(x), value(y), pre(NULL), next(NULL){}
    };
    unordered_map<int, LRUNode *> LRUmap;
    LRUNode *head = NULL, *tail = NULL;
    
    LRUCache(int capacity)
    {
        LRUsize = capacity;
    }

    int get(int key)
    {
        if (LRUmap.count(key)) // if exists
        {
            if (head != LRUmap[key] && tail != LRUmap[key]) // 节点在中间
            {
                LRUmap[key] -> pre -> next = LRUmap[key] -> next;
                LRUmap[key] -> next -> pre = LRUmap[key] -> pre;
                LRUmap[key] -> next = head;
                head -> pre = LRUmap[key];
                head = LRUmap[key];
                head -> pre = NULL;
            }
            else if (head != LRUmap[key] && tail == LRUmap[key]) // 节点最后一个则放在头部即可
            {
                tail = LRUmap[key] -> pre;
                tail -> next = NULL;
                LRUmap[key] -> pre = NULL;
                head -> pre = LRUmap[key];
                LRUmap[key] -> next = head;
                head = LRUmap[key];
            }
            return LRUmap[key] -> value;
        }
        else
            return -1;
    }

    void set(int key, int value)
    {
        if (LRUmap.count(key))
        {
            LRUmap[key] -> value = value; // 一定要更新value
            if (head != LRUmap[key] && tail != LRUmap[key]) // 节点在中间
            {
                LRUmap[key] -> pre -> next = LRUmap[key] -> next;
                LRUmap[key] -> next -> pre = LRUmap[key] -> pre;
                LRUmap[key] -> next = head;
                head -> pre = LRUmap[key];
                head = LRUmap[key];
                head -> pre = NULL;
            }
            else if (head != LRUmap[key] && tail == LRUmap[key]) // 节点最后一个则放在头部即可
            {
                tail = tail -> pre;
                tail -> next = NULL;
                LRUmap[key] -> pre = NULL;
                head -> pre = LRUmap[key];
                LRUmap[key] -> next = head;
                head = LRUmap[key];
            }
        }
        else
        {
            LRUNode *tmp = new LRUNode(key, value);
            if (head == tail && head == NULL)
            {
                head = tmp;
                tail = tmp;
                LRUmap[key] = head;

            }
            else if (LRUsize == LRUmap.size()) //注意可能容量只为1，满了记得删除
            {
                tmp -> next = head;
                head -> pre = tmp;
                head = tmp;
                LRUmap[key] = tmp;
                LRUmap.erase(tail -> key);
                tail = tail -> pre;
                tail -> next = NULL;
 
            }
            else
            {
                tmp -> next = head;
                head -> pre = tmp;
                head = tmp;
                LRUmap[key] = tmp;
            }
        }
    }
};