【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. 题目: 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中,则返回关键…...
robots.txt 如何禁止蜘蛛(百度,360,搜狗,谷歌)搜索引擎获取页面内容
什么是蜘蛛抓取 搜索引擎使用spider程序自动访问互联网上的网页并获取网页信息。spider在访问一个网站时,会首先会检查该网站的根域下是否有一个叫做robots.txt的纯文本文件。您可以在您的网站中创建一个纯文本文件robots.txt,在文件中声明该网站中不想…...
JVM 学习—— 类加载机制
前言 在上一篇文章中,荔枝梳理了有关Java中JVM体系架构的相关知识,其中涉及到的有关Java类加载机制的相关知识并没有过多描述。那么在这篇文章中,荔枝会详细梳理一下有关JVM的类加载机制和双亲委派模型的知识,希望能够帮助到有需要…...
C#实现int类型和字节流的相互在转化
通过TCP协议进行数据传输时,需要将所有传输的内容转为字节流,这里就用到了将int型的数据转为字节流的。代码如下: 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代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&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。关键字是索引,值表示与…...
TypeScript技能总结(二)
typescript是js的超集,目前很多前端框架都开始使用它来作为项目的维护管理的工具,还在不断地更新,添加新功能中,我们学习它,才能更好的在的项目中运用它,发挥它的最大功效 //readonly 只能修饰属性&#x…...
整理一些Postgresql工作中常用面试中会问的问题---Postgresql面试题001
1.什么是Postgresql TOAST? TOAST (The Oversized-Attribute Storage Technique,超大尺寸字段存储技术)主要用于存储大字段的值。 PostgreSQL 页面(page)大小是固定的(通常为8KB),且不允许tuples跨多个页面存储。因此不能存储非常大的字段值。为了克服这个限制,大字段…...
Xposed回发android.os.NetworkOnMainThreadException修复
最近用xposed进行hook回发的时候,又出现了新的问题; android.os.NetworkOnMainThreadException; 在Android4.0以后,写在主线程(就是Activity)中的HTTP请求,运行时都会报错,这是因为…...
【Leetcode】二叉树的最近公共祖先,二叉搜索树转换成排好序的双向链表,前序遍历与中序遍历构造二叉树
一.二叉树的最近公共祖先 链接 二叉树的最近公共祖先 题目再现 『Ⅰ』思路一:转换成相交链表问题 观察上图,节点1和节点4的最近公共祖先是3,这是不是很像相交链表的问题,关于相交链表,曾经我在另一篇文章里写到过&a…...
途乐证券|互联金融概念爆发,安硕信息“20cm”涨停,高伟达等大涨
互联金融概念4日盘中强势拉升,截至发稿,安硕信息“20cm”涨停,高伟达、卓创资讯、慧博云通涨超12%,恒银科技、极点软件亦涨停,指南针涨超9%,金证股份涨逾7%。 高伟达昨日在投资者互动平台表明,公…...
计数排序算法
计数排序 计数排序说明: 计数排序(Counting Sort)是一种非比较性的排序算法,它通过统计元素出现的次数,然后根据元素出现的次数将元素排列在正确的位置上,从而实现排序。计数排序适用于非负整数或者具有确…...
企业高性能web服务器-nginx
1.nginx简介: nginx是企业高可用的web服务器,nginx也可用来做反向代理服务器器,具有高并发,占用资源少,功能丰富,也可以作为简单的负载均衡。 nginx在企业中的功能: web服务软件 反向代理服务器…...
GaussDB数据库的元数据及其管理简介
目录 一、前言 二、元数据简介 1、元数据定义 2、元数据分类 3、数据库元数据管理 三、GaussDB数据库的元数据管理 1、GaussDB数据库的元数据管理 2、通过“SQL 系统表/系统视图/系统函数”的方式管理(采集)元数据 1)获取表、视图及…...
合并两个有序链表 LeetCode热题100
题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路 遍历两个链表比较大小,按从小到大添加到链表即可。 代码 /*** Definition for singly-linked list.* struct ListNode {* int val;* List…...
【C++】模拟实现string
目录 🌞专栏导读 🌛定义string类 🌛构造函数 🌛拷贝构造函数 🌛赋值函数 🌛析构函数 🌛[]操作符重载 🌛c_str、size、capacity函数 🌛比较运算符重载 &#…...
AI智慧安监视频监控汇聚平台EasyCVR调用接口出现跨域现象该如何解决?
视频监控汇聚EasyCVR可拓展性强、视频能力灵活、部署轻快,可支持的主流标准协议有GB28181、RTSP/Onvif、RTMP等,以及厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等,能对外分发RTSP、RTMP、FLV、HLS、WebRTC等格式的视…...
无人机机巢有哪些,无人机机场/机场的主要分类
随着无人机技术的飞速发展,无人机已经渗透到了物流、农业、救援、公共安全等多个领域。而为了使这些无人机能更加高效、灵活地运行,一个新的概念应运而生,那就是无人机机巢(UAV Nest)。复亚智能无人机机巢是一种供无人…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
