当前位置: 首页 > 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;从机器自动化控制、测试测量到设备状态监测…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...