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

【Leetcode】(自食用)LRU算法(哈希链表法)

step by step.

题目:

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

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

思路:

主要是置换算法

·去重 => 想到哈希HashSet

·更新最新使用的 => 想到顺序结构 => LinkedHashSet

代码:

class LRUCache {LinkedHashMap<Integer,Integer> hs;int cap;public LRUCache(int capacity) {hs = new LinkedHashMap<Integer,Integer>();this.cap = capacity;}public int get(int key) {if(this.hs.containsKey(key)) {mKRecent(key,hs.get(key));return hs.get(key);}else return -1;}public void put(int key, int value) {if(hs.containsKey(key)){hs.put(key,value);mKRecent(key,value);return;}if(hs.size()==this.cap){//overhs.remove(hs.keySet().iterator().next());}hs.put(key,value); //插入队尾,更新最新}public void mKRecent(int key,int value){//重置,主要目的:插入队尾hs.remove(key);hs.put(key,value);}
}/*** 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);*/

相关文章:

【Leetcode】(自食用)LRU算法(哈希链表法)

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

robots.txt 如何禁止蜘蛛(百度,360,搜狗,谷歌)搜索引擎获取页面内容

什么是蜘蛛抓取 搜索引擎使用spider程序自动访问互联网上的网页并获取网页信息。spider在访问一个网站时&#xff0c;会首先会检查该网站的根域下是否有一个叫做robots.txt的纯文本文件。您可以在您的网站中创建一个纯文本文件robots.txt&#xff0c;在文件中声明该网站中不想…...

JVM 学习—— 类加载机制

前言 在上一篇文章中&#xff0c;荔枝梳理了有关Java中JVM体系架构的相关知识&#xff0c;其中涉及到的有关Java类加载机制的相关知识并没有过多描述。那么在这篇文章中&#xff0c;荔枝会详细梳理一下有关JVM的类加载机制和双亲委派模型的知识&#xff0c;希望能够帮助到有需要…...

C#实现int类型和字节流的相互在转化

通过TCP协议进行数据传输时&#xff0c;需要将所有传输的内容转为字节流&#xff0c;这里就用到了将int型的数据转为字节流的。代码如下&#xff1a; public static byte[] BytesConvertToInt(int vel) {byte[] hex new byte[4];hex[3] (byte)(vel >> 24) & 0xff)…...

Centos设置固定IP地址,外网访问

查看网络信息 一般会看到enp0s3的网络配置 ip address切换至网络配置路径 cd /etc/sysconfig/network-scripts/编辑配置 vi ifcfg-enp0s3 编辑配置 主要修改 静态ip:BOOTPROTOdhcp --> OOTPROTOstaticDNS(訪問外網):DNS1114.114.114.114本机ip: 192.168.70.121子网掩码…...

非线性弹簧摆的仿真(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

css实现文字颜色渐变+阴影

效果 代码 <div class"top"><div class"top-text" text"总经理驾驶舱">总经理驾驶舱</div> </div><style lang"scss" scoped>.top{width: 100%;text-align: center;height: 80px;line-height: 80px;fo…...

C++学习笔记总结练习:关联容器

关联容器 0 关联容器概述 关联容器与顺序容器的区别 关联容器和顺序容器有着根本不同。关联容器中的元素是按关键字来把偶才能和访问的。书序容器中的元素是按他们在容器中的位置来顺序保存和访问的。 两个基础类型 map:键值对key-value。关键字是索引&#xff0c;值表示与…...

TypeScript技能总结(二)

typescript是js的超集&#xff0c;目前很多前端框架都开始使用它来作为项目的维护管理的工具&#xff0c;还在不断地更新&#xff0c;添加新功能中&#xff0c;我们学习它&#xff0c;才能更好的在的项目中运用它&#xff0c;发挥它的最大功效 //readonly 只能修饰属性&#x…...

整理一些Postgresql工作中常用面试中会问的问题---Postgresql面试题001

1.什么是Postgresql TOAST? TOAST (The Oversized-Attribute Storage Technique,超大尺寸字段存储技术)主要用于存储大字段的值。 PostgreSQL 页面(page)大小是固定的(通常为8KB),且不允许tuples跨多个页面存储。因此不能存储非常大的字段值。为了克服这个限制,大字段…...

Xposed回发android.os.NetworkOnMainThreadException修复

最近用xposed进行hook回发的时候&#xff0c;又出现了新的问题&#xff1b; android.os.NetworkOnMainThreadException&#xff1b; 在Android4.0以后&#xff0c;写在主线程&#xff08;就是Activity&#xff09;中的HTTP请求&#xff0c;运行时都会报错&#xff0c;这是因为…...

【Leetcode】二叉树的最近公共祖先,二叉搜索树转换成排好序的双向链表,前序遍历与中序遍历构造二叉树

一.二叉树的最近公共祖先 链接 二叉树的最近公共祖先 题目再现 『Ⅰ』思路一&#xff1a;转换成相交链表问题 观察上图&#xff0c;节点1和节点4的最近公共祖先是3&#xff0c;这是不是很像相交链表的问题&#xff0c;关于相交链表&#xff0c;曾经我在另一篇文章里写到过&a…...

途乐证券|互联金融概念爆发,安硕信息“20cm”涨停,高伟达等大涨

互联金融概念4日盘中强势拉升&#xff0c;截至发稿&#xff0c;安硕信息“20cm”涨停&#xff0c;高伟达、卓创资讯、慧博云通涨超12%&#xff0c;恒银科技、极点软件亦涨停&#xff0c;指南针涨超9%&#xff0c;金证股份涨逾7%。 高伟达昨日在投资者互动平台表明&#xff0c;公…...

计数排序算法

计数排序 计数排序说明&#xff1a; 计数排序&#xff08;Counting Sort&#xff09;是一种非比较性的排序算法&#xff0c;它通过统计元素出现的次数&#xff0c;然后根据元素出现的次数将元素排列在正确的位置上&#xff0c;从而实现排序。计数排序适用于非负整数或者具有确…...

企业高性能web服务器-nginx

1.nginx简介&#xff1a; nginx是企业高可用的web服务器&#xff0c;nginx也可用来做反向代理服务器器&#xff0c;具有高并发&#xff0c;占用资源少&#xff0c;功能丰富&#xff0c;也可以作为简单的负载均衡。 nginx在企业中的功能&#xff1a; web服务软件 反向代理服务器…...

GaussDB数据库的元数据及其管理简介

目录 一、前言 二、元数据简介 1、元数据定义 2、元数据分类 3、数据库元数据管理 三、GaussDB数据库的元数据管理 1、GaussDB数据库的元数据管理 2、通过“SQL 系统表/系统视图/系统函数”的方式管理&#xff08;采集&#xff09;元数据 1&#xff09;获取表、视图及…...

合并两个有序链表 LeetCode热题100

题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路 遍历两个链表比较大小&#xff0c;按从小到大添加到链表即可。 代码 /*** Definition for singly-linked list.* struct ListNode {* int val;* List…...

【C++】模拟实现string

目录 &#x1f31e;专栏导读 &#x1f31b;定义string类 &#x1f31b;构造函数 &#x1f31b;拷贝构造函数 &#x1f31b;赋值函数 &#x1f31b;析构函数 &#x1f31b;[]操作符重载 &#x1f31b;c_str、size、capacity函数 &#x1f31b;比较运算符重载 &#…...

AI智慧安监视频监控汇聚平台EasyCVR调用接口出现跨域现象该如何解决?

视频监控汇聚EasyCVR可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等&#xff0c;以及厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等&#xff0c;能对外分发RTSP、RTMP、FLV、HLS、WebRTC等格式的视…...

无人机机巢有哪些,无人机机场/机场的主要分类

随着无人机技术的飞速发展&#xff0c;无人机已经渗透到了物流、农业、救援、公共安全等多个领域。而为了使这些无人机能更加高效、灵活地运行&#xff0c;一个新的概念应运而生&#xff0c;那就是无人机机巢&#xff08;UAV Nest&#xff09;。复亚智能无人机机巢是一种供无人…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...