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

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)

例题&#xff1a; 分析&#xff1a; 这道题可以用两个哈希表来实现&#xff0c;一个hash表&#xff08;kvMap&#xff09;用来存储节点&#xff0c;另一个hash表&#xff08;freqMap&#xff09;用来存储双向链表&#xff0c;链表的头节点代表最近使用的元素&#xff0c;离头节…...

Vue学习笔记:计算属性

计算属性 入门进阶二次进阶三次进阶四次进阶结界五次进阶六次进阶七次进阶八次进阶九次进阶终章彩蛋 入门 Vue.js中&#xff0c;计算属性示例&#xff1a; export default {data() {return {firstName: John,lastName: Doe};},computed: {// 计算属性&#xff1a;全名fullNam…...

深度学习本科课程 实验2 前馈神经网络

任务 3.3 课程实验要求 &#xff08;1&#xff09;手动实现前馈神经网络解决上述回归、二分类、多分类任务 l 从训练时间、预测精度、Loss变化等角度分析实验结果&#xff08;最好使用图表展示&#xff09; &#xff08;2&#xff09;利用torch.nn实现前馈神经网络解决上述回归…...

【python】python爱心代码【附源码】

一、实现效果&#xff1a; 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 二、完整代码&#xff1a; import math import random import threading import time from math import sin, cos, pi, log from tkinter import * import re# 烟花相关设置 Fireworks [] m…...

Linux---信号

前言 到饭点了&#xff0c;我点了一份外卖&#xff0c;然后又开了一把网游&#xff0c;这个时候&#xff0c;我在打游戏的过程中&#xff0c;我始终记得外卖小哥会随时给我打电话&#xff0c;通知我我去取外卖&#xff0c;这个时候游戏还没有结束。我在打游戏的过程中需要把外…...

24种设计模式之行为型模式(下)-Java版

软件设计模式是前辈们代码设计经验的总结&#xff0c;可以反复使用。设计模式共分为3大类&#xff0c;创建者模式(6种)、结构型模式(7种)、行为型模式(11种)&#xff0c;一共24种设计模式&#xff0c;软件设计一般需要满足7大基本原则。下面通过5章的学习一起来看看设计模式的魅…...

基于微信小程序的校园水电费管理小程序的研究与实现

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

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 模板部署 官方地址&#xff1a;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编程中&#xff0c;为了便于调试和代码质量和安全性检查。利用该方法可以在开发周期的早期捕获错误&#xff0c;并且检查团队编程风格&#xff0c;提高一致性。这对团队协作开发特别有用&#xff0c;可以提高开发的效率&#xff0c;保持代码质…...

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 画过一个三角三角形&#xff0c;html 的 Canvas 也画过一次类似的&#xff0c; 今天用 Flutter Canvas 试了下 感觉差不多&#xff1a; html 版本 大致效果如下&#xff1a; 思路和 html 实现的类似&#xff1a; 也就是找出点的位置&#xff0c;使用二阶…...

算法训练营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

一、背景及样式效果 因项目需要&#xff0c;需要文本编辑时&#xff0c;支持项目符号&#xff08;无序列表&#xff09;尝试了BulletSpan&#xff0c;但不是很理想&#xff0c;并且考虑到影响老版本回显等因素&#xff0c;最终决定自定义一个BulletEditText。 先看效果&…...

【axios报错异常】: Uncaught ReferenceError: axios is not defined

问题描述: 当前代码在vivo手机和小米手机运行是正常的,点击分享按钮调出相关弹框,发送接口进行分享,但是现在oppo手机出现了问题: 点击分享按钮没有反应. 问题解析: 安卓同事经过查询后,发现打印了错误: 但是不清楚这个问题是安卓端造成的还是前端造成的,大家都不清楚. 问题…...

Docker基础与持续集成

docker 基础知识&#xff1a; docker与虚拟机 !左边为虚拟机&#xff0c;右边为docker环境 – Server :物理机服务器Host OS &#xff1a;构建的操作系统Hypervisor &#xff1a;一种虚拟机软件&#xff0c;装了之后才能虚拟化操作系统Guest OS &#xff1a;虚拟化的操作系统…...

flutter开发实战-ijkplayer视频播放器功能

flutter开发实战-ijkplayer视频播放器功能 使用better_player播放器进行播放视频时候&#xff0c;在Android上会出现解码失败的问题&#xff0c;better_player使用的是video_player&#xff0c;video_player很多视频无法解码。最终采用ijkplayer播放器插件&#xff0c;在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 实验五:…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...