[数据结构与算法] LRUCache的两种写法（Python）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LRUCache的两种写法（Python） -> 正文阅读

[数据结构与算法]LRUCache的两种写法（Python）

LeetCode链接

手动实现双向链表 + dict 时间复杂度 get put O(1)

class Node:
    def __init__(self, k=0, v=0):
        self.k = k
        self.v = v
        self.next = None
        self.prev = None

class LRUCache:

    def __init__(self, capacity: int):
        # dict 的value存储链表的node节点
        self.data = {}
        self.capacity = capacity
        self.size = 0
        # 虚拟头尾节点
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.data:
            n = self.data[key]
            # 将节点移动至尾部
            self._remove(n)
            self._add(n)
            return n.v
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            n = self.data[key]
            n.v = value
            # 将节点移动至尾部
            self._remove(n)
            self._add(n)
        else:
            n = Node(key, value)
            self.data[key] = n
            self._add(n)
            self.size += 1
            if self.size > self.capacity:
                n_to_remove = self.head.next
                self._remove(n_to_remove)
                # 记得把对应的键清除
                self.data.pop(n_to_remove.k)    

    def _remove(self, n: Node):
        n_prev = n.prev
        n_next = n.next
        n_prev.next = n_next
        n_next.prev = n_prev
    
    def _add(self, n: Node):
        """
        此处add始终在尾部添加 配合_remove可以把常用的节点移动到链表的尾部
        自然，头部就是最不经常使用的节点，长度超限，删除之即可
        """
        tail_prev = self.tail.prev
        tail_prev.next = n
        n.prev = tail_prev
        n.next = self.tail
        self.tail.prev = n

基于已有的 collections.OrderedDict

class LRUCache(collections.OrderedDict):

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity


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

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)