问题：LRU 缓存机制, 设计和实现一个 LRU（最近最少使用）缓存数据结构，使它应该支持一下操作：get 和 put。get(key) - 如果 key 存在于缓存中，则获取 key 的 value（总是正数），否则返回 -1。put(key,value) - 如果 key 不存在，请设置或插入 value。当缓存达到其容量时，它应该在插入新项目之前使最近最少使用的项目作废。

出题人：阿里巴巴出题专家：文景／阿里云 CDN 资深技术专家。

参考答案：

Python:

class LRUCache(object): def __init__(self, capacity): """ :type capacity: int """ self.cache = {} self.keys =  self.capacity = capacity def visit_key(self, key): if key in self.keys: self.keys.remove(key) self.keys.append(key) def elim_key(self): key = self.keys[0] self.keys = self.keys[1:] del self.cache[key] def get(self, key): """ :type key: int :rtype: int """ if not key in self.cache: return -1 self.visit_key(key) return self.cache[key] def put(self, key, value): """ :type key: int :type value: int :rtype: void """ if not key in self.cache: if len(self.keys) == self.capacity: self.elim_key self.cache[key] = value self.visit_key(key)
def main: s = [["put","put","get","put","get","put","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[ 4,4],[1],[3],[4]]] obj = LRUCache(2) l= for i,c in enumerate(s[0]): if(c == "get"): l.append(obj.get(s[1][i][0])) else: obj.put(s[1][i][0], s[1][i][1]) print(l)
if __name__ == "__main__": main

C++

class LRUCache{ public: LRUCache(int capacity) { cap = capacity; } int get(int key) { auto it = m.find(key); if (it == m.end) return -1; l.splice(l.begin, l, it->second); return it->second->second; } void set(int key, int value) { auto it = m.find(key); if (it != m.end) l.erase(it->second); l.push_front(make_pair(key, value)); m[key] = l.begin; if (m.size > cap) { int k = l.rbegin->first; l.pop_back; m.erase(k); } }}