题解 | #设计LRU缓存结构#
设计LRU缓存结构
https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84
/** * Your Solution object will be instantiated and called as such: * Solution* solution = new Solution(capacity); * int output = solution->get(key); * solution->set(key,value); */ /* //哈希表:根据key直接访问value的一种数据结构。用来统计频率、快速检验某个元素是否出现过等。 // 设计LRU(最近最少使用)缓存结构,该结构在构造时确定大小,假设大小为 capacity ,操作次数是 n ,并有如下功能: // 1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 // 2. get(key):如果关键字 key 存在于缓存中,则返回key对应的value值,否则返回 -1 。 // 3. set(key, value):将记录(key, value)插入该结构,如果关键字 key 已经存在,则变更其数据值 value,如果不存在,则向缓存中插入该组 key-value ,如果key-value的数量超过capacity,弹出最久未使用的key-value */ #include <list> class Solution { list<pair<int,int>> dou_list;//双向链表 unordered_map<int, list<pair<int, int>>::iterator> m;//一个容器map //unordered_map是一个将key和value关联起来的容器,它可以高效的根据单个key值查找对应的value。 //用链表存,链表头部是最近使用的,尾部是最后使用的,如果要删去,就直接把尾部删去 int n_capacity; public: Solution(int capacity){ // write code here n_capacity=capacity; } int get(int key) { // write code here if(m.count(key)) { //放在头部,需要tmp存着,然后删掉这个位置,再放到头部 auto tmp=*m[key]; dou_list.erase(m[key]); dou_list.push_front(tmp);//把它放在最前面==在容器头部插入一个数据 m[key]=dou_list.begin(); //return tmp.second; return dou_list.front().second; } return -1; } void set(int key, int value){ // write code here if(m.count(key)) { //如果map容器m的key存在 dou_list.erase(m[key]);//删除这个位置的key } else if(n_capacity==dou_list.size()) { //删掉末尾的 auto tmp_f=dou_list.back();//末尾元素赋值给tmp——f m.erase(tmp_f.first); dou_list.pop_back();//尾删法 } dou_list.push_front(pair<int,int>(key,value)); m[key]=dou_list.begin(); } };