LRU Cache -- Lintcode 134

原题连接： http://www.lintcode.com/en/PRoblem/lru-cache/

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.

题目要求设计和实现一个给LRU Cache用的数据结构，要求包含两个操作， get 和 set。首先题目有一点没有讲清楚，那就是当要插入的（key，value)已经存在时的行为。题目只是说当key不存在时插入，而当要插入的key已经存在时的行为如何，题目并没有说明，是覆盖旧的value还是直接返回。我是通过提交代码，发现当要插入的key已经存在时，用新的value覆盖旧的value。网络上有很多关于用一个hash table 和一个list实现的代码，我就不再累述。下面讲述我用两个hash table的实现。一个叫cache的用于保存数据的<key，value>，另一个叫stamp用于保存<key，timeStamp>。get操作很简单，直接在cache里面查找并返回相应的结果，同时要更新stamp里的时间戳。set操作先检查要插入的key是否已经存在。如果存在，更新value和time stamp并返回。如果不存在，并且cache的数据个数小于capacity，直接执行插入操作。如果capacity已经满了，就从stamp里查找时间戳最小的key，此时需要O(capacity)的时间复杂度。然后把对应的数据删除并插入当前的<key，value>。 C++实现如下：

class LRUCache{public:    // @param capacity, an integer    int currTime;    int cap;    unordered_map<int, int> cache;    unordered_map<int, int> stamp;        LRUCache(int capacity) {        // write your code here        currTime = 0;        cap = capacity;        cache.reserve(capacity);        stamp.reserve(capacity);    }        // @return an integer    int get(int key) {        // write your code here        if (cache.count(key))        {            ++currTime;            stamp[key] = currTime;                        return cache[key];        }                return -1;    }    // @param key, an integer    // @param value, an integer    // @return nothing    void set(int key, int value) {        // write your code here            ++currTime;                 if (cache.count(key))        {            cache[key] = value;            stamp[key] = currTime;            return;        }        if (cache.size() < cap)        {            cache[key] = value;            stamp[key] = currTime;                        return;        }                int minTime = INT_MAX;        unordered_map<int, int>::iterator leIt, it = stamp.begin();                while (it != stamp.end())        {            if (it->second < minTime)            {                minTime = it->second;                leIt = it;            }                        ++it;        }                unordered_map<int, int>::iterator cacheIt = cache.find(leIt->first);        cache.erase(cacheIt);        cache[key] = value;                stamp.erase(leIt);        stamp[key] = currTime;    }};