美文网首页
146. LRU(待纠错)

146. LRU(待纠错)

作者: HamletSunS | 来源:发表于2019-08-08 22:36 被阅读0次

思路:
通过哈希表迅速找到映射关系。
通过双向链表和头、尾指针迅速定位第一个节点和最后一个节点,之所以用链表是为了确定当空间满后应当删除哪个值。链表的顺序代表了内存中数据的使用情况(越往后就说明越久没有被使用)

核心逻辑:
查的时候,先通过hash表找有没有,有的话直接取值,并把对应节点移动至链表头部,没有的话新建节点,放入链表头部
插入数据,先通过hash表找有没有,有的话更新并移向头部,没有的话再判断容量满没满,满了就删除最后一个节点(同时也删除hash表中的映射,所以需要节点中保存key),然后再往头部插入节点并建立hash表映射。

待纠错
一直出错的原因是当链表达到最大长度删除最后一个节点的时候忘记连tail的pre指针了。。。

class LRUCache {
private:
    struct Node{
        int key;
        int val;
        Node *pre;
        Node *next;
        Node(int x,int y) :key(x),val(y), pre(nullptr), next(nullptr){};
    };
    Node *head, *tail;
    map<int, Node *> rec;
    int count, size;

    void moveToHead(Node *&node){
        Node *pre = node->pre, *next = node->next;
        pre->next = next;
        next->pre = pre;

        next = head->next;
        node->next = next;
        next->pre = node;
        head->next = node;
        node->pre = head;
    }
public:
    LRUCache(int capacity) {
        size = capacity;
        count = 0;
        head = new Node(0,0);
        tail = new Node(0,0);
        head->next = tail;
        tail->pre = head;
    };

    int get(int key) {
        if (rec.find(key) == rec.end())
            return -1;
        else{
            Node *node = rec[key];//get the val

            //move the node to head

            moveToHead(node);
            return node->val;
        }
    };

    void put(int key, int value) {
        if (rec.find(key) != rec.end()){
            Node *node = rec[key];
            moveToHead(node);
            node->val = value;
            return;
        }
        else{
            if (count == size){
                Node *cur = tail->pre, *pre = cur->pre;
                rec.erase(cur->key);
                pre->next = tail;
                                tail->pre=pre;//之前出错就是因为漏了这个。。。
                delete cur;
                count--;
            }
            Node *node = new Node(key,value),*next=head->next;
            head->next = node;
            node->pre = head;

            next->pre = node;
            node->next = next;
            rec.insert(make_pair(key, node));
            
            count++;
        }
    };

};

相关文章

  • 146. LRU(待纠错)

    思路:通过哈希表迅速找到映射关系。通过双向链表和头、尾指针迅速定位第一个节点和最后一个节点,之所以用链表是为了确定...

  • 146. LRU Cache

    146. LRU Cache

  • LeetCode 146-150

    146. LRU缓存机制[https://leetcode-cn.com/problems/lru-cache/]...

  • LRU(leetcode.146)

    146. LRU 缓存机制[https://leetcode-cn.com/problems/lru-cache/...

  • 146. LRU 缓存

    146. LRU 缓存[https://leetcode.cn/problems/lru-cache/] 请你设计...

  • 2019-01-13

    LeetCode 146. LRU Cache Description Design and implement ...

  • 146. LRU 缓存

    题目地址(146. LRU 缓存) https://leetcode.cn/problems/lru-cache/...

  • LeetCode 146. LRU缓存机制(LRU Cache)

    146. LRU缓存机制 Python3 实现 LRU(最近最少使用) 缓存机制 更多可参见:https://en...

  • 算法第4天:LRU缓存机制

    leetcode 146. LRU缓存机制 middle 运用你所掌握的数据结构,设计和实现一个 LRU (最...

  • 实现LRU缓存算法

    本文基于LeetCode第146. LRU 缓存机制[https://leetcode-cn.com/proble...

网友评论

      本文标题:146. LRU(待纠错)

      本文链接:https://www.haomeiwen.com/subject/wgfqjctx.html