Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LC146— LRU 缓存机制

LC146— LRU 缓存机制

作者头像
Java架构师必看
修改于 2023-09-25 08:17:06
修改于 2023-09-25 08:17:06
37100
代码可运行
举报
文章被收录于专栏:Java架构师必看Java架构师必看
运行总次数:0
代码可运行

146. LRU 缓存机制

难度中等1299

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制

实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?

LRU模板代码

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public class LRUCache {
   
    class DLinkedNode {
   
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {
   
        }

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

    //缓存映射表
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;


    public LRUCache(int capacity) {
   
        this.size = 0;
        this.capacity = capacity;

        //使用伪头部和伪尾部
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
   
        DLinkedNode node = cache.get(key);
        if (node == null) {
   
            return -1;
        }
        // 如果 key 存在,先通过哈希表定位,再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
   
        DLinkedNode node = cache.get(key);
        if (node == null) {
   
            //如果key不存在 创建一个新的节点
            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 {
   
            //如果key存在的 先通过定位哈希表位置 咋修改value 并移动到头部
            moveToHead(node);
            node.value = value;
        }
    }

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


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

    }

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

    }

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

}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
146. LRU 缓存机制
要在O(1)时间复杂度完成这两种操作,我们想到的使用HashMap来进行操作,而且参考LRUCache的特性,需要对元素进行移动或者删除,首选的是双向链表。
用户7447819
2021/07/23
2960
LeetCode146. LRU缓存机制
 基础数据结构的应用,HashMap中存的是key和Node,Node中存的是key和value
mathor
2018/08/16
3430
LeetCode146. LRU缓存机制
【LeetCode】146. LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类:
韩旭051
2021/01/07
4620
Leetcode LRU 缓存机制
缓存是一种提高数据读取性能的技术,在计算机中cpu和主内存之间读取数据存在差异,CPU和主内存之间有CPU缓存,而且在内存和硬盘有内存缓存。当主存容量远大于CPU缓存,或磁盘容量远大于主存时,哪些数据应该被应该被清理,哪些数据应该被保留,这就需要缓存淘汰策略来决定。常见的策略有三种:先进先出策略FIFO(First In,First Out)、最少使用策略LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used)。
用户10384376
2023/02/25
3170
Leetcode LRU 缓存机制
【Leetcode】146.LRU缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
Leetcode名企之路
2019/03/18
1.1K0
【Leetcode】146.LRU缓存机制
2020-09-18:LRU手撸,说下时间复杂度和空间复杂度。
空间复杂度:O(capacity),因为哈希表和双向链表最多存储 capacity+1 个元素。
福大大架构师每日一题
2020/09/18
1.1K0
2020-09-18:LRU手撸,说下时间复杂度和空间复杂度。
实现 LRU 缓存算法
LRU 算法全称是最近最少使用算法(Least Recently Use),是一种简单的缓存策略。顾名思义,LRU 算法会选出最近最少使用的数据进行淘汰。
Se7en258
2022/06/24
1K0
实现 LRU 缓存算法
LeetCode-146-LRU缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
benym
2022/07/14
3100
经典算法之链表篇(三)
ma布
2024/10/21
1060
经典算法之链表篇(三)
☆打卡算法☆LeetCode 146. LRU 缓存 算法解析
请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类:
恬静的小魔龙
2022/08/07
3150
☆打卡算法☆LeetCode 146. LRU 缓存 算法解析
LRU 缓存机制实现:哈希表 + 双向链表
LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
一个会写诗的程序员
2021/03/23
2K0
LRU 缓存机制实现:哈希表 + 双向链表
搞定大厂算法面试之leetcode精讲15.链表
搞定大厂算法面试之leetcode精讲15.链表 视频讲解(高效学习):点击学习 目录: 1.开篇介绍 2.时间空间复杂度 3.动态规划 4.贪心 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.单调栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其他类型题 链表操作如下图: 动画过大,点击查看 时间复杂度: prepend: O(1
全栈潇晨
2021/12/02
4490
一个今日头条的面试题——LRU原理和Redis实现
很久前参加过今日头条的面试,遇到一个题,目前半部分是如何实现 LRU,后半部分是 Redis 中如何实现 LRU。
Java架构
2018/09/20
2.1K0
一个今日头条的面试题——LRU原理和Redis实现
LRU算法与Caffeine、Redis中的缓存淘汰策略
在现代计算机系统中,缓存是提高系统性能的关键技术之一。为了避免频繁的IO操作,常见的做法是将数据存储在内存中的缓存中,以便快速访问。然而,由于内存资源有限,缓存的大小是有限的,因此需要一种策略来淘汰缓存中的数据,以便为新的数据腾出空间。本文将介绍一种常用的缓存淘汰策略——最近最少使用(Least Recently Used,LRU)算法,并且比较它与Caffeine和Redis中的缓存淘汰策略。
疯狂的KK
2023/08/17
5240
LRU算法与Caffeine、Redis中的缓存淘汰策略
数据结构界的“六脉神剑”:数组、链表、哈希表、栈、队列、树的终极解析与实战演练
在编程的世界里,数据结构是构建高效算法的基石。它们就像是武侠小说中的武功秘籍,掌握了它们,就能在代码的江湖中游刃有余。今天,我们就来深入探讨数据结构界的“六脉神剑”——数组、链表、哈希表、栈、队列和树。这六种数据结构,每一种都有其独特的运行原理和应用场景,它们是编程高手的必备技能。
疯狂的KK
2024/05/06
2870
数据结构界的“六脉神剑”:数组、链表、哈希表、栈、队列、树的终极解析与实战演练
146. LRU 缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类: LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。 void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之
编程张无忌
2021/06/29
2310
漫画:LRU从实现到应用层层剖析(第一讲)
LRU是Least Recently Used的缩写,译为最近最少使用。它的理论基础为“最近使用的数据会在未来一段时期内仍然被使用,已经很久没有使用的数据大概率在未来很长一段时间仍然不会被使用”由于该思想非常契合业务场景 ,并且可以解决很多实际开发中的问题,所以我们经常通过LRU的思想来作缓存,一般也将其称为LRU缓存机制。因为恰好leetcode上有这道题,所以我干脆把题目贴这里。但是对于LRU而言,希望大家不要局限于本题(大家不用担心学不会,我希望能做一个全网最简单的版本,希望可以坚持看下去!)下面,我们一起学习一下。
程序员小浩
2020/03/30
3440
漫画:LRU从实现到应用层层剖析(第一讲)
Leetcode模块训练2
1. 两数之和(1)# 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1: 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。 示例 2: 输入:nums = [3,2
素履coder
2022/11/16
3370
LRU算法简介
LRU(Least Recently Used)算法是一种缓存淘汰算法,常用于缓存系统中,通过保留最近使用的数据而淘汰最久未使用的数据,以提高缓存的命中率。LRU算法的核心思想是基于时间局部性原理:最近访问的数据在未来会被再次访问。
孟斯特
2024/01/28
6680
LRU算法简介
【LeetCode热题100】【链表】LRU缓存
我昨天面了天美L1的游戏客户端开发,面了我100分钟,问完实习、项目、计算机图形学和C++后给了我两道算法题做,一道是最长公共子序列,一道是LRU缓存,我知道是经典的题目,但是我都没敲过,我之前写过一个KV的数据库系统用过LRU(最近最少使用)缓存,用的是双向链表和哈希表解决的,当时是实现了一个双向链表,用来存储value,哈希表存储key和对应存储value的链表节点的指针,最近被访问的key就把它的节点移到链表头,超过容量就删掉链表尾
叶茂林
2024/03/31
920
相关推荐
146. LRU 缓存机制
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档