实现一个LRU（最近最少使用）缓存，要求支持get和put操作，且时间复杂度都为O(1)。

Question

Accepted Answer

要实现一个LRU缓存，我们可以使用Python的`OrderedDict`。`OrderedDict`是一个有序的字典，它可以记住元素插入的顺序。以下是Python代码实现：
python
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

def get(self, key):
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return -1

def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)
在这个实现中，`get`操作时，如果键存在于缓存中，将该键值对移动到字典的末尾，表示最近使用过，然后返回对应的值；如果键不存在，则返回-1。`put`操作时，如果键已经存在，将该键值对移动到字典的末尾；如果键不存在，将其添加到字典中。如果缓存的容量超过了限制，删除字典中最旧的元素。由于`OrderedDict`的`move_to_end`和`popitem`操作的时间复杂度都是O(1)，所以`get`和`put`操作的时间复杂度也都是O(1)。