【leetcode】LRU Cache(hard)★

浏览数：25 / 时间：2015年06月20日

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 -1;
        // 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 = 0;                //初始化时间
        c = capacity;         //初始化容量
    }
    
    int get(int key) {
        unordered_map<int, Data>::iterator it = record.find(key);
        if(it == record.end())
        {
            return -1;
        }
        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;
};