LeetCode 460. LFU 缓存(链表+哈希)

2024-04-15 22:58

本文主要是介绍LeetCode 460. LFU 缓存(链表+哈希),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述
思路:
链表+哈希,类似LRU的构造。代码参考自leetcode官方题解。

struct Node {int key,val,freq;Node(int _key,int _val,int _freq):key(_key),val(_val),freq(_freq){}
};
class LFUCache {
private:int minq,cap;unordered_map<int,list<Node>::iterator>key_table;unordered_map<int,list<Node>>freq_table;
public:LFUCache(int capacity) {cap = capacity;minq = 0;key_table.clear();freq_table.clear();}int get(int key) {if(cap == 0) return -1;auto it = key_table.find(key);if(it == key_table.end()) return -1;list<Node>::iterator it2 = it -> second;Node now = *it2;freq_table[now.freq].erase(it2);if(freq_table[now.freq].size() == 0) {if(minq == now.freq) minq++;freq_table.erase(now.freq);}freq_table[now.freq + 1].push_front({key,now.val,now.freq + 1});key_table[key] = freq_table[now.freq + 1].begin();return now.val;}void put(int key, int value) {if(cap == 0) return;auto it = key_table.find(key);if(it == key_table.end()) {if(key_table.size() == cap) {key_table.erase(freq_table[minq].back().key);freq_table[minq].pop_back();if(freq_table[minq].size() == 0) {freq_table.erase(minq);}}minq = 1;freq_table[1].push_front({key,value,1});key_table[key] = freq_table[1].begin();} else {list<Node>::iterator it2 = it -> second;Node now = *it2;freq_table[now.freq].erase(it2);if(freq_table[now.freq].size() == 0) {if(now.freq == minq) minq++;freq_table.erase(now.freq);}freq_table[now.freq + 1].push_front({key,value,now.freq + 1});key_table[key] = freq_table[now.freq + 1].begin();}} 
};/*** Your LFUCache object will be instantiated and called as such:* LFUCache* obj = new LFUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/

这篇关于LeetCode 460. LFU 缓存(链表+哈希)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907160

相关文章

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

一文详解Nginx的强缓存和协商缓存

《一文详解Nginx的强缓存和协商缓存》这篇文章主要为大家详细介绍了Nginx中强缓存和协商缓存的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、强缓存(Strong Cache)1. 定义2. 响应头3. Nginx 配置示例4. 行为5. 适用场景二、协商缓存(协

Golang基于内存的键值存储缓存库go-cache

《Golang基于内存的键值存储缓存库go-cache》go-cache是一个内存中的key:valuestore/cache库,适用于单机应用程序,本文主要介绍了Golang基于内存的键值存储缓存库... 目录文档安装方法示例1示例2使用注意点优点缺点go-cache 和 Redis 缓存对比1)功能特性

MySQL8.0设置redo缓存大小的实现

《MySQL8.0设置redo缓存大小的实现》本文主要在MySQL8.0.30及之后版本中使用innodb_redo_log_capacity参数在线更改redo缓存文件大小,下面就来介绍一下,具有一... mysql 8.0.30及之后版本可以使用innodb_redo_log_capacity参数来更改

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

MySQL 缓存机制与架构解析(最新推荐)

《MySQL缓存机制与架构解析(最新推荐)》本文详细介绍了MySQL的缓存机制和整体架构,包括一级缓存(InnoDBBufferPool)和二级缓存(QueryCache),文章还探讨了SQL... 目录一、mysql缓存机制概述二、MySQL整体架构三、SQL查询执行全流程四、MySQL 8.0为何移除查

Redis缓存问题与缓存更新机制详解

《Redis缓存问题与缓存更新机制详解》本文主要介绍了缓存问题及其解决方案,包括缓存穿透、缓存击穿、缓存雪崩等问题的成因以及相应的预防和解决方法,同时,还详细探讨了缓存更新机制,包括不同情况下的缓存更... 目录一、缓存问题1.1 缓存穿透1.1.1 问题来源1.1.2 解决方案1.2 缓存击穿1.2.1

Redis与缓存解读

《Redis与缓存解读》文章介绍了Redis作为缓存层的优势和缺点,并分析了六种缓存更新策略,包括超时剔除、先删缓存再更新数据库、旁路缓存、先更新数据库再删缓存、先更新数据库再更新缓存、读写穿透和异步... 目录缓存缓存优缺点缓存更新策略超时剔除先删缓存再更新数据库旁路缓存(先更新数据库,再删缓存)先更新数