Python的dictionary查找元素O(1)时间, 但缺点是无序。而collections.OrderedDict是有序的, 后加入的元素一定排在先加入元素的后面, 操作和dictionary类似:

import collections
a = collections.OrderedDict()
a[1] = 10 # 若1在a中就更新其值, 若1不在a中就加入(1, 10)这一对key-value。
a[2] = 20
a[3] = 30
del a[2]
a.popitem(last = True) # 弹出尾部的元素
a.popitem(last = False) # 弹出头部的元素

一开始总超时, 因为手动判断了一个key在不在OrderedDict中, 使用try...except...就过了。由于except只有KeyError一种, 所以不用写明。实际上except: 比 except KeyError: 要快一点点。但是使用OrderedDict纯属作弊，所以以下的Solution 1仅供说明Python的丰富数据类型:

# Solution 1, you are cheating!  作弊解法，等于没做

class LRUCache:
    # @param capacity, an integer
    def __init__(self, capacity):
        LRUCache.Dict = collections.OrderedDict()
        LRUCache.capacity = capacity
        LRUCache.numItems = 0

    # @return an integer
    def get(self, key):
        try:
            value = LRUCache.Dict[key]
            del LRUCache.Dict[key]
            LRUCache.Dict[key] = value
            return value
        except:
            return -1
        
    # @param key, an integer
    # @param value, an integer
    # @return nothing
    def set(self, key, value):
        try:
            del LRUCache.Dict[key]
            LRUCache.Dict[key] = value
            return
        except:
            if LRUCache.numItems == LRUCache.capacity:
                LRUCache.Dict.popitem(last = False)
                LRUCache.numItems -= 1
            LRUCache.Dict[key] = value
            LRUCache.numItems += 1
        return

好吧，正常的实现是Hash + Doubly Linked List (双向链表):

# Solution 2, now you become serious...

class LRUCache:
    # dictionary + doubly linked list, see the picture in http://www.programcreek.com/2013/03/leetcode-lru-cache-java/
    class Node:
        def __init__(self, key, value):
            self.prev = None
            self.key = key
            self.value = value
            self.next = None

    # @param capacity, an integer
    def __init__(self, capacity):
        self.capacity, self.dict = capacity, {}
        self.head, self.tail = self.Node('head', 'head'), self.Node('tail', 'tail') # dummy head node and dummy tail node
        self.head.next = self.tail
        self.tail.prev = self.head

    # @return an integer
    def get(self, key):
        if key not in self.dict:
            return -1
        else:
            self.insertNodeAtFirst(self.unlinkNode(self.dict[key]))
            return self.dict[key].value

    # @param key, an integer
    # @param value, an integer
    # @return nothing
    def set(self, key, value):
        if key in self.dict:
            self.insertNodeAtFirst(self.unlinkNode(self.dict[key]))
            self.dict[key].value = value
        else:
            if len(self.dict) >= self.capacity: # remove the least recently used element
                del self.dict[self.unlinkNode(self.tail.prev).key]
            self.dict[key] = self.Node(key, value)
            self.insertNodeAtFirst(self.dict[key])
    
    def unlinkNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        return node
        
    def insertNodeAtFirst(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node