leetcode-LRUCache的解

51 阅读 0 评论 34 点赞

我是靠谱客的博主合适硬币，最近开发中收集的这篇文章主要介绍leetcode-LRUCache的解，觉得挺不错的，现在分享给大家，希望可以做个参考。

因为要频繁执行查询插入删除等操作，所以考虑用hash表来做。

为了实现LRU，可以根据数据的最后使用时间维护一个堆，查找和调整都是O(lgn) ，没有试过，不知道想法对不对。

我采用的是双链表+map的办法，在表头插，表尾删。

class LRUCacheValue;

typedef pair<const int, LRUCacheValue> VTYPE;

class LRUCacheValue

public:

    VTYPE * next;

    VTYPE * prev;

    LRUCacheValue(int v);

    LRUCacheValue():value(-1), next(NULL), prev(NULL){}

    ~LRUCacheValue(){}

    int getValue() const;

    void setValue(int v);

private:

    int value;

};

LRUCacheValue::LRUCacheValue(int v):value(v), next(NULL), prev(NULL)

int LRUCacheValue::getValue() const

    return value;

void LRUCacheValue::setValue(int v)

    value = v;

class LRUCache{

public:

    typedef map<int, LRUCacheValue> MAP;

    LRUCache(int capacity) {

        _capacity = capacity;

        vmap.clear();

        head = NULL;

        tail = NULL;

    int get(int key)

        MAP::iterator it = vmap.find(key);

        if(it != vmap.end())

            int ret = it->second.getValue();

            update(it, ret);

            return ret;

        return -1;

    void set(int key, int value) {

        MAP::iterator it = vmap.find(key);

        if(it != vmap.end())

            update(it, value);

        else

            insert(key, value);

    void update(MAP::iterator it, int value)

        VTYPE *v = &*it;

        VTYPE *pre = v->second.prev;

        VTYPE *nex = v->second.next;

        v->second.setValue(value);

        if(pre != NULL)

            pre->second.next = nex;

            v->second.next = head;

            head->second.prev = v;

            v->second.prev = NULL;

            head = v;

            if(nex != NULL)

                nex->second.prev = pre;

            else

                tail = pre;

    void insert(int key, int value)

        if(vmap.size() >= _capacity)

            VTYPE * old = tail;

            VTYPE* p = tail->second.prev;

            if(p != NULL)

                p->second.next = NULL;

                tail = p;

            vmap.erase(old->first);

        pair<MAP::iterator, bool> ret = vmap.insert(make_pair(key, LRUCacheValue(value)));

        VTYPE *inserted = &*ret.first;

        if(head != NULL)

            head->second.prev = inserted;

            inserted->second.next = head;

            head = head->second.prev;

        else

            head = inserted;

        if(tail == NULL)

            tail = head;

private:

    unsigned int _capacity;

    MAP vmap;

    VTYPE* head;

    VTYPE* tail;

};

有一点之前没有注意的是，查询也应该更新查询到的元素在链表中的位置。

以上就是合适硬币为你收集整理的leetcode-LRUCache的解的全部内容，希望文章能够帮你解决leetcode-LRUCache的解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。