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

每日一题:LeetCode 146 LRU缓存

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。进阶:你是否可以在 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提示:1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
最多调用 3 * 104 次 get 和 put来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lru-cache

LRUCache需要满足:如果在添加元素的时候容量不够,那么将最久没有访问的节点删除掉。

那么其实内部需要维护的逻辑就是,在插入或者查询元素的时候,需要将频繁操作的元素的生命周期延长,那么就可以将经常操作元素放置在头部(或者尾部,自己统一逻辑就好),那么尾部的元素自然就是最久没有访问的了。当每次容量不够的时候,就将尾部的元素移除掉即可。

那么就涉及到两个要素:

1 元素需要按照操作顺序排序

2 查找元素要足够快,删除元素也要快。

Map速度查询快,链表删除和插入快,结合这两点就可以形成如下结构:

HashMap中再维护一个双向链表,黑色的节点是存储在HashMap中的,红色的线表示的是双向链表的方向。其实也就是在原有的HashMap的基础上,增加了元素之间的关系,可以按照特定顺序去访问。其实这就是LinkedHashMap的内部结构。

那么为什么不用单链表呢?因为在删除的时候是需要获取到上一个节点的,如果是单链表的话就需要将链表从头到尾再访问一遍。

 

本题具体实现如下:

在双向链表的实现中,使用一个伪头部(dummy head)和伪尾部(dummy tail)标记界限,这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

class LRUCache {private LRUCache.Node dummyHead;private LRUCache.Node dummyTail;private Map<Integer, Node> map;int capacity = 0;class Node {Node pre;Node next;Integer key;Integer value;public Node(Integer key, Integer value) {this.key = key;this.value = value;}}public LRUCache(int capacity) {this.capacity = capacity;map = new HashMap<>(capacity);dummyHead = new Node(-1, -1);dummyTail = new Node(-1, -1);dummyHead.next = dummyTail;dummyTail.pre = dummyHead;}public int get(int key) {if (map.containsKey(key)) {Node node = map.get(key);moveToHead(node);return node.value;} else {return -1;}}private void moveToHead(Node node) {//  pre -> node -> nextnode.pre.next = node.next;node.next.pre = node.pre;addToHead(node);}private void addToHead(Node node) {//dummyHead -> node -> oldHeadNode oldeHead = dummyHead.next;oldeHead.pre = node;node.next = oldeHead;node.pre = dummyHead;dummyHead.next = node;}public void put(int key, int value) {if (map.containsKey(key)) {Node node = map.get(key);node.value = value;moveToHead(node);return;}if (map.size() >= capacity) {Node tailNode = removeTailNode();map.remove(tailNode.key);}Node node = new Node(key, value);map.put(key, node);addToHead(node);}private Node removeTailNode() {//pre -> node -> dummyTailNode oldNode = dummyTail.pre;Node newNode = oldNode.pre;newNode.next = dummyTail;dummyTail.pre = newNode;oldNode.pre = null;oldNode.next = null;return oldNode;}}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.exyb.cn/news/show-2929.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

[HDU2520]我是菜鸟,我怕谁(每日一题5.30)

题目链接&#xff1a;Problem - 2520 (hdu.edu.cn) 乍一看这个题&#xff0c;发现不就是匀加速直线运动么&#xff0c;于是写出了如下的代码&#xff1a; #include <iostream>using namespace std;int d(int t);int main() {int T;cin >> T;while(T--){int t;cin …...

第二讲:基本飞行姿态

四旋翼在其四个轴臂上四个桨的高速转动作用下&#xff0c;会受到四个桨的拉力&#xff0c;拉力方向与机身垂直&#xff0c;当四个桨产生的拉力总和大于机身重力时&#xff0c;飞机处于上升状态&#xff1b;当总拉力小于机身重力时&#xff0c;飞机处于下降状态&#xff1b;当总…...

MySQL索引用法实例分析

建议看原文&#xff1a;https://www.jb51.net/article/88846.htm 这篇文章主要介绍了MySQL索引用法,结合实例形式较为详细的分析了mysql索引的功能、定义、使用方法与相关注意事项,需要的朋友可以参考下 本文实例分析了MySQL索引用法。分享给大家供大家参考&#xff0c;具体如下…...

必看!LuatOS自定义C库全新教程,一文极速上手

今天继续讲LuatOS的开发&#xff0c;上一期简单说了一下如何移植LuatOS&#xff0c;相信很多朋友已经看过了。那么今天&#xff0c;我就开始讲C和Lua调用的部分教程。 LuatOS相关资料及Lua语言的官方定义&#xff0c;详见以下链接&#xff1a; LuatOS仓库&#xff1a; https:/…...

Xshell 连接不上Linux Centos 7的解决方法之设置静态IP

前序 最近在开发项目&#xff0c;需要在服务器部署数据库、ftp文件管理等相关内容时&#xff0c;为了方便操作&#xff0c;使用Xshell会话管理工具进行服务器操作。出现连不上服务器网络的问题&#xff0c;就所遇问题进行学习解决方案及总结记录。 配置虚拟机网络 1.在虚拟机…...

ann2snn的代码分析

首先&#xff0c;主函数是if_cnn_mnist_work.py 1.输出snn测试结果的就是这么一些代码&#xff1a; utils.pytorch_ann2snn(model_namemodel_name,norm_tensornorm_tensor,test_data_loadertest_data_loader,devicedevice,TT,log_dirlog_dir,configconfig)2.ctrl鼠标左键点击py…...

基于域名访问网站1(作业)

搭建一个基于http://www.zuoye.com:22222访问的web网站&#xff0c;网站首页在/www/http/&#xff0c;内容为zuoye 结果 过程&#xff1a; 创建网页的根目录&#xff0c;并编辑网页内容为zuoye 编辑/etc/httpd/conf.d/zuoye.conf 关闭防火墙 关闭selinux 重启httpd 编辑/…...

虚拟内存和地址空间

目录 一、物理内存vs虚拟内存 二、物理内存空间和虚拟内存空间 三、32bit的地址空间 四、cpu位宽和cpu地址总线宽 五、虚拟内存地址空间划分 六、虚拟地址和物理地址的映射 早期的计算机程序都是直接跑在物理内存上的&#xff0c;这就要求程序大小不能超过物理内存的上限…...

STM32CubMx自学笔记(一)-LED灯翻转

STM32CubMX自学笔记&#xff08;一&#xff09;---LED灯翻转工程创建系统具体配置工程代码编写下载验证结语工程创建 首先得安装STM32CubMx软件。具体安装步骤参照 保姆级安装步骤&#xff0c;这里将不再赘述&#xff0c;第一节主要是介绍新工程的创建&#xff0c;首先在桌面打…...

十四、Python第十四课——文件和异常

&#xff08;请先看这篇文章&#xff1a;https://blog.csdn.net/GenuineMonster/article/details/104495419&#xff09; 如果看完这篇博文&#xff0c;你的问题还是没有解决&#xff0c;那么请关注我的公众号&#xff0c;后台发消息给我吧&#xff0c;当天回复&#x…...

Linux下安装sqlite3

文章目录前言安装步骤测试安装成功前言 sqlite3的安装 安装步骤 依次执行以下命令&#xff1a; 1)wget http://www.sqlite.org/sqlite-3.5.6.tar.gz 2)tar -xzvf sqlite-3.5.6.tar.gz 3)cd sqlite-3.5.6 4)./configure 5)make 6)make install测试安装成功 出现红色方框信息…...

拉伯配资6月1日策略

5月回想&#xff1a;在5月份的战略中&#xff0c;我们认为其时胶着的商场可能在5月会有所改动。从实践表现来看&#xff0c;5月下旬商场明显出现了一些活泼做多的信号&#xff0c;商场也选择了向上打破。上证指数上涨超4%&#xff0c;深圳成指上涨近3%。 行情判别&#xff1a;从…...

微信小程序趋势及前景,大厂直通车!

最近看到群里看到一个女生&#xff0c;讲述了她从开始选择Android&#xff0c;经过非常努力的学习和挣扎&#xff0c;然而最后面对当前的环境却不得不放弃。看完以后真的非常替她感觉惋惜&#xff0c;如果早几年入行可能结果会比现在好很多&#xff0c;但可惜&#xff0c;这就是…...

设计模式导读助记

各个设计模式的详细介绍都已经完成&#xff0c;但是不经常用总会忘&#xff0c;所以我想用 一句话 总结设计模式&#xff0c;思考模式的真正意图&#xff0c;再用 一点提示 来思考代码如何实现 写在前面 我整理的设计模式这一个系列&#xff0c;主要是结合了以下几本书 : 《设…...

RT-Thrad|STM32F103+ESP8266 S01+RT-Thread联网之环境搭建(1/3)

文章目录前言硬件准备百问网STM32F103ESP8266 01SESP8266 介绍ESP8266 01S技术规格参数软件准备下载安装 Keil μVision5Pack Installer安装 ST-Link 驱动获取RT-Thread源码下载安装 RT-Thread env 工具文章列表 RT-Thrad|STM32F103ESP8266 S01RT-Thread联网之环境搭建(1/3)RT…...

天眼查怎么删除信息_天眼查删除信息的方法介绍

天眼查信息怎么删除 天眼查风险信息怎么清除 天眼查问答信息怎么删除 天眼查法律诉讼信息可以删吗 天涯查上的信息删除怎么操作&#xff0c;天眼查成立于2014年&#xff0c;至今发展迅速&#xff0c;已经帮助了无数的企业和消费者&#xff0c;那么很多企业的天眼查信息有时候需…...

Xxl-Job调度器原理解析

项目解析源码地址&#xff1a;https://gitee.com/lidishan/xxl-job-code-analysisxxl-job版本&#xff1a;2.3.0Xxl-Job分为执行器、调度器。而我们平时的客户端就属于一个执行器&#xff0c;执行器启动的时候会自动注册到调度器上&#xff0c;然后调度器进行远程调度。调度器初…...

51单片机利用锁存器控制数码管显示年月日时分秒

数码管模块中的两片74hc573&#xff0c;一片锁存段码&#xff0c;一片锁存位码&#xff0c;这样才能驱动8位数码管。74hc573是锁存器&#xff0c;用于数码管显示时通常是采用段选、片选共用同一组并口的驱动方式。 驱动数码管需要两个信号&#xff0c;一个是段选信号&#xff…...

webrtc之SVC实现(十)

一、概念 SVC&#xff08;可适性视频编码或可分级视频编码&#xff09;是传统H.264/MPEG-4 AVC编码的延伸&#xff0c;可提升更大的编码弹性&#xff0c;并具有时间可适性&#xff08;Temporal Scalability&#xff09;、空间可适性&#xff08;Spatial Scalability&#xff09…...

LeetCode 数值的整数次方

实现 pow(x, n) &#xff0c;即计算 x 的 n 次幂函数&#xff08;即&#xff0c;xn&#xff09;。不得使用库函数&#xff0c;同时不需要考虑大数问题。 示例 1&#xff1a; 输入&#xff1a;x 2.00000, n 10 输出&#xff1a;1024.00000 示例 2&#xff1a; 输入&#xf…...

链表 + 数组模拟链表

链表的指针实现 1.指针 #include<iostream> using namespace std; int main(){int a 5;int *p; // int 型的指针double *q; //double 型的指针p &a;// cout << p 指向 acout << *p << endl; //间接输出 areturn 0; }2.申请动态内存&#xff08…...

boost::geometry::detail::overlay::approximately_equals用法的测试程序)

boost::geometry::detail::overlay::approximately_equals用法的测试程序 实现功能C++实现代码实现功能 boost::geometry::detail::overlay::approximately_equals用法的测试程序) C++实现代码 #include <geometry_test_common.hpp> #include <boost/geometry/algo…...

boost::geometry::model::multi_polygon用法的测试程序

boost::geometry::model::multi_polygon用法的测试程序 实现功能C++实现代码实现功能 boost::geometry::model::multi_polygon用法的测试程序 C++实现代码 #include <algorithms/area/test_area.hpp> #include <boost/geometry/geometries/geometries.hpp> #inc…...

boost::geometry模块使用 Karney 的直接方法

boost::geometry模块使用 Karney 的直接方法 实现功能C++实现代码实现功能 boost::geometry模块使用 Karney 的直接方法 C++实现代码 #include <boost/geometry.hpp> #include <boost/geometry/formulas/karney_direct.hpp> using namespace boost::geometry; i…...

Ways to Encrypt Password on Server

Background: the history of store password in server, starts with plain text, to MD5, SHA-1, SHA-2, to add salt/pepper/multihashing, to bcrypt/Argon2id etc. Best way so far to encrypt password on server : use bcrypt(unless have specific reasons not to do...

【社区周会】2021-06-01 内容概要

工程进展 工程周报更新时间&#xff1a;9:00AM PT (16:00UTC, 悉尼11,北京8, 希腊3, 阿姆斯特丹2, 奥尼查1, 纽约-4, 西雅图-7)&#xff0c;Zoom直播地址可在YouTube&#xff1a;Casper频道 查阅本周及过往更新。 执行 1.3.x版本周期第三周冲刺已由收尾过渡到集成测试阶段。…...

【GIT】OpenSSL SSL_read: Connection was reset, errno 10054

问题描述 从远程仓库拉取项目时报错 fatal: unable to access https://github.com/Henry-chr/godone.git/: OpenSSL SSL_read: Connection was reset, errno 10054解决方案 造成这个错误很有可能是网络不稳定&#xff0c;连接超时导致的&#xff0c; 再次尝试后成功同步远程…...

2021-06-02

JavaScript 逆向辅助模拟的理解原文地址代码原文地址 查看地方 代码 async_playwright().start() #启动 ba.chromium.launch() #创建浏览器 cb.new_page() #创建新页面 page.route(“js1.js”,lambda route: route.fulfill(path"./js2.js) #2替换1&#xff0c;1是虚拟路…...

OA系统十四:注销功能;

注销&#xff1a;就是把登录时所保留的信息全部给清除掉&#xff1b;其本质就是清除保存在Session中的数据&#xff0c;让session回到初始的状态&#xff1b; 至于为什么只需要手动清除session对象中的数据&#xff0c;而request对象中的数据不用手动清除&#xff0c;这是因为r…...

php面试题

php面试常见算法题 二分法查找&#xff1a; /***二分法查找* param $array 是待查找的数组* param $low 最小的键* param $hight 最大的键* param $k 要查找的位置*/ function twofunction($array, $low, $height, $k) {if (is_array($array)) {$mid ($low $height) / 2;if…...

Hadoop(理论)

Hadoop 目录Hadoop一、大数据概论1、什么是大数据2、大数据特点4、大数据的起源5、大数据的数据来源6、大数据目前面临问题二、Hadoop引言1、解决问题2、Hadoop诞生3、Hadoop的发现版本4、Hadoop的特点6、Hadoop的生态圈三、HDFS1、简介2、优缺点3、HDFS的核心设计3.1数据块3.2…...

电信流失用户分析与对策

0 目的 本文目的是找到付费客户的流失原因&#xff0c;并给出相应的理论建议。 数据来源&#xff1a; https://www.kaggle.com/blastchar/telco-customer-churn​www.kaggle.com 1前期工作 1.1数据清洗-列名翻译 BEGIN; ALTER TABLE 电信流失用户 CHANGE customerID 顾客I…...

云计算技术学习书籍推荐

云计算是通过使计算分布在大量的分布式计算机上&#xff0c;而非本地计算机或远程服务器中&#xff0c;企业数据中心的运行将与互联网更相似。从应用方面理解&#xff0c; 云计算&#xff0c;是一种分布式计算&#xff0c;充分利用资源&#xff0c;实现资源的共享。但是现代云计…...

博弈论与多智能体强化学习

Ann Nowe, Peter Vrancx, and Yann-Michael De Hauwere Abstract. Reinforcement Learning was originally developed for Markov Decision Processes (MDPs). It allows a single agent to learn a policy that maximizes a pos- sibly delayed reward signal in a stochast...

数据安全与理论实践

现状趋势: 我们主要从安全现状以及趋势分析两个方面来。 讲解这一节的内容。 下面我们先讲安全现状&#xff0c;我们主要从三个方面来介绍数据安全的现状。首先是。 个人角度啊&#xff0c;随着电商物流行业的兴起&#xff0c;大家的隐私保护意识增强&#xff0c;越来越多的人愿…...

elementUI table某列数据是数组,需要多行显示

需求&#xff1a; 从后台请求到的数据&#xff0c;是数组&#xff0c;需要用table展示&#xff0c;数组里面有一个属性也是数组。想让属性的数组在table里分行显示。 代码&#xff1a; 只需要在 el-table-column 使用 插槽 遍历数组就行了&#xff08;可以用div&#xff0c;div…...

机器学习导论--1.机器学习理论基础详解

机器学习理论基础详解一.大数据时代究竟改变了什么二.大数据的4V特征三.大数据架构1.要明确的2.项目描述--以电信日志分析为例3.大数据架构--以电信日志分析为例4.大数据架构--医疗四.人工智能1.人工智能的发展和应用场景2.人工智能、机器学习、深度学习的关系3.数据、数据分析…...

css做钟表,使用css3做钟表

.wrap{width:200px;height:200px;border:2px solid #000;border-radius:50%;margin:100px auto;position:relative;}li{position:absolute;width:2px;height:5px;top:0;left:99px;background:#000;-webkit-transform-origin:center 100px;}/*li:nth-child(1){-webkit-transfor...

html5绘制圆形钟表,HTML5 Canvas实现圆形钟表代码演示

function init(){clock();setInterval(clock,1000);}function clock(){var now new Date();var ctx document.getElementById(canvas).getContext(2d);ctx.save();ctx.clearRect(0,0,150,150);ctx.translate(75,75);ctx.scale(0.4,0.4);ctx.rotate(-Math.PI/2);ctx.strokeSt...

贪心算法练习:数列极差问题

在黑板上写n个正整数排成的一个数列&#xff0c;进行如下操作&#xff1a; 每次擦掉其中的两个数a和b&#xff0c;然后在数列里面加入一个数a*b1&#xff0c; 如此循环往复直到黑板上只剩下一个数&#xff0c;在所有按这种操作方式 最后得到的数中&#xff0c;最大的记为max&am…...

java写一个圆形钟表_+JAVA写得钟表的源代码

import java.awt.Color;import java.awt.Font;import java.awt.Graphics;import java.text.SimpleDateFormat;import java.util.Date;import java.util.Locale;import javax.swing.JFrame;import javax.swing.JPanel;public class Clock extends JPanel implements Runnable {...

ES关键字

一、管理性命令 1、查看集群的节点 GET /_cat/nodes?v2、查看集群健康状况 GET /_cat/health3、查看集群中的库&#xff08;index&#xff09; GET /_cat/indices?v二、库&#xff08;index&#xff09;操作 1、查看某个具体库 GET /_cat/indices/xxx2、手动建库 PUT …...

return 关键字

C语言提供了return关键字&#xff0c;可以用于退出函数的运行&#xff0c;而且&#xff0c;可以在退出函数的时候&#xff0c;返回一个数据。 例如while循环语句中的break关键字一样&#xff0c;break语句可以跳出while循环语句&#xff0c;结束while循环语句的运行。那么&…...

instanceof关键字

instanceof关键字 在Java中可以使用instanceof关键字判断一个对象到底是不是一个类的实例。 示例代码: public class PolDemo01 {static class A{public void tell1(){System.out.println("A--tell1");}public void tell2(){System.out.println("A--tell2"…...

大一学生WEB前端静态网页——唯品会1页 包含hover效果

⛵ 源码获取 文末联系 ✈ Web前端开发技术 描述 网页设计题材&#xff0c;DIVCSS 布局制作,HTMLCSS网页设计期末课程大作业 | 在线商城购物 | 水果商城 | 商城系统建设 | 多平台移动商城 | H5微商城购物商城项目 | HTML期末大学生网页设计作业&#xff0c;Web大学生网页 HTML&a…...

java that关键字_JAVA中的关键字详解

Abstract 抽象的一个Java语言中的关键字&#xff0c;用在类的声明中来指明一个类是不能被实例化的&#xff0c;但是可以被其它类继承。一个抽象类可以使用抽象方法&#xff0c;抽象方法不需要实现&#xff0c;但是需要在子类中被实现break一个Java的关键字&#xff0c;用来改变…...

关键字

目录关键字常见关键字关键字 C语言中一共有32个关键字&#xff0c;每个都有特定的含义&#xff0c;是程序必不可少的部分&#xff0c;这些关键字是规定好了的&#xff0c;因此不能把关键字用来定义变量名。下面列出所有的关键字&#xff1a; auto,break&#xff0c;case&#…...

JAVA 关键字 查询表

JAVA 关键字 查询表 1.abstract - 2 - [ˈbˌstrkt] adj.抽象的&#xff0c;理论上的&#xff1b;难解的&#xff1b;抽象派的&#xff1b;茫然的 2.boolean - 3 - [ˈbuliən] adj.布尔数学体系的 3.break - 3 - [brek] vt.& vi.打破&#xff1b;折断…...

关键字的基本概念和使用

1.关键字 - typedef - 类型重定义 typedef 顾名思义是类型定义&#xff0c;这里应该理解为类型重命名。 使用方法&#xff1a; typedef unsigned int uint;/*把 unsigned int 重新命名为 uint&#xff0c;当我们一个文件需要频繁使用此类型时把他重新命名为一个简单的…...

关键字详解

文章目录1.typedef2.register3.static4.structC语言为使用者提供了许多的关键字&#xff0c;这些关键字不能被使用者们所修改&#xff0c;使用者也无法自己创建关键字&#xff0c;我们在定义变量时也不能使用关键字作为变量名&#xff1b;下面由我来向大家其中的3个关键字。 下…...