题目-中等难度

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例

示例：

提示：

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 链表

时间
2428ms
击败 96.49%使用 Python 的用户
内存
75.66mb
击败 44.44%使用 Python 的用户

class DoubleLinkedNode:
    def __init__(self, key=0,value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.dic = {}
        # 创建节点作为列表头
        self.head = DoubleLinkedNode()
        # 创建节点作为列表尾
        self.tail = DoubleLinkedNode()
        # 新建链表只有表头和表尾，让表头下一项为表尾
        self.head.next = self.tail
        # 让表尾前一项为表头，完成链表连接
        self.tail.prev = self.head
        self.l = 0


    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        # 如果key不存在于字典，返回-1
        if key not in self.dic:
            return -1
        # 如果存在，获取节点
        node = self.dic[key]
        # 把节点移至头
        self.moveToHead(node)
        # 返回节点值
        return node.value


    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        # 如果未在字典中
        if key not in self.dic:
            # 创建新节点
            node = DoubleLinkedNode(key,value)
            # 将节点添加至字典
            self.dic[key] = node
            # 将节点添加至头部
            self.addToHead(node)
            # 计数字典中节点个数
            self.l += 1
            # 如果数量超出容量
            if self.l > self.capacity:
                # 获取尾部节点
                exNode = self.tail.prev
                # 移除尾部节点
                self.removeNode(exNode)
                # 移除字典中的尾部节点
                self.dic.pop(exNode.key)
                # 字典节点数-1
                self.l -= 1
        # 如果存在于字典
        else:
            # 获取原先存在的节点
            node = self.dic[key]
            # 更新节点值
            node.value = value
            # 更新过后移到链表头
            self.moveToHead(node)

    def addToHead(self, node):
        # node在self.head后面
        node.prev = self.head
        # node在self.head下一个节点的前面
        node.next = self.head.next
        # self.head和它下一个节点中间插入node节点
        self.head.next.prev = node
        # 让node成为self.head下一个节点
        self.head.next = node

    def removeNode(self, node):
        # 让节点前一项的next存储节点下一项的地址
        node.prev.next = node.next
        # 节点的下一项的prev存储节点前一项的地址，删除了节点并重新连接链表结构
        node.next.prev = node.prev

    def moveToHead(self, node):
        # 移除原先的node
        self.removeNode(node)
        # 将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)

Ashiu

146. LRU 缓存

146. LRU 缓存

题目-中等难度

示例

1. 链表