这是一道非常高频，非常经典的题目：

首先分析下题意：

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，当LRU cache中存在该键时，则返回元素，不存在则返回－1。同时因为LRU cache纪录的是最近访问的元素，所以在做了get操作后，该get的元素需要放到最后。

另一个功能是set, 如果该键不存在，则在最后插入该元素（如果达到容量上限，则删除最前端元素least recently used），如果存在则和get中类似，将该元素移动到最后。

快速的访问键值，很容易想起使用hashmap, 但是另外一点是需要移动位置来反映元素的访问顺序，这个在经典的dict中没有实现，当然一个神器是可以纪录插入字典顺序的collections.OrderedDict(). OrderedDict()本身是使用dict和doubly linked list来实现的，doubly linked list的优点是O(1)时间删除和插入元素，则可以O(1)时间实现移动元素到队尾的功能。代码如下：

 

class node(object):        def __init__(self, key, value):            self.key = key            self.val = value            self.pre = None            self.next = None            class LRUCache:    # @param capacity, an integer    def __init__(self, capacity):        self.head = None        self.tail = None        self.map = {}        self.capacity = capacity    #remove node         def removeNode(self, key):        n = self.map[key]        if n != self.head:            n.pre.next = n.next            n.next.pre = n.pre        else:            self.head = n.next            if n.next:               n.next.pre = None        self.map.pop(key)    # add node at the end of doubly linked list        def addEnd(self, key, value):        n = node(key, value)        n.pre = self.tail        if self.tail:            self.tail.next = n        self.tail = n        self.map[key] = n        if not self.head: #in case the capacity is 1            self.head = n                def get(self, key):        if key not in self.map:            return -1        else:            value = self.map[key].val            if self.map[key] != self.tail:                self.removeNode(key)                self.addEnd(key, value)            return value        def set(self, key, value):        if key in self.map:            if self.map[key] != self.tail:                 self.removeNode(key)                self.addEnd(key, value)               else:                self.tail.val = value                   self.map[key] = self.tail        else:            if len(self.map) == self.capacity:                self.removeNode(self.head.key)            self.addEnd(key, value)

OrderedDict:

class LRUCache(object):    def __init__(self, capacity):        """        :type capacity: int        """        self.map = collections.OrderedDict()   #dict inside        self.capacity = capacity            def get(self, key):        """        :rtype: int        """        if key not in self.map:            return -1        else:           value = self.map[key]           self.map.pop(key)           self.map[key] = value           return value            def set(self, key, value):        """        :type key: int        :type value: int        :rtype: nothing        """        if key in self.map:            self.map.pop(key)            self.map[key] = value        else:            if self.capacity == len(self.map):                self.map.popitem(last = False)                self.map[key] = value            else:                self.map[key] = value