题目描述

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

解题思路

LRU的思想是一种最近最少使用的缓存机制，也就是对于cache已有的数据，每次访问它会使它移到最前面，对于cache没有的数据，会直接加到最前面（如果超出了cache的缓存大小，则将最后面的一个数据删除）
主要思路是使用双链表+hash
python中的hash使用字典来实现，存储key与node的一一对应关系
双链表来模拟cache，每个节点node代表一个key包含的数据值

代码

class DLinkList:
    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.capacity = capacity
        #创建头结点和尾结点，方便操作
        self.head = DLinkList()
        self.tail= DLinkList()
        self.head.next = self.tail
        self.tail.prev = self.head
        #初始长度为0
        self.size = 0
        #建立一个字典，存储对应关系
        self.cache = dict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        #如果key存在，则把key对应的节点移到链表头部，并返回其值
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            #先创建新节点，并将节点与key的对应关系加到cache，再将这个节点加入到链表头部
            node = DLinkList(key, value)
            self.cache[key] = node
            self.addToHead(node)
            self.size += 1
            #判断是否超出了缓存大小
            if self.size > self.capacity:
                #移除链表队尾
                remove = self.removeTail()
                #删除cache的对应索引
                self.cache.pop(remove.key)
                self.size -= 1
        else:
            #如果key存在，则直接将对应节点移到链表队头，且修改value
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

    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 removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

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

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