【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 主要特点 轻量级ÿ…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
