LFU缓存(Leetcode460)
例题:

分析:
这道题可以用两个哈希表来实现,一个hash表(kvMap)用来存储节点,另一个hash表(freqMap)用来存储双向链表,链表的头节点代表最近使用的元素,离头节点越远的节点代表最近最少使用的节点。
注意:freqMap 的 key 为节点的使用频次。
下图是freqMap的结构:

这是kvMap: 它的key没有什么特殊含义,value是储存的节点

题目中调用get方法会增加元素的使用次数(freq),这时在freqMap中需要将该节点转移到对应的位置上(比如该节点使用了两次,那就把该节点转移到key为2的位置上去)
put方法分为两种情况:如果要添加的key不存在,说明是新元素,放到key为1的位置上,如果key存在,此时是修改操作,改变元素的value值,对应的频次+1,同样放到对应的位置上。
淘汰策略:要保证两个hash表中的节点数一致。
代码实现:
package leetcode;import java.util.HashMap;//设计LFU缓存
public class LFUCacheLeetcode460 {static class LFUCache {static class Node{Node prev;Node next;int key;int value;int freq = 1;public Node(){}public Node(int key, int value) {this.key = key;this.value = value;}}static class DoublyLinkedList{Node head;Node tail;int size;public DoublyLinkedList(){head = tail = new Node();head.next = tail;tail.prev = head;}//头部添加 head<->1<->2<->tail 添加3public void addFirst(Node node){Node oldFirst = head.next;oldFirst.prev = node;head.next = node;node.prev = head;node.next = oldFirst;size++;}//指定节点删除 head<->1<->2<->3<->tail 删除2public void remove(Node node){Node prev = node.prev;Node next = node.next;prev.next = next;next.prev = prev;size--;}//删除最后一个节点public Node removeLast(){Node last = tail.prev;remove(last);return last;}//判断双向链表是否为空public boolean isEmpty(){return size == 0;}}private HashMap<Integer,Node> kvMap = new HashMap<>();private HashMap<Integer,DoublyLinkedList> freqMap = new HashMap<>();private int capacity;private int minFreq = 1;public LFUCache(int capacity) {this.capacity = capacity;}/** 获取节点 不存在:返回 -1* 存在: 增加节点的使用频次,将其转移到频次+1的链表中* 判断旧节点所在的链表是否为空,更新最小频次minFreq* */public int get(int key) {if(!kvMap.containsKey(key)){return -1;}Node node = kvMap.get(key);//先删除旧节点DoublyLinkedList list = freqMap.get(node.freq);list.remove(node);//判断当前链表是否为空,为空可能需要更新最小频次if(list.isEmpty() && node.freq == minFreq){minFreq++;}node.freq++;//将新节点放入新位置,可能该频次对应的链表不存在,不存在需要创建freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList()).addFirst(node);return node.value;}/** 更新* 将节点的value更新,增加节点的使用频次,将其转移到频次+1的链表中* 新增* 检查是否超过容量,若超过,淘汰minFreq链表的最后节点* 创建新节点,放入kvMap,并加入频次为 1 的双向链表* */public void put(int key, int value) {if(kvMap.containsKey(key)){ //更新Node node = kvMap.get(key);DoublyLinkedList list = freqMap.get(node.freq);list.remove(node);if(list.isEmpty() && node.freq == minFreq){minFreq++;}node.freq++;freqMap.computeIfAbsent(node.freq, k -> new DoublyLinkedList()).addFirst(node);node.value = value;}else{ //新增//先判断容量是否已满if(kvMap.size() == capacity){//执行淘汰策略Node node = freqMap.get(minFreq).removeLast();kvMap.remove(node.key);}Node node = new Node(key, value);kvMap.put(key, node);//加入频次为1的双向链表freqMap.computeIfAbsent(1, k -> new DoublyLinkedList()).addFirst(node);minFreq = 1;}}}public static void main(String[] args) {LFUCache cache = new LFUCache(2);cache.put(1, 1);cache.put(2, 2);System.out.println(cache.get(1)); // 1 freq=2cache.put(3, 3);System.out.println(cache.get(2)); // -1System.out.println(cache.get(3)); // 3 freq=2cache.put(4, 4);System.out.println(cache.get(1)); // -1System.out.println(cache.get(3)); // 3 freq=3System.out.println(cache.get(4)); // 4 freq=2}
}
相关文章:
LFU缓存(Leetcode460)
例题: 分析: 这道题可以用两个哈希表来实现,一个hash表(kvMap)用来存储节点,另一个hash表(freqMap)用来存储双向链表,链表的头节点代表最近使用的元素,离头节…...
Vue学习笔记:计算属性
计算属性 入门进阶二次进阶三次进阶四次进阶结界五次进阶六次进阶七次进阶八次进阶九次进阶终章彩蛋 入门 Vue.js中,计算属性示例: export default {data() {return {firstName: John,lastName: Doe};},computed: {// 计算属性:全名fullNam…...
深度学习本科课程 实验2 前馈神经网络
任务 3.3 课程实验要求 (1)手动实现前馈神经网络解决上述回归、二分类、多分类任务 l 从训练时间、预测精度、Loss变化等角度分析实验结果(最好使用图表展示) (2)利用torch.nn实现前馈神经网络解决上述回归…...
【python】python爱心代码【附源码】
一、实现效果: 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 二、完整代码: import math import random import threading import time from math import sin, cos, pi, log from tkinter import * import re# 烟花相关设置 Fireworks [] m…...
Linux---信号
前言 到饭点了,我点了一份外卖,然后又开了一把网游,这个时候,我在打游戏的过程中,我始终记得外卖小哥会随时给我打电话,通知我我去取外卖,这个时候游戏还没有结束。我在打游戏的过程中需要把外…...
24种设计模式之行为型模式(下)-Java版
软件设计模式是前辈们代码设计经验的总结,可以反复使用。设计模式共分为3大类,创建者模式(6种)、结构型模式(7种)、行为型模式(11种),一共24种设计模式,软件设计一般需要满足7大基本原则。下面通过5章的学习一起来看看设计模式的魅…...
基于微信小程序的校园水电费管理小程序的研究与实现
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…...
python二维高斯热力图绘制简单的思路代码
import numpy as np import matplotlib.pyplot as plt from scipy.ndimage import gaussian_filter import cv2# 生成一个示例图像 image_size 100 image np.zeros((image_size, image_size))# 在图像中心创建一个高亮区域 center_x, center_y image_size // 2, image_size …...
k8s 部署 nocas 同时部署mysql
使用 ygqygq2 的 helm 模板部署 官方地址:https://artifacthub.io/packages/helm/ygqygq2/nacos 添加 helm 仓库 helm repo add ygqygq2 https://ygqygq2.github.io/charts/下载 helm 安装文件 helm pull ygqygq2/nacos解压 tar -zxvf nacos-2.1.6.tgz执行 hel…...
GolangCI-Lint配置变更实践
GolangCI-Lint配置变更实践 Golang编程中,为了便于调试和代码质量和安全性检查。利用该方法可以在开发周期的早期捕获错误,并且检查团队编程风格,提高一致性。这对团队协作开发特别有用,可以提高开发的效率,保持代码质…...
UE中对象创建方法示例和类的理解
对象创建方法示例集 创建Actor示例 //创建一个护甲道具 AProp* armor GetWorld()->SpawnActor<AProp>(pos, rotator); 创建Component示例 UCapsuleComponent* CapsuleComponent CreateDefaultSubobject<UCapsuleComponent>(TEXT("CapsuleComponent&qu…...
ElementUI鼠标拖动没列宽度
其实 element ui 表格Table有提供给我们一个resizable属性 按官方文档上描述 它就是控制是否允许拖拽表格列大小的属性 而且 它的默认值就是 true 但是依旧很多人会反应拖拽不了 首先 表格要有边框 如果没有变宽 确实是拖拽不了 给 el-table加上 border属性 运行结果如下 但…...
Flutter canvas 画一条会动的波浪线 进度条
之前用 Flutter Canvas 画过一个三角三角形,html 的 Canvas 也画过一次类似的, 今天用 Flutter Canvas 试了下 感觉差不多: html 版本 大致效果如下: 思路和 html 实现的类似: 也就是找出点的位置,使用二阶…...
算法训练营day22, 回溯2
216. 组合总和 III func combinationSum3(k int, n int) [][]int { //存储全部集合 result : make([][]int, 0) //存储单次集合 path : make([]int, 0) var backtrace func(k int, n int, sum int, startIndex int) backtrace func(k int, n int, sum int, startIndex int) {…...
undefined symbol: avio_protocol_get_class, version LIBAVFORMAT_58
rv1126上进行编译和在虚拟机里面进行交叉编译ffmpeg都不行 解决办法查看 查看安装的ffmpeg链接的文件 ldd ./ffmpeg rootEASY-EAI-NANO:/home/nano/ffmpeg-4.3.6# ldd ffmpeg linux-vdso.so.1 (0xaeebd000)libavdevice.so.58 > /lib/arm-linux-gnueabihf/libavde…...
Android简单支持项目符号的EditText
一、背景及样式效果 因项目需要,需要文本编辑时,支持项目符号(无序列表)尝试了BulletSpan,但不是很理想,并且考虑到影响老版本回显等因素,最终决定自定义一个BulletEditText。 先看效果&…...
【axios报错异常】: Uncaught ReferenceError: axios is not defined
问题描述: 当前代码在vivo手机和小米手机运行是正常的,点击分享按钮调出相关弹框,发送接口进行分享,但是现在oppo手机出现了问题: 点击分享按钮没有反应. 问题解析: 安卓同事经过查询后,发现打印了错误: 但是不清楚这个问题是安卓端造成的还是前端造成的,大家都不清楚. 问题…...
Docker基础与持续集成
docker 基础知识: docker与虚拟机 !左边为虚拟机,右边为docker环境 – Server :物理机服务器Host OS :构建的操作系统Hypervisor :一种虚拟机软件,装了之后才能虚拟化操作系统Guest OS :虚拟化的操作系统…...
flutter开发实战-ijkplayer视频播放器功能
flutter开发实战-ijkplayer视频播放器功能 使用better_player播放器进行播放视频时候,在Android上会出现解码失败的问题,better_player使用的是video_player,video_player很多视频无法解码。最终采用ijkplayer播放器插件,在flutt…...
SpringFramework实战指南(五)
SpringFramework实战指南(五) 4.3 基于 注解 方式管理 Bean4.3.1 实验一: Bean注解标记和扫描 (IoC)4.3.2 实验二: 组件(Bean)作用域和周期方法注解4.3.3 实验三: Bean属性赋值:引用类型自动装配 (DI)4.3.4 实验四: Bean属性赋值:基本类型属性赋值 (DI)4.3.5 实验五:…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!
本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...
