当前位置: 首页 > news >正文

【力扣100】146.LRU缓存

添加链接描述

class DLinkedNode:def __init__(self, key=0, value=0):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity: int):self.cache = dict()# 使用伪头部和伪尾部节点    self.head = DLinkedNode()self.tail = DLinkedNode()self.head.next = self.tailself.tail.prev = self.headself.capacity = capacityself.size = 0def get(self, key: int) -> int:if key not in self.cache:return -1# 如果 key 存在,先通过哈希表定位,再移到头部node = self.cache[key]self.moveToHead(node)return node.valuedef put(self, key: int, value: int) -> None:if key not in self.cache:# 如果 key 不存在,创建一个新的节点node = DLinkedNode(key, value)# 添加进哈希表self.cache[key] = node# 添加至双向链表的头部self.addToHead(node)self.size += 1if self.size > self.capacity:# 如果超出容量,删除双向链表的尾部节点removed = self.removeTail()# 删除哈希表中对应的项self.cache.pop(removed.key)self.size -= 1else:# 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部node = self.cache[key]node.value = valueself.moveToHead(node)def addToHead(self, node):node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef removeNode(self, node):node.prev.next = node.nextnode.next.prev = node.prevdef moveToHead(self, node):self.removeNode(node)self.addToHead(node)def removeTail(self):node = self.tail.prevself.removeNode(node)return node

思路:

  1. 这道题的题目理解:
  • 1)当使用get命令时,如果无,则返回-1;如果有则先在哈希表中查找这个值,返回值的同时,这个节点移到最前面(因为被访问过了,就排在前面)
  • 2)当使用put命令时,先在哈希表里查找这个值,如果有,则把这个节点的值做更改,然后把这个节点放到前面;如果没有,则先在哈希表中添加这个节点,然后把这个节点放进链表中;同时这里要注意,控制链表的长度,如果大于指定长度,则把尾结点指向的值弹出,同时还要把弹出的节点从哈希表里删掉 self.cache.pop(removed.key)
  1. 然后需要添加的四个函数:
  • 添加指定值节点
  • 删除指定值节点
  • 指定值节点移到头部:先删除指定值,再添加指定值
  • 超出长度后,删除尾结点节点这个函数需要返回值,因为要在哈希表中删除对应的键值对,这里也对应了为什么我在构建节点时需要把key和value都保存在节点里,因为哈希表删除需要给出**键**

相关文章:

【力扣100】146.LRU缓存

添加链接描述 class DLinkedNode:def __init__(self, key0, value0):self.key keyself.value valueself.prev Noneself.next Noneclass LRUCache:def __init__(self, capacity: int):self.cache dict()# 使用伪头部和伪尾部节点 self.head DLinkedNode()self.tail D…...

【Vue中给输入框加入js验证_blur失去焦点进行校验】

【Vue中给输入框加入js验证_blur失去焦点进行校验】 通俗一点就是给输入框加个光标离开当前文本输入框时&#xff0c;然后对当前文本框内容进行校验判断 具体如下&#xff1a; 1.先给文本框加属性 blur“validatePhoneNumber” <el-input v-model“entity.telephone” blur…...

vue3项目引入电子签名(可横屏竖屏)

实现效果&#xff1a;&#xff08;左边横屏&#xff0c;右边竖屏&#xff09; 前言&#xff1a;【使用开源项目smooth-signature 实现签名的功能。Gitee 地址是 &#xff1a;GitHub - linjc/smooth-signature: H5带笔锋手写签名&#xff0c;支持PC端和移动端&#xff0c;任何前…...

mysql中count(*)、count(1)、count(主键)、count(字段)的区别

文章目录 count函数的语义count(主键)count(1)count(*)count(字段)替代方案explain或者show table status中间表或者其他数据库计数 以下分析都是基于 select count(?) from table 这个语句来分析&#xff0c;不带过滤条件。 count函数的语义 count() 是一个聚合函数&#x…...

Nginx生成自签名证书从而添加域名的HTTPS访问

数字证书 ## 原理参考 https://mysticaldream.github.io/2023/05/certificate/## https://blog.csdn.net/m0_52440465/article/details/130713591 简介 数字证书是由证书颁发机构(CA)签名并颁发的电子文件,用于建立网络连接的身份认证和加密通信。SSL 证书是数字证书的一种。…...

无框架Java转go语言写http与tcp请求

项目地址 https://github.com/cmdch2017/http_tcpServer 项目结构 如何快速上手 http篇 1、controller包就相当于RestController&#xff0c;这里返回了一个Person对象&#xff0c;当你需要新建一个接口时&#xff0c;再新写一个func仿照下面的方法就行了 package control…...

【Git】Git基本操作

文章目录 Git 是什么Git 的优点Git 安装Linux UbuntuLinux CentOsWindows Git 基本操作1. 创建 Git 本地仓库2. 配置 Git3. Git工作区、暂存区和版本库4. 添加文件5. 查看 .git 文件6. 修改文件7. 版本回退 Git 是什么 Git是一个免费的、开源的分布式版本控制系统&#xff0c;…...

JavaSE学习笔记 Day20

JavaSE学习笔记 Day20 个人整理非商业用途&#xff0c;欢迎探讨与指正&#xff01;&#xff01; 上一篇 文章目录 JavaSE学习笔记 Day20十七、数据结构与算法17.1算法17.1.1冒泡排序17.1.2选择排序17.1.3插入排序17.1.4三个排序的区别 17.2顺序表17.2.1顺序表代码实现17.2.2顺…...

【蓝桥杯选拔赛真题52】python空调模式 第十四届青少年组蓝桥杯python 选拔赛比赛真题解析

目录 python空调模式 一、题目要求 1、编程实现 2、输入输出...

Android Studio: 解决Gradle sync failed 错误

文章目录 1. 前言2. 错误情况3. 解决办法3.1 获取gradle下载地址3.2 获取gradle存放目录3.3 替换并删除临时文件3.4 触发Try Again 4. 执行成功 1. 前言 今天调试项目&#xff0c;发现新装的AS&#xff0c;在下载gradle的过程中&#xff0c;一直显示连接失败&#xff0c;Gradl…...

【手写数据库】从零开始手写数据库内核,行列混合存储模型,学习大纲成型了

目录 ​专栏内容: 参天引擎内核架构 本专栏一起来聊聊参天引擎内核架构,以及如何实现多机的数据库节点的多读多写,与传统主备,MPP的区别,技术难点的分析,数据元数据同步,多主节点的情况下对故障容灾的支持。 手写数据库toadb 本专栏主要介绍如何从零开发,开发的步骤,以…...

机器学习中的一些经典理论定理

PAC学习理论 当使用机器学习方法来解决某个特定问题时&#xff0c;通常靠经验或者多次试验来选择合适的模型、训练样本数量以及学习算法收敛的速度等。但是经验判断或多次试验往往成本比较高&#xff0c;也不太可靠&#xff0c;因此希望有一套理论能够分析问题难度、计算模型能…...

c语言:成本100元,40%的利润怎么计算|练习题

一、利润的计算公式&#xff1a; 利润售价-成本 售价成本/(1-利润率) 二、用c语言代码表示为&#xff1a; 如图&#xff1a; 三、计算源代码【带注释】 #include <stdio.h> int main() { float cost;//成本变量 int prof_rate;//利润率变量 float price;//…...

【Python必做100题】之第二十二题(复制列表)

题目&#xff1a;将一个列表的数据复制到另一个列表中 重点&#xff1a;确保复制到位要导入copy方法进行深度复制 代码如下&#xff1a; #将一个列表的数据复制到另一个列表中 import copy list [1,2,3,4] print(list) list1 copy.copy(list) list[0] 30 print(list) pri…...

Java 数据结构篇-实现堆的核心方法与堆的应用(实现 TOP-K 问题:最小 k 个数)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 堆的说明 2.0 堆的成员变量及其构造方法 3.0 实现堆的核心方法 3.1 实现堆的核心方法 - 获取堆顶元素 peek() 3.2 实现堆的核心方法 - 下潜 down(int i) 3.3 实…...

startUML6.0.1破解方法

startUML6.0.1破解方法 文章目录 startUML6.0.1破解方法1.startUML6.0.1快速破解2.概述3.安装Nodejs4.安装asar5.修改app.asar中的源码6.将修改后的源码重新压缩7.覆盖官方的asar文件8.重启startUML9.参考文档 1.startUML6.0.1快速破解 后绪步骤可以不看&#xff0c;直接下载我…...

Python实现多种图像分割方法:基于阈值分割和基于区域分割

Python实现多种图像分割方法&#xff1a;基于阈值分割和基于区域分割 图像分割是图像分析的第一步&#xff0c;是计算机视觉的基础&#xff0c;但也是图像处理中最困难的问题之一。经典的计算机视觉任务&#xff0c;如目标检测、图像识别等都和图像分割相关&#xff0c;图像分…...

SQL学习笔记+MySQL+SQLyog工具教程

文章目录 1、前言2、SQL基本语言及其操作2.1、CREATE TABLE – 创建表2.2、DROP TABLE – 删除表2.3、INSERT – 插入数据2.4、SELECT – 查询数据2.5、SELECTDISTINCT – 去除重复值后查询数据2.6、SELECTWHERE – 条件过滤2.7、AND & OR – 运算符2.8、ORDER BY – 排序2…...

SpringBoot的日志管理

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开心好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

leetcode---76. 最小覆盖子串 [C++/滑动窗口+哈希表]

原题&#xff1a;76. 最小覆盖子串 - 力扣&#xff08;LeetCode&#xff09; 题目解析&#xff1a; 此题在这道题的基础上进行理解会更简单 leetcode --- 30. 串联所有单词的子串[C 滑动窗口/双指针]-CSDN博客 本题要求在s字符串中找到含有t字符串所有字符的最短子串。 也就是…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...