Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
思路：
这题吧，思路挺清楚的，就是每次get, set时都把对应的数据设为时间最近的数据，如果满了，就在set时把最老的数据扔掉，把新的插入到最近的位置。
关键是，如何在O(1)的时间内get到所需的数据，如何在O(1)的时间内，找到最老的数据。
第一个问题可以用unordered_map轻松解决，但是，第二个问题我就不会了。我很low的用了遍历，果断超时了。看答案后发现，要用list的splice函数解决。
把所有的数据按照访问时间由近到远存放在一个list中，当再次访问里面的数据时，就把该数据移动到list的开始位置，满了后就移除list的最后一个元素。
上大神的答案：
class LRUCache {
private:
// A list of (key, value) pairs
list<pair<int, int>> items;
// Map items to iterators (pointers) to list nodes
unordered_map<int, list<pair<int, int>>::iterator> cache;
// The capacity of the list
int capacity;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
// If key is not found in hash map, return -1
if (cache.find(key) == cache.end())
return -;
// Move the (key, value) pair to the beginning of the list
items.splice(items.begin(), items, cache[key]);
return cache[key]->second;
}
void set(int key, int value) {
// The key is not in the hash table
if (cache.find(key) == cache.end()) {
// If the cache is full then delete the least recently
// used item, which is at the end of the list
if (items.size() == capacity) {
cache.erase(items.back().first);
items.pop_back();
}
items.push_front(make_pair(key, value));
cache[key] = items.begin();
} else {
// Update the value associated with the key
cache[key]->second = value;
// Move the (key, value) pair to the beginning of the list
items.splice(items.begin(), items, cache[key]);
}
}
}
我的代码，时间是用自己设的time来记录的，超时了。
typedef struct Data
{
int value;
int time;
Data(){}
Data(int v, int t) : value(v), time(t){}
}Data; class LRUCache{
public:
LRUCache(int capacity) {
t = ; //初始化时间
c = capacity; //初始化容量
} int get(int key) {
unordered_map<int, Data>::iterator it = record.find(key);
if(it == record.end())
{
return -;
}
else
{
it->second.time = t++;
return it->second.value;
} } void set(int key, int value) {
if(record.find(key) != record.end())
{
record[key].value = value;
record[key].time = t++;
return;
}
if(record.size() == c) //容量已经达到
{
unordered_map<int, Data>::iterator replace = record.begin();
for(unordered_map<int, Data>::iterator it = record.begin(); it != record.end(); it++)
{
replace = (it->second.time < replace->second.time) ? it : replace;
}
record.erase(replace); //删掉时间最早的
} Data newData(value, t);
record[key] = newData;
t++;
}
private:
unordered_map<int, Data> record;
int c;
int t;
};