注意的点：

1、这道题本质是要求一个可以排序的字典（因为O（1）的时间复杂度就是字典），所以要不就用collections自带的OrderDict，要不然就用字典加双头链表自己实现一个。
2、OrderedDict的两个方法：
.move_to_end(key, last=False)：把元素后移一位，last=True的话就是移动到最后
.popitem(last=True)：把最后位置的元素pop出去

解法一：python的OrderDict

from collections import OrderedDictclass LRUCache:def __init__(self, capacity: int):self.capacity = capacityself.cache = OrderedDict()def get(self, key: int) -> int:if key in self.cache:self.cache.move_to_end(key, last=False)return self.cache[key]else:return -1def put(self, key: int, value: int) -> None:self.cache[key] = valueself.cache.move_to_end(key, last=False)if len(self.cache) > self.capacity:self.cache.popitem(last=True)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

解法二：字典加双链表

class LRUCache:def __init__(self, capacity: int):self.max = capacityself.store = dict()  self.head = Linknode(None, None)self.tail = self.headdef get(self, key: int) -> int:if key not in self.store.keys():return -1self.addcurrentnode2tail(key)return self.store[key]def put(self, key: int, value: int) -> None:if key not in self.store.keys():node = Linknode(None, key)self.tail.next = node# self.tail = self.tail.nextself.tail = nodeif len(self.store.keys()) == self.max:tempnode = self.head.nextremoved_key = tempnode.valself.head.next = tempnode.nexttempnode.next = Noneself.store.pop(removed_key)self.store[key] = valueelse:  # 找到这个self.addcurrentnode2tail(key)self.store[key] = valuedef addcurrentnode2tail(self, akey):print(889, self.head)hi = self.headwhile hi.next:if hi.next.val == akey:breakhi = hi.next# 把hi移动到链表的尾部(可能已经是末尾了)if hi.next.next:temp = hi.next.nexthi.next.next = Noneself.tail.next = hi.nexthi.next = tempself.tail = self.tail.nextclass Linknode:def __init__(self, ne=None, val=None):self.next = neself.val = val
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)