LRU缓存(Leetcode146)

例题:

分析:

       题目要求函数get和put要达到O(1)的时间复杂度,可以用 hashMap 来实现,因为要满足逐出最久未使用的元素的一个效果,还需要配合一个双向链表来共同实现。链表中的节点为一组key-value。

我们可以用双向链表来储存数据(key-value),当调用put方法添加数据时,可以将数据(key-value)添加到双向链表的队头,队头的元素表示最新使用的元素,越靠近队尾,就是最久未用的元素。

当调用get方法时,若存在此元素,则从双向链表中把该组数据(key-value)提到队头来。

代码实现:
package leetcode;

import java.util.HashMap;

public class LRUCacheLeetcode146 {

    static class LRUCache {

        static class Node{
            Node next;
            Node prev;
            int key;
            int value;
            public Node(){

            }

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        static class DoublyLinkedList{
            Node head;
            Node tail;

            public DoublyLinkedList() {
                head = tail = new Node();
                head.next = tail;
                tail.prev = head;
            }

            //头部添加 head<->1<->2<->tail    假如添加3
            public void addFirst(Node newNode){
                Node oldFirst = head.next;
                oldFirst.prev = newNode;
                head.next = newNode;
                newNode.prev = head;
                newNode.next = oldFirst;
            }

            //已知节点删除  head<->1<->2<->tail  假如删除2
            public void remove(Node node){
                Node prev = node.prev;
                Node next = node.next;
                prev.next = next;
                next.prev = prev;
            }

            //尾部删除
            public Node removeLast(){
                Node last = tail.prev;
                remove(last);
                return last;
            }
        }

        private final HashMap<Integer, Node> map = new HashMap<>();
        private final DoublyLinkedList list = new DoublyLinkedList();
        private final int capacity;
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            if(!map.containsKey(key)){
                return -1;
            }
            Node node = map.get(key);
            //hash表中存在该数据,改组数据应放到队头
            //先从中删除原始数据
            list.remove(node);
            //再将改组数据添加到队头
            list.addFirst(node);
            return node.value;
        }

        public void put(int key, int value) {
            if(map.containsKey(key)){ //更新
                Node node = map.get(key);
                node.value = value;
                list.remove(node);
                list.addFirst(node);
            }else{ //添加
                Node newNode = new Node(key, value);
                map.put(key, newNode);
                list.addFirst(newNode);
                if(map.size() > capacity){
                    Node removed = list.removeLast();
                    //删除hash表中的数据
                    map.remove(removed.key);
                }
            }
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3);
        System.out.println(cache.get(2)); // -1
        cache.put(4, 4);
        System.out.println(cache.get(1)); // -1
        System.out.println(cache.get(3)); // 3
    }
}

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

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

相关文章

LED显示屏安装后常见调试问题及解决方法

LED全彩显示屏在户外广泛应用&#xff0c;通常由多个箱体组装而成。在安装和调试过程中&#xff0c;可能会出现一些常见问题&#xff0c;下面对这些问题及解决方法进行汇总&#xff1a; 1. 加载不上可能是哪些原因造成的&#xff1f; - A. 确保控制系统硬件已正确上电&#xff…

RK3588平台开发系列讲解(视频篇)H.264码流结构介绍

文章目录 一、 码流查看工具二、 I帧、 P帧、 B帧三、序列四、GOP, 即关键帧间隔五、片和宏块沉淀、分享、成长,让自己和他人都能有所收获!😄 📢H.264码流结构介绍。 一、 码流查看工具 ① H.264码流查看工具: Elecard_streamEye、 Elecard StreamEye Tools、 Special…

本地部署Tomcat开源服务器并结合内网穿透远程访问

文章目录 前言1.本地Tomcat网页搭建1.1 Tomcat安装1.2 配置环境变量1.3 环境配置1.4 Tomcat运行测试1.5 Cpolar安装和注册 2.本地网页发布2.1.Cpolar云端设置2.2 Cpolar本地设置 3.公网访问测试4.结语 前言 Tomcat作为一个轻量级的服务器&#xff0c;不仅名字很有趣&#xff0…

智能小车案例:基于Raspberry Pi的自动巡航与避障系统

项目背景 随着物联网技术的不断发展&#xff0c;智能小车成为了现代生活和工业自动化中的重要工具。为了实现智能小车的自动巡航与避障功能&#xff0c;我们采用了Raspberry Pi作为主控制器&#xff0c;结合传感器和执行器&#xff0c;构建了一个完整的系统。 所需材料 Raspber…

山海鲸可视化:引领银行管理进入数据可视化新时代

在金融领域&#xff0c;数据是决策的关键。作为山海鲸可视化的开发者&#xff0c;我们深知数据的价值&#xff0c;并致力于通过可视化技术为银行管理提供更为直观、高效的数据分析工具。 应用场景&#xff1a; 风险管理&#xff1a;银行在运营过程中面临各种风险&#xff0c;如…

第17次修改了可删除可持久保存的前端html备忘录:增加年月日星期,增加倒计时,更改保存区名称可以多个备忘录保存不一样的信息,匹配背景主题:现代深色

第17次修改了可删除可持久保存的前端html备忘录&#xff1a;增加年月日星期&#xff0c;增加倒计时&#xff0c;更改保存区名称可以多个备忘录保存不一样的信息&#xff0c;匹配背景主题&#xff1a;现代深色 备忘录代码&#xff1a; <!DOCTYPE html> <html lang&quo…

Vue学习笔记14 --自定义hook函数/toRef/provide/inject等

9.自定义hook函数 什么是hook&#xff1f;—— 本质是一个函数&#xff0c;把setup函数中使用的Composition API进行了封装。 类似于vue2.x中的mixin。 自定义hook的优势: 复用代码, 让setup中的逻辑更清楚易懂。 10.toRef 作用&#xff1a;创建一个 ref 对象&#xff0c;其…

音视频数字化(音乐CD)

上篇文章【音视频数字化(音频数字化)】我们聊了音频数字化原理,其中谈到了音乐CD,结尾也提到了一个小问题:“CD音质是最高吗?为什么?”不知道大家是怎么理解的。 其实CD质量只是“无损”存储,但是数字化标准只是“44.1kHz,16bit”,因此相对于现在,音质不能说最高。 …

电脑用的视频编辑软件有哪些 视频剪辑软件排行榜 视频剪辑软件推荐 视频剪辑培训学习 视频剪辑制作自学 电脑视频剪辑需要什么配置

电脑视频剪辑软件这么多&#xff0c;到底哪些比较好用&#xff1f;下面就让我们以十大电脑视频剪辑软件排行榜来细数好用的软件。另外&#xff0c;电脑视频剪辑需要什么配置&#xff1f;本文也会给大家从内存、CPU等参数上介绍&#xff0c;并推荐好用的电脑设备。 一、十大电脑…

Orion-14B-Chat-RAG本地部署的解决方案

大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…

2024年能源环境、材料科学与人工智能国际会议(ICEEMSAI2024)

2024年能源环境、材料科学与人工智能国际会议(ICEEMSAI2024) 会议简介 2024国际能源环境、材料科学和人工智能大会&#xff08;ICEEMSAI 2024&#xff09;主要围绕能源环境、物质科学和人工智慧等研究领域&#xff0c;旨在吸引能源环境、先进材料和人工智能专家学者、科技人员…

Git系列---远程操作

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 引用 1.理解分布式版本控制…

赋能五星养老机构,河北爱晚红枫与清雷科技达成合作

“作为2023年河北省5家五星级养老机构之一&#xff0c;爱晚红枫医养服务有限公司以康复医学为特色&#xff0c;专为失能和半失能人群以及周边患者提供专业的康养治疗服务。此次和清雷科技合作&#xff0c;旨在用高科技的系统和监测产品进一步提升院区的医养结合能力&#xff0c…

如何用 python +ddt+excel 实现接口自动化测试

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 关注公众号【互联网杂货铺】&#xff0c;回复 1 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 “ 接口自动化测试是指通过编写代码或使用工具&#xff0c;模拟…

Linux中重定向是怎么一回事?

Linux中重定向是怎么一回事&#xff1f; 输出重定向追加重定向输入重定向 输出重定向 Linux下一切皆文件&#xff0c;当我们写下echo命令字符串时&#xff0c;相当于在显示器文件中写入数据 而输入echo 字符串 > filename时&#xff0c;相当于把原本应该写入显示器当中的数…

Linux进程控制:进程创建与等待

目录 一、fork函数 1.1fork函数的调用与功能 1.2fork函数的返回值与写实拷贝 1.3fork的常规用法与失败原因 二、进程终止 2.1进程的退出场景和常见退出方法 2.2_exit函数与exit函数 2.2.1_exit函数 2.2.2exit函数 2.3return退出 三、进程等待 3.1wait及waitpid的方法…

ElementUI Form:InputNumber 计数器

ElementUI安装与使用指南 InputNumber 计数器 点击下载learnelementuispringboot项目源码 效果图 el-radio.vue &#xff08;InputNumber 计数器&#xff09;页面效果图 项目里el-input-number.vue代码 <script> export default {name: el_input_number,data() {re…

Lua脚本

1.准备 1.简介 1.Lua是一种轻量小巧的脚本语言&#xff0c;用标准C语言编写并以源代码形式开放 2.目标 1.其设计目的是为了嵌入应用程序中&#xff0c;从而为应用程序提供灵活的扩展和定制功能 3.特点 1.轻量级&#xff1a;用标准C语言编写并以源代码形式开放&#xff0c;编译后…

嵌入式中屏幕能够显示汉字的原理方法

LCD是嵌入式常见设备&#xff0c;如何在LCD上显示汉字和英文&#xff1f;矢量字体和点阵字体有何不同&#xff1f;同一个字符为何有多种编码&#xff1f; GB2312、GB18030指什么&#xff1f;他们之间有关系吗&#xff1f;嵌入式设备如何支持多国语言&#xff1f;从哪里获取字库…

QGIS 矢量对齐工具-VectorBender

VectorBender 是一个QGIS Python 插件&#xff0c;允许转换矢量图层以匹配另一个几何图形。根据定义的输入点的数量&#xff0c;插件选择三种变换类型&#xff1a;平移、均匀或弯曲。 前两个允许快速对齐非地理参考数据&#xff0c;而第三个允许匹配具有复杂的非均匀和非线性变…