当前位置: 首页 > 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;。复亚智能无人机机巢是一种供无人…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL

ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...