time limit ：1 second
Space constraints ：65536K
1
2
3
4
5
6
7
8
Design a data structure , realization LRU Cache Function of (Least Recently Used – Least recently used cache ). It supports the following 2 Actions ： get and
put.
int get(int key) – If key Already exists , Return to key Corresponding value value（ Always greater than 0）; If key non-existent , Return to -1.
void put(int key, int value) –
If key non-existent , take value insert ; If key Already exists , Then use value Replace the value that already exists . If the capacity reaches the limit ,LRU
Cache You need to , Remove the least recently used elements .
Please pay special attention “ use ” Definition of ： New insert or get key Deemed to be used once ; The existing values are replaced and updated , It doesn't count as being used .
limit ： Please at O(1) Within the time complexity of the above 2 Actions .
Enter a description :
The first line reads an integer n, express LRU Cache Capacity limits for . From the second line to the end of the file , each 1 Bank representative 1 Actions .
If the 1 Characters are p, The character is followed by 2 Integers , express put Operational key and value.
If the 1 Characters are g, The character is followed by 1 Integers , express get Operational key.
Output description :
According to the input get Sequence of operations , Output by line get The return result of the operation .
Input example 1:
2 p 1 1 p 2 2 g 1 p 2 102 p 3 3 g 1 g 2 g 3
Output example 1:
1 1 -1 3
Examples 1:
2 //Cache The capacity is 2 p 1 1 //put(1, 1) p 2 2 //put(2, 2) g 1 //get(1), return 1 p 2 102
//put(2, 102), Update existing key, It doesn't count as being used p 3 3 //put(3, 3), Capacity exceeds limit , Most recently used key=2 eliminate g 1
//get(1), return 1 g 2 //get(2), return -1 g 3 //get(3), return 3
Here and here Leetcode The difference is that , The new operation is not used here , Just follow the new .
#include <iostream> #include <unordered_map> #include <list> using namespace
std; class LRUCache { public: LRUCache(int capacity) :_capacity(capacity) {} //
O(1) time // Put the element first int get(int key) { auto it = _m.find(key); if (it ==
_m.end()) return -1; int val = it->second->second; _list.erase(it->second); //
Delete this list _list.push_front(make_pair(key, val)); _m[key] = _list.begin(); //
Keep up with the new Hash Head part return val; } // Add an element to Casche in O(1) // If key existence , take key Move to the beginning // If it doesn't exist ,
Insert new node // If the capacity exceeds the limit , Delete last node 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 Maximum length of list<pair<int,
int>> _list; // Double linked list // A hash table 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; } } }
Technology