定个小目标之刷LeetCode热题(23)

今天写这道题,背过八股文的都应该知道LRU算法缓存的基本原理,在 Java 语言中,同样有类似的数据结构 LinkedHashMap本题我们采用自己创建哈希表+双链表的形式简单实现一下

对于get操作:通过cache.get(key)获取,如果不存在则直接返回-1,否则返回对于key的value并把该结点移动到链表头部

对于put操作:通过cache.get(key)获取,如果存在则直接替换该结点的value并把该结点移动到链表头部,否则创建新的结点,把它put到chache中,然后添加到链表头部并且size++,最后判断size是否大于capacity,如果大于则需要移除链表尾部结点,并且需要移除cache中对应的结点,最后size--

代码如下

class LRUCache {
    // 双链表
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {
        }

        public DLinkedNode(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }

    // 创建哈希表
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    // 哈希表当前结点个数
    private int size;
    // 最大结点个数,不能超过此阈值,否则需要进行移除链表尾结点操作
    private int capacity;
    // 双链表伪头部和伪尾部
    DLinkedNode head, tail;

    // 传入一个int型数字构建一个LRUCache对象
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    // get操作
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    public void removeNode(DLinkedNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    public void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // put操作
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

题目链接:题单 - 力扣(LeetCode)全球极客挚爱的技术成长平台

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

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

相关文章

【经典爬虫案例】用Python爬取微博热搜榜!

一、爬取目标 本次爬取的是: 微博热搜榜 &#xff08;代码也可直接在下方拿&#xff09;&#xff1a; ​ 分别爬取每条热搜的&#xff1a; 热搜标题、热搜排名、热搜类别、热度、链接地址。 下面&#xff0c;对页面进行分析。 经过分析&#xff0c;此页面没有XHR链接通过&am…

CSDN 自动上传图片并优化Markdown的图片显示

文章目录 完整代码一、上传资源二、替换 MD 中的引用文件为在线链接参考 完整代码 完整代码由两个文件组成&#xff0c;upload.py 和 main.py&#xff0c;放在同一目录下运行 main.py 就好&#xff01; # upload.py import requests class UploadPic: def __init__(self, c…

VBA学习(6): 调整工作表中所有图表尺寸并使其大小相同

有时候&#xff0c;我们想要将工作表中的所有图表进行缩放操作&#xff0c;且要求这些图表调整后的尺寸大小相同。如果使用手动拖放调整&#xff0c;看似大小相同&#xff0c;实际可能有差异。当然&#xff0c;也可以选取所有的图表后&#xff0c;在工作表选项卡中输入其宽度和…

TOP10!YashanDB斩获广东省优秀信创产品与解决方案双料荣誉

近日&#xff0c;2024广东软件风云榜结果出炉&#xff0c;表彰为广东软件产业和数字经济、新型工业化发展作出突出贡献的企业、企业家、优秀产品等。深算院崖山数据库系统 YashanDB荣获广东省“2024年优秀信息技术应用创新产品TOP10”和“2024年优秀信息技术应用创新行业应用解…

LeetCode 1789, 6, 138

目录 1789. 员工的直属部门题目链接表要求知识点思路代码 6. Z 字形变换题目链接标签思路代码 138. 随机链表的复制题目链接标签思路代码 1789. 员工的直属部门 题目链接 1789. 员工的直属部门 表 表Employee的字段为employee_id&#xff0c;department_id和primary_flag。…

SpringBoot购物网站

摘要 随着信息技术的高速发展&#xff0c;二十一世纪的网络技术和网络应用正在快速融入人们的生活&#xff0c;并且由于网络服务以及网络应用日渐普及&#xff0c;人们对于现在生活的需求也随之增长&#xff0c;而网上购物的便捷对人们的吸引力越来越大&#xff0c;购物网站可…

Android 大话binder通信 (上)

戳蓝字“牛晓伟”关注我哦&#xff01; 用心坚持输出易读、有趣、有深度、高质量、体系化的技术文章 本文摘要 用故事的方式把binder通信的整个过程都描述出来&#xff0c;binder通信都经历了哪些节点&#xff0c;在这些节点上的数据有哪些变化&#xff0c;同时还对binder通…

触控MCU芯片(1):英飞凌PSoC第6代第7代

前言: 说到触摸MCU芯片,这个历史也是很久了,比如日常经常接触到的洗衣机、电冰箱、小家电,隔着一层玻璃,轻轻一按就能识别按键,感觉比过去纯机械式的按键更高级更美观,不仅白电,现在很多汽车也都在进行触摸按键的改版,不再使用笨重的机械按键,比如空调调温按键、档位…

淘宝评论电商API接口,揭示用户真实评价

随着互联网的快速发展&#xff0c;电子商务已经成为了人们生活中不可或缺的一部分。淘宝作为中国最大的在线购物平台&#xff0c;拥有数以亿计的消费者和商家。而用户评价作为消费者了解商品和服务的重要途径&#xff0c;对于商家的信誉和销售有着至关重要的影响。因此&#xf…

SCADA软件地毯式介绍,你想知道的都在这里.

很多小伙伴对SCADA很陌生&#xff0c;殊不知这个可是智慧工业制造的大脑和中枢神经&#xff0c;很多指令的发出&#xff0c;监控状态的现实都得通过这个系统&#xff0c;本文详解介绍一下什么是SCADA&#xff0c;重大作用&#xff0c;其在工业制造中的位置&#xff0c;以及市面…

Export S parameter sweep data 导出 S 参数扫描代码

Export S parameter sweep data 导出 S 参数扫描代码 正文正文 相信有不少小伙伴们会比较苦恼一件事情,就是 Lumerical Script 中的绘图并不智能。功能较为简陋以至于图像展现时不够美观,因此,很多时候我们需要将仿真数据导出使用。那么如何导出仿真数据呢?在 Lumerical S…

【Linux进程通信】Linux进程间的无声对话:匿名管道与命名管道技术

W...Y的主页 &#x1f60a; 代码仓库分享 &#x1f495; 前言&#xff1a;我们已经知道了进程和文件的基本理论&#xff0c;知道了进程和文件的重要性。进程具有独立性&#xff0c;所以两个进程不能直接通信&#xff0c;那么进程间应该怎样通信呢&#xff1f;我们今天来解开其…

物联网技术-第4章物联网通信技术-4.1计算机网络

目录 1.1计算机网络拓扑与组成 &#xff08;1&#xff09;全连通式网络 &#xff08;2&#xff09;星型网 &#xff08;3&#xff09;环形网 &#xff08;4&#xff09;总线网 &#xff08;5&#xff09;不规则型网 1.2数据交换类型 &#xff08;1&#xff09;电路交换网 &…

硬件开发笔记(十八):核心板与底板之间的连接方式介绍说明:板对板连接器

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/139663096 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…

DSP28335:独立按键控制LED灯

做任何事情不可操之过急&#xff0c;虽然我们可能在之前的单片机学过相关的原理&#xff0c;但是一个新的单片机依然有他的学习的地方&#xff0c;之前我觉得很简单&#xff0c;就跳过这个学习&#xff0c;结果到后面就很浮躁&#xff0c;导致后面的内容与这一章相连接的时候&a…

利用这个css属性,你也能轻松实现一个新手引导库

相信大家或多或少都在各种网站上使用过新手引导&#xff0c;当网站提供的功能有点复杂时&#xff0c;这是一个对新手非常友好的功能&#xff0c;可以跟随新手引导一步一步了解网站的各种功能&#xff0c;我们要做的只是点击下一步或者上一步&#xff0c;网站就能滚动到指定位置…

齐普夫定律在循环神经网络中的语言模型的应用

目录 齐普夫定律解释公式解释图与公式的关系代码与图的分析结论 使用对数表达方式的原因1. 线性化非线性关系2. 方便数据可视化和分析3. 降低数值范围4. 方便参数估计公式详细解释结论 来自&#xff1a;https://zh-v2.d2l.ai/chapter_recurrent-neural-networks/language-model…

智慧校园发展趋势:2024年及未来教育科技展望

展望2024年及未来的教育科技领域&#xff0c;智慧校园的发展正引领着一场教育模式的深刻变革&#xff0c;其核心在于更深层次地融合技术与教育实践。随着人工智能技术的不断成熟&#xff0c;个性化学习将不再停留于表面&#xff0c;而是深入到每个学生的个性化需求之中。通过精…

电感的本质是什么

什么是电感&#xff1f; 电感器件一般是指螺线圈&#xff0c;由导线圈一圈靠一圈地绕在绝缘管上&#xff0c;绝缘管可以是空心的&#xff0c;也可以包含铁芯或磁粉芯。 为什么把’线’绕成’圈’就是电感&#xff1f; 电感的工作原理非常抽象&#xff0c;为了解释什么是电感…

单片机 PWM输入捕获【学习记录】

前言 学习是永无止境的&#xff0c;就算之前学过的东西再次学习一遍也能狗学习到很多东西&#xff0c;输入捕获很早之前就用过了&#xff0c;但是仅仅是照搬例程没有去进行理解。温故而知新&#xff01; 定时器 定时器简介 定时器的分类 高级定时器 通用定时器 基本定时器…