首页 💻 数据结构,📝 算法学习

题目传送门

https://leetcode-cn.com/problems/lru-cache/

题意

设计实现一个 LRU 缓存机制, 至于 LRU 是什么, 请参看百度百科

思路

内部实现数据结构是双向链表+散列表, 散列表的每一个 key 是当前的 key , value 是指向链表中该节点的指针; 双向链表是用来存储每个节点信息的(最近使用过的节点最靠前)

  • get 操作: 如果当前散列表中存在此 key , 则将其移到链表的最前面, 然后返回该 value ; 否则返回-1
  • set 操作: 如果当前散列表中存在此 key , 则更新散列表中的value; 如果不存在该 key 并且链表长度小于 capacity , 则新建节点放在最前面并将散列表指向当前节点; 如果如果不存在该 key 并且链表长度大于或等于 capacity , 则删除链表中最后面的节点再插入新的节点

代码

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> nodeList;
    unordered_map<int, list<pair<int, int>>::iterator> mp;

public:
    LRUCache(int capacity) {
        this -> capacity = capacity;
    }

    int get(int key) {
        if(mp.count(key)) {
            int ans = mp[key] -> second;
            nodeList.erase({mp[key]});
            nodeList.push_front({key, ans});
            mp[key] = nodeList.begin();
            return ans;
        }
        return -1;
    }

    void put(int key, int value) {
        if(get(key) != -1) {
            mp[key] -> second = value;
        } else if(this -> capacity > nodeList.size()) {
            nodeList.push_front({key, value});
            mp[key] = nodeList.begin();
        } else {
            int rKey = nodeList.back().first;
            mp.erase(rKey);
            nodeList.pop_back();
            nodeList.push_front({key, value});
            mp[key] = nodeList.begin();
        }
    }
};



文章评论