难度：中等

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

解题思路：
本题使用双向链表和哈希表来解决。使用链表是为了表示头部的键值对是最近使用的，而尾部的键值对是最久没有使用的。那为什么不使用单链表呢？因为一旦删除了尾结点，我们无法知道尾结点的上一个节点是谁，所以需要在尾结点前加入pre指向前一个节点，也就是双向链表。使用哈希表的目的是可以在O(1)时间内找到key所对应的节点，这个节点存有key所对应的value。

python代码：

# 双向链表+哈希表
class DLinkedNode:
    def __init__(self, key=0, value=0) -> None:
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

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

    def get(self, key: int) -> int:
        if key in self.hash_map:
            self.removeNode(self.hash_map[key])
            self.moveTohead(self.hash_map[key])
            return self.hash_map[key].value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hash_map:
            self.hash_map[key].value = value
            self.removeNode(self.hash_map[key])
            self.moveTohead(self.hash_map[key])
        else:
            Node = DLinkedNode(key, value)
            if self.size < self.capacity:
                self.size += 1
            else:
                self.hash_map.pop(self.tail.prev.key)
                self.removeNode(self.tail.prev)
            self.hash_map[key] = Node
            self.moveTohead(Node)

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

    def moveTohead(self, Node):
        Node.next = self.head.next
        self.head.next.prev = Node
        self.head.next = Node
        Node.prev = self.head



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

复杂度分析：

• 时间复杂度 O ( 1 ) O(1) O(1)：查找、添加、删除、移动到头节点（插入），都是常数时间；
• 空间复杂度 O ( c a p a c i t y ) O(capacity) O(capacity)：双向链表和哈希表最多存储 c a p a c i t y capacity capacity个节点。