时间限制:1秒

空间限制:65536K

1

2

3

4

5

6

7

8

    设计一个数据结构,实现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操作的返回结果。
 

输入例子1:
2 p 1 1 p 2 2 g 1 p 2 102 p 3 3 g 1 g 2 g 3
输出例子1:
1 1 -1 3
例子说明1:
2 //Cache容量为2 p 1 1 //put(1, 1) p 2 2 //put(2, 2) g 1 //get(1), 返回1 p 2 102
//put(2, 102),更新已存在的key,不算被使用 p 3 3 //put(3, 3),容量超过限制,将最近最少使用的key=2清除 g 1
//get(1), 返回1 g 2 //get(2), 返回-1 g 3 //get(3), 返回3
 

这里与Leetcode不同的是,这里跟新的操作不算使用,只用跟新即可。
#include <iostream> #include <unordered_map> #include <list> using namespace
std; class LRUCache { public: LRUCache(int capacity) :_capacity(capacity) {} //
O(1) 时间 // 将元素放到最前面 int get(int key) { auto it = _m.find(key); if (it ==
_m.end()) return -1; int val = it->second->second; _list.erase(it->second); //
删除这一个链表 _list.push_front(make_pair(key, val)); _m[key] = _list.begin(); //
跟新Hash表头部 return val; } // 加入一个元素到Casche中 O(1) // 如果key存在, 将key移到开头 // 如果不存在,
插入新节点 // 如果容量超限, 删除最后一个节点 void put(int key, int value) { auto it =
_m.find(key); if (it != _m.end()) { it->second->second = value; return; }
_list.push_front(make_pair(key, value)); _m[key] = _list.begin(); if
(_list.size() > _capacity) { int key = _list.back().first; _m.erase(key);
_list.pop_back(); } } private: int _capacity; // Cache的最大长度 list<pair<int,
int>> _list; // 双向链表 // 一个哈希表 unordered_map<int, list<pair<int,
int>>::iterator> _m; }; /** * Your LRUCache object will be instantiated and
called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 =
obj->get(key); * obj->put(key,value); */ int main() { int n; cin >> n; LRUCache
Cache = LRUCache(n); int key, value; char op; while (cin >> op) { if (op ==
'p') { cin >> key >> value; Cache.put(key, value); } else if (op == 'g') { cin
>> key; cout << Cache.get(key) << endl; } } }
 

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信