首页 > 编程语言 >[Python手撕]LRU

[Python手撕]LRU

时间:2024-09-01 14:16:03浏览次数:10  
标签:node map Python self value next LRU key

class Node:
    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.length = 0
        self.map = {}
        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.map:
            self.remove(self.map[key])
            self.refresh(self.map[key])
            return self.map[key].value
        else:
            return -1
        

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self.map[key].value = value
            self.remove(self.map[key])
            self.refresh(self.map[key])
        else:
            if self.length == self.capacity:
                t = self.head.next.key
                self.remove(self.head.next)
                del self.map[t]
                node = Node(key, value)
                self.refresh(node)
                self.map[key] = node
            else:
                node = Node(key, value)
                self.refresh(node)
                self.map[key] = node
                self.length += 1

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

    def refresh(self, node):
        node.prev = self.tail.prev
        self.tail.prev.next = node
        node.next = self.tail
        self.tail.prev = node

    def show(self):
        cur = self.head.next
        while cur.next:
            print(cur.key,cur.value, end="|")
            cur = cur.next
        print()


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

标签:node,map,Python,self,value,next,LRU,key
From: https://www.cnblogs.com/DCFV/p/18391248

相关文章

  • [Python手撕]LFU
    classNode:def__init__(self,key=0,val=0,pre=None,next=None,fre=0,tail=None):self.key=keyself.val=valself.pre=preself.next=nextself.fre=freself.tail=tailclassLFUCache:d......
  • python读取txt文本文件-批量更改mysql数据库中一批用户的用户名的python脚本保存及转
    一、python读取txt文本文件-批量更改mysql数据库中一批用户的用户名的python脚本保存    做一个简单的事:使用python读取一个txt文件,里面存储着N行用户id,需要一行行读取后再读取另一个存储用户昵称的txt文件,判断昵称是否有重复,如果没有重复就将数据库中的当前uid用户的昵称......
  • Python 数据结构——二叉树(最最最最最实用的二叉树教程)
    本文章以实用为主,所以不多废话直接开整本文所介绍的二叉树是最基础的二叉树,不是二叉搜索树,也不是平衡二叉树,就基本的二叉树二叉树的创建基本二叉树的创建其实比链表还要简单,只需创建一个节点的类即可,随后用指针将其串起来。不同于链表的是,二叉树为一个父节点连接到两个子节......
  • 用Python解决预测问题_对数线性模型模板
    对数线性模型(Log-linearmodel)是统计学中用于分析计数数据或频率数据的一类模型,特别是在多维列联表(contingencytables)分析中非常常见。这种模型通过取对数将乘法关系转换为加法关系,从而简化了数据分析。在对数线性模型中,我们通常对观测频数的对数进行建模,模型的形式可以表示......
  • 【Python系列】signal信号处理
    ......
  • 【Python系列】 参数默认规则
    ......
  • 20240901_113250 python 知识点列表
    开发环境20240901_113224python环境依赖的备份与导入_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/1188873020240901_114639填空题环境的备份与导入_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/11888767......
  • 【Python】标准库的使用
    Python通过模块来体现“库”降低了程序猿的学习成本提高了程序的开发效率库就是是别人已经写好了的代码,可以让我们直接拿来用荀子曰:“君子性非异也,善假于物也”一个编程语言能不能流行起来,一方面取决于语法是否简单方便容易学习,一方面取决于生态是否完备所谓的......
  • 20240901_113224 python 环境依赖的备份与导入
    20240830_173845python当前环境依赖包导出到文件中_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/1187710920240830_183845python从依赖包记录文件中批量安装包_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/11877185......
  • Python 潮流周刊#67:uv 的重磅更新(摘要)
    本周刊由Python猫出品,精心筛选国内外的250+信息源,为你挑选最值得分享的文章、教程、开源项目、软件工具、播客和视频、热门话题等内容。愿景:帮助所有读者精进Python技术,并增长职业和副业的收入。分享了12篇文章,12个开源项目,全文2000字。以下是本期摘要:......