原題連接： 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.

題目要求設(shè)計和實現(xiàn)一個給LRU Cache用的數(shù)據(jù)結(jié)構(gòu)，要求包含兩個操作， get 和 set。首先題目有一點沒有講清楚，那就是當(dāng)要插入的（key，value)已經(jīng)存在時的行為。題目只是說當(dāng)key不存在時插入，而當(dāng)要插入的key已經(jīng)存在時的行為如何，題目并沒有說明，是覆蓋舊的value還是直接返回。我是通過提交代碼，發(fā)現(xiàn)當(dāng)要插入的key已經(jīng)存在時，用新的value覆蓋舊的value。網(wǎng)絡(luò)上有很多關(guān)于用一個hash table 和一個list實現(xiàn)的代碼，我就不再累述。下面講述我用兩個hash table的實現(xiàn)。一個叫cache的用于保存數(shù)據(jù)的<key，value>，另一個叫stamp用于保存<key，timeStamp>。get操作很簡單，直接在cache里面查找并返回相應(yīng)的結(jié)果，同時要更新stamp里的時間戳。set操作先檢查要插入的key是否已經(jīng)存在。如果存在，更新value和time stamp并返回。如果不存在，并且cache的數(shù)據(jù)個數(shù)小于capacity，直接執(zhí)行插入操作。如果capacity已經(jīng)滿了，就從stamp里查找時間戳最小的key，此時需要O(capacity)的時間復(fù)雜度。然后把對應(yīng)的數(shù)據(jù)刪除并插入當(dāng)前的<key，value>。 C++實現(xiàn)如下：

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;    }};