设计一个LRU缓存，要求实现put和get方法，时间复杂度为O(1)。

Question

Accepted Answer

LRU（Least Recently Used）缓存是一种缓存淘汰策略，当缓存满时，会优先淘汰最久未使用的数据。可以使用哈希表和双向链表来实现LRU缓存。哈希表用于快速查找数据，双向链表用于维护数据的访问顺序。以下是Python代码实现：
python
class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = dict()
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)
        else:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size -= 1

def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

在这段代码中，哈希表self.cache用于存储键值对，双向链表用于维护数据的访问顺序。get方法和put方法的时间复杂度都是$O(1)$。