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

OJ练习第160题——LRU 缓存

LRU 缓存

力扣链接:146. LRU 缓存

题目描述

请你设计并实现一个满足 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) 的平均时间复杂度运行。

示例

在这里插入图片描述

Java代码(LinkedHashMap)

class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity;}
}

Java代码(哈希表 + 双向链表)

class LRUCache {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key, int _value) {key = _key; value = _value;}}private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();private int size;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) {return -1;}// 如果 key 存在,先通过哈希表定位,再移到头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {// 如果 key 不存在,创建一个新的节点DLinkedNode newNode = new DLinkedNode(key, value);// 添加进哈希表cache.put(key, newNode);// 添加至双向链表的头部addToHead(newNode);++size;if (size > capacity) {// 如果超出容量,删除双向链表的尾部节点DLinkedNode tail = removeTail();// 删除哈希表中对应的项cache.remove(tail.key);--size;}}else {// 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部node.value = value;moveToHead(node);}}private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail() {DLinkedNode res = tail.prev;removeNode(res);return res;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

相关文章:

OJ练习第160题——LRU 缓存

LRU 缓存 力扣链接&#xff1a;146. LRU 缓存 题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓…...

使用 Hugging Face Transformer 创建 BERT 嵌入

介绍 最初是为了将文本从一种语言更改为另一种语言而创建的。BERT 极大地影响了我们学习和使用人类语言的方式。它改进了原始 Transformer 模型中理解文本的部分。创建 BERT 嵌入尤其擅长抓取具有复杂含义的句子。它通过检查整个句子并理解单词如何连接来做到这一点。Hugging F…...

unity 控制Dropdown的Arrow箭头变化

Dropdown打开下拉菜单会以“Template”为模板创建一个Dropdown List&#xff0c;在“Template”上添加一个脚本在Start()中执行下拉框打开时的操作&#xff0c;在OnDestroy()中执行下拉框收起时的操作即可。 效果代码如下用于控制Arrow旋转可以根据自己的想法进行修改&#xff…...

Java开发面试--nacos专区

1、 Nacos是什么&#xff1f; 请简要介绍Nacos是什么以及它的主要功能和用途。 答&#xff1a; 简介&#xff1a; Nacos是一个开源的、高性能、动态服务发现、配置和服务管理平台&#xff0c;通常用于微服务架构中。Nacos的名称来源于"Naming"&#xff08;服务发现…...

GB28181学习(三)——心跳保活

心跳保活 要求&#xff1a; 1. 当原设备发现工作异常时&#xff0c;应立即向本SIP监控域的SIP服务器发送状态信息&#xff1b; 2. 无异常时&#xff0c;定时向本SIP监控域的SIP服务器发送状态信息&#xff1b; 3. 状态信息报送采用**MESSGAE**方法&#xff1b; 4. SIP设备宜在…...

黑马JVM总结(三)

&#xff08;1&#xff09;栈内存溢出 方法的递归调用&#xff0c;没有设置正确的结束条件&#xff0c;栈会有用完的一天&#xff0c;导致栈内存溢出 可以修改栈的大小&#xff1a; 再次运行&#xff1a;减少了次数 案例二&#xff1a; 两个类的循环应用问题&#xff0c;导致Js…...

【数据结构】二叉树基础入门

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …...

MFC自定义消息的实现方法----(线程向主对话框发送消息)、MFC不能用UpdateData的解决方法

在MFC中&#xff0c;我们一边在使用多线程时&#xff0c;经常会遇到在需要调用到新建的控件&#xff0c;此时建议不要在新建的线程中直接调用主对话框的控件&#xff0c;我们可以通过自定义消息&#xff0c;在新建线程中发送并触发主线程进行相关的界面控件操作。 以Dialog对话…...

Linux单列模式实现线程池

目录 一、单列模式 1.1 单列模式概念以及实现条件 1.2 饿汉模式 1.1.1 饿汉模式代码实现 1.1.2 饿汉模式特征和优缺点 1.3 懒汉模式 1.3.1 懒汉模式代码实现 1.3.2 懒汉模式特征以及优缺点 二、线程池 2.1 线程池概念 2.2 实现简单线程池逻辑 2.3 模拟实现懒汉模式线程…...

汇川PLC学习Day3:轴控代码编写、用户程序结构说明与任务配置示例、用户变量空间与编址

汇川PLC学习Day3&#xff1a;轴控代码编写、用户程序结构说明与任务配置示例、用户变量空间与编址 一、新建轴与轴控代码编写 1. 新建轴 (1)新建一个轴 &#xff08;2&#xff09;将轴名字更新为实际名字 可以后面实例化后再更改&#xff0c;汇川可以在更新名字时同步更新…...

javaee springMVC Map ModelMap ModelAndView el和jstl的使用

pom依赖 <?xml version"1.0" encoding"UTF-8"?><project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 …...

vue监听表单输入的身份证号自动填充性别和生日

1&#xff0c;先给表单绑定一个v-model值 <el-input type"number" v-model"form.idCard" placeholder"请输入证件号码" /> 2&#xff0c;使用watch监听输入的值 watch(form, (newName, oldName) > {var numid newName.idCard.split(…...

蓝桥杯官网练习题(翻硬币)

题目描述 小明正在玩一个"翻硬币"的游戏。 桌上放着排成一排的若干硬币。我们用 * 表示正面&#xff0c;用 o 表示反面&#xff08;是小写字母&#xff0c;不是零&#xff09;。 比如&#xff0c;可能情形是&#xff1a;**oo***oooo; 如果同时翻转左边的两个硬币…...

企业架构LNMP学习笔记34

LVS-DR模式&#xff1a; 老师分析&#xff1a; 1、首先用户用CIP请求VIP 2、根据上图可以看到&#xff0c;不管是Director Server还是Real Server上都需要配置VIP&#xff0c;那么当用户请求到达我们的集群网络的前端路由器的时候&#xff0c;请求数据包的源地址为CIP目标地址…...

Python学习之六 循环结构

在很多情况下,我们往往需要循环输入多次,比如,密码最多只能输错3次等。这时候,我们需要使用循环结构。本小节,将学习循环。 一、while循环 while循环的一般形式如下: while 判断条件: 循环语句块 当判断条件为真,便执行循环语句块。比如说,我们需要写一个判断账号…...

flutter 网络地址URL转file

方法1 import dart:io; import package:http/http.dart as http; import package:path/path.dart; import package:path_provider/path_provider.dart;Future<File> _fileFromImageUrl() async {final response await http.get(Uri.parse(https://example.com/xyz.jpg)…...

【JavaEE基础学习打卡07】JDBC之应用分层设计浅尝!

目录 前言一、简单说说应用分层二、实体层1.O/R映射2.O/R映射实践三、数据访问层1.DAO层2.DAO层实战总结前言 📜 本系列教程适用于JavaWeb初学者、爱好者,小白白。我们的天赋并不高,可贵在努力,坚持不放弃。坚信量最终引发质变,厚积薄发。 🚀 文中白话居多,尽量以小白…...

Helm Kubernetes Offline Deploy Rancher v2.7.5 Demo (helm 离线部署 rancher 实践)

文章目录 1. 简介2. 预备条件3. 选择 SSL 配置4. 离线安装的 Helm Chart 选项5. 下载介质6. 生成证书7. 镜像入库8. 安装 rancher9. 配置 nodeport10. 配置 ingress11. 界面访问11.1 首页预览11.2 查看集群信息11.3 查看项目空间11.4 查看节点信息 1. 简介 Rancher 是一个开源…...

网络编程day6——基于C/S架构封装的线程池

一、线程竞争基本概念 竞争与同步 同一个进程中的线程共享进程中的绝大多数资源&#xff0c;当它们随意竞争时可能会导致资源被破坏、脏数据、不完整问题 通过一些手段让线程在竞争资源时相互协调、避免出现以上问题&#xff0c;这就称为线程同步 原子操作&#xff1a; 操作过程…...

ARM/X86工业级数据采集 (DAQ) 与控制产品解决方案

I/O设备&#xff0c;包括信号调理模块、嵌入式PCI/PCIE卡、便携式USB模块、DAQ嵌入式计算机、模块化DAQ系统&#xff0c;以及DAQNavi/SDK软件开发包和DAQNavi/MCM设备状态监测软件。 工业I/O产品适用于各种工业自动化应用&#xff0c;从机器自动化控制、测试测量到设备状态监测…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...