题目要求:
设计一个数据结构,实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作: get 和 put。
int get(int key) – 如果key已存在,则返回key对应的值value(始终大于0);如果key不存在,则返回-1。
void put(int key, int value) – 如果key不存在,将value插入;如果key已存在,则使用value替换原先已经存在的值。如果容量达到了限制,LRU Cache需要在插入新元素之前,将最近最少使用的元素删除。
请特别注意“使用”的定义:新插入或获取key视为被使用一次;而将已经存在的值替换更新,不算被使用。
限制:请在O(1)的时间复杂度内完成上述2个操作。
输入描述
第一行读入一个整数n,表示LRU Cache的容量限制。 从第二行开始一直到文件末尾,每1行代表1个操作。
如果每行的第1个字符是p,则该字符后面会跟随2个整数,表示put操作的key和value。
如果每行的第1个字符是g,则该字符后面会跟随1个整数,表示get操作的key。
输出描述
按照输入中get操作出现的顺序,按行输出get操作的返回结果。
示例:
输入:
2
p 1 1
p 2 2
g 1
p 2 102
p 3 3
g 1
g 2
g 3
输出:
1
1
-1
3
解题思路:
put(key,value)在O(1)的时间内完成,可以使STD中的一个容器:双端链表list,由于list没有实现[]操作符重载,为了实现O(1)内查找,可以使用另一个容器:ordered_map。每次“使用”元素的时候,就将该元素调整到链表的首部,这样当超出容量的时候,直接删除链表末尾的元素及其在map中对应的值。
list介绍:
list是一种序列式容器。
list容器完成的功能实际上和双向链表极其相似,list中的数据元素是通过链表指针串连成逻辑意义上的线性表,也就是list也具有链表的主要优点,即:在链表的任一位置进行元素的插入、删除操作都是快速的。
由于list元素节点并不要求在一段连续的内存中,显然在list中是不支持快速随机存取的,因此对于迭代器,只能通过“++”或“–”操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的操作,这点,是与vector等不同的地方。
begin() #返回一个指向容器起始位置的iteratorrbegin() #返回list中末尾的迭代器end() #返回list末端下一位置的iteratorpush_back() #插入元素到list的末尾push_front() #从list的头部插入元素empty() #判断list是否为空resize() #调用resize(n)将list的长度改为只容纳n个元素,超出的元素将被删除,如果需要扩展那么调用默认构造函数T()将元素加到list末端。如果调用resize(n,val),则扩展元素要调用构造函数T(val)函数进行元素构造,其余部分相同clear() #清空list中的所有元素front() #返回list容器中的头部元素引用back() #返回list容器的最后一个元素的引用pop_back() #删除链表的末尾元素pop_front() #删除链表的首部元素swap() #交换两个链表,list1,swap(list2)和swap(list1,list2)都可以实现list1和list2的交换splice() #实现链表拼接/**将源list的内容部分或全部元素删除,拼插入到目的list,有三种函数声明dest_list.splice(iterator position,list<T,Allocator>& source_list) #将source_list的所有元素剪接到dest_list的position的后面dest_list.splice(iterator position,list<T,Allocator>& source_list, iterator it)#将source_list的it位置处的元素剪接到dest_list的position的后面dest_list.splice(iterator position,list<T,Allocator>& source_list, iterator first,iterator last)#将source_list的first到last的元素剪接到dest_list的position后面##测试#include<list>#include <iostream>using namespace std;int main(){list<int>list1,list2;for(int i=1;i<=4;i++) {list1.push_back(i);list2.push_back(i+10);}// list1 1 2 3 4// list2 11 12 13 14list<int>::iterator it=list1.begin();it++;list1.splice(it,list2);//1 11 12 13 14 2 3 4if(list2.empty()) cout<<"list2 is empty"<<endl;list2.splice(list2.begin(),list1,it);cout<<*it<<" "<<endl;/*list1 1 11 12 13 14 3 4list2 2这里的it的值还是2,但是指向的已经是list2中的了 */it=list1.begin();advance(it,3);//advance 的意思是增加的意思,就是相当于 it=it+3;这里指向13list1.splice(list1.begin(),list1,it,list1.end()); //13 14 3 4 1 11 12 可以发现it到list1.end()被剪贴到list1.begin()前面了 for(list<int>::iterator it=list1.begin();it!=list1.end();++it) cout<<*it<<" ";cout<<endl;for(list<int>::iterator it=list2.begin();it!=list2.end();++it) cout<<*it<<" ";cout<<endl;list<pair<int,int> > list3;for(i=1;i<=3;i++)list3.push_back(make_pair(i,i+3));list<pair<int,int> >::iterator iter=list3.begin();cout<<iter->first<<" "<<iter->second<<endl;return 0;} ##结果list2 is empty213 14 3 4 1 11 1221 4**/
unordered_map介绍
1、与map的区别
map的内部实现是红黑树(红黑树是一种严格的平衡二叉搜索树),因此该容器具有自动排序的功能,map内部的所有元素都是有序的。对map的所有操作都是基于红黑树,因此很多操作都可以在O(logn)的时间内完成,map适用于对元素顺序有要求的场合。
缺点:由于红黑树的节点需要保存节点指针和数据域,所以红黑树的空间开销比较大。
unorder_map的内部实现是哈希表,并且使用开放链表寻址法解决冲突问题,因此元素的查找速度可以达到O(1),适用于对于查找操作有较高才做的场合。
缺点:哈希表的时间复杂度比较高。
2、使用
find(key) #返回key所对应的迭代器,如果该迭代器与end()相等,说明map中不存在key。count(key) #返回key在map中出现的次数,如果为0说明key不在map中iterator erase(const_iterator pos ) #移除map中pos处键值对iterator erase(const_iterator first, const_iterator last );#移除map中first到last的键值对size_type erase(const key_type& key )#移除特定key的键值对。begin() #返回指向容器起始位置的迭代器end() #返回指向容器末尾位置的迭代器 cbegin() #返回指向容器起始位置的常迭代器(const_iterator) cend() #返回指向容器末尾位置的常迭代器 insert() #插入元素 /**unordered_map的迭代器是一个指针,指向这个元素,通过迭代器来取得它的值。unordered_map<Key,T>::iterator it;(*it).first; // the key value (of type Key)(*it).second; // the mapped value (of type T)(*it); // the "element value" (of type pair<const Key,T>) it->first;// 同 (*it).first (the key value)it->second; // 同(*it).second (the mapped value) **/
实现代码:
#include <iostream>#include <unordered_map>#include <list>#include <string>#include <sstream>using namespace std;class LRUCache{private:int cap;list<pair<int,int>> L;unordered_map<int,list<pair<int,int>>::iterator> m;public:LRUCache(int capacity){cap=capacity;}int get(int key){auto it=m.find(key);if(it == m.end()) return -1;L.splice(L.begin(),L,it->second);return it->second->second;}void put(int key,int value){auto it=m.find(key);if(it != m.end()) {it->second->second=value;}else{L.push_front(make_pair(key,value));m[key]=L.begin();}if(m.size() > cap){int k=L.rbegin()->first;L.pop_back();m.erase(k);}}};int main(){int n;cin>>n;LRUCache L(n);string cmd;char commond;while(getline(cin,cmd)){istringstream iss(cmd);iss>>commond;if(commond=='p'){int key,val;iss>>key>>val;L.put(key,val);}else if(commond=='g'){int key;iss>>key;int val=L.get(key);cout<<val<<endl;}}return 0;}
注意
按行读取输入,每一行的输入通过getline(cin,cmd)读入到cmd中,然后通过istringstream iss(cmd)构造一个字符串输入流,然后从中解析出字符、整数。
如果觉得《数据结构LRUCache(Least Recently Used – 最近最少使用缓存)》对你有帮助,请点赞、收藏,并留下你的观点哦!