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

【难点】【LRU】146.LRU缓存

题目

法1:基于Java的LinkedHashMap

必须掌握法1。参考链接
关于LinkedHashMap的介绍

class LRUCache {int cap;LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();public LRUCache(int capacity) { this.cap = capacity;}public int get(int key) {if (!cache.containsKey(key)) {return -1;}// 将 key 变为最近使用makeRecently(key);return cache.get(key);}public void put(int key, int val) {if (cache.containsKey(key)) {// 修改 key 的值cache.put(key, val);// 将 key 变为最近使用makeRecently(key);return;}if (cache.size() >= this.cap) {// 链表头部就是最久未使用的 keyint oldestKey = cache.keySet().iterator().next();cache.remove(oldestKey);}// 将新的 key 添加链表尾部cache.put(key, val);}private void makeRecently(int key) {int val = cache.get(key);// 删除 key,重新插入到队尾cache.remove(key);cache.put(key, val);}
}

法2:自定义数据结构

参考链接

public 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<Integer, DLinkedNode>();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,并移到头部node.value = value;moveToHead(node);}}private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail() {DLinkedNode res = tail.prev;removeNode(res);return res;}
}
http://www.lryc.cn/news/263365.html

相关文章:

  • 基于YOLOv8深度学习的吸烟/抽烟行为检测系统【python源码+Pyqt5界面+数据集+训练代码】目标检测、深度学习实战
  • 菜鸟学习日记(python)——匿名函数
  • CompleteFuture与Future的比较
  • 数据分享 I 全国市级商品房屋销售数据,shp/excel格式,2005-2020年数据
  • 面试题总结(十一)【C++】【华清远见西安中心】
  • c++_01_名字空间_复合类型_缺省参数_哑元函数
  • 前端常见面试题之html和css篇
  • 使用libaom处理av1编码教程
  • 面试题总结(十)【数据库】【华清远见西安中心】
  • 计算机网络:物理层(三种数据交换方式)
  • ubuntu18.04 64 位安装笔记——备赛笔记——2024全国职业院校技能大赛“大数据应用开发”赛项——任务2:离线数据处理
  • Nvidia 驱动安装不完整记录
  • 龙芯loongarch64服务器编译安装gcc-8.3.0
  • 宏基因组学Metagenome-磷循环Pcycle功能基因分析-从分析过程到代码及结果演示-超详细保姆级流程
  • element plus 日期范围 自定义内容
  • [23] GaussianAvatars: Photorealistic Head Avatars with Rigged 3D Gaussians
  • JSON Ajax
  • ElasticSearch与HBase的分布式存储设计
  • 回归预测 | MATLAB实现NGO-SCN北方苍鹰算法优化随机配置网络的数据回归预测 (多指标,多图)
  • Bezier 曲线 2D
  • Linux静态ip
  • 一种基于外观-运动语义表示一致性的视频异常检测框架 论文阅读
  • Netty—NIO万字详解
  • 面试经典150题(32-37)
  • 手撕分布式缓存---HTTP Client搭建
  • word如何快速制作简易代码块
  • Linux常用网络指令
  • Spark on Yarn 安装配置实验(3.1.1)
  • 详解YOLOv5网络结构/数据集获取/环境搭建/训练/推理/验证/导出/部署
  • ansible(不能交互)