©2020-2024 ioDraw All rights reserved,
Privacy Policy
时间限制：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; } } }