Leetcode|460. LFU 缓存(KV+KF+FK哈希链表+minFreq)

2024-01-10 03:48

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

在这里插入图片描述
在这里插入图片描述

相关题目

《Leetcode|146. LRU 缓存机制(key2node哈希链表)》
《Leetcode|460. LFU 缓存(KV+KF+FK哈希链表+minFreq)》

解题逻辑

这道题虽然不难,但是逻辑较多,第一次手撕时由于漏掉2个逻辑没有AC,后来花了些时间debug完才AC,对于这种逻辑较多但不难的题,想要一次写对,还是不要偷懒。先不要着急写代码,把大致逻辑图画出来,这样能避免写代码时部分细节逻辑的遗忘

  • get(key)put(key, val)基本逻辑
    在这里插入图片描述

  • increaseFreq(key)基本逻辑在这里插入图片描述

  • removeMinFreq(key)insertNew(key, val)基本逻辑

完整代码

/**双链表数据结构**/
struct DListNode {int key;DListNode* prev;DListNode* next;DListNode(): key(0), prev(nullptr), next(nullptr) {}DListNode(int _key): key(_key), prev(nullptr), next(nullptr) {}
};
/**哈希链表数据结构**/
class HashList {
private:DListNode* head;DListNode* tail;unordered_map<int, DListNode*> key2node;  // 哈希链表int size;
public:HashList(int _key): size(0) {// 添加头尾空节点head = new DListNode();tail = new DListNode();head->next = tail;tail->prev = head;addRecentKey(_key);}void addRecentKey(int key) {auto node = new DListNode(key);// 插入1个最近使用节点node->prev = tail->prev;node->next = tail;tail->prev->next = node;tail->prev = node;// 更新哈希表key2node[key] = node;size++;}void removeAnyKey(int key) {auto& node = key2node[key];// 1.删链表节点node->prev->next = node->next;node->next->prev = node->prev;// 2.删哈希表节点key2node.erase(key);size--;}int removeLongestUsed() {int key = head->next->key;removeAnyKey(key);return key;}bool isEmpty() { return size == 0; } 
};class LFUCache {
private:int capacity, size, minFreq;unordered_map<int, int> key2val;        // KV表unordered_map<int, int> key2freq;       // KF表unordered_map<int, HashList*> freq2key; // FK表
public:LFUCache(int _capacity): capacity(_capacity), size(0), minFreq(0) {}int get(int key) {if (!key2val.count(key)) return -1;increaseFreq(key);return key2val[key];}void put(int key, int value) {if (!capacity) return;if (key2val.count(key)) {key2val[key] = value;increaseFreq(key);return;}if (capacity == size) removeMinFreq();insertNew(key, value);}void increaseFreq(int key) {int freq = key2freq[key];// 1.更新KF表key2freq[key]++;// 2.更新FK表// 删除FK[freq]哈希链表对应的key, 删除后若哈希链表为空,则删除FK中的freq项freq2key[freq]->removeAnyKey(key);if (freq2key[freq]->isEmpty()) {freq2key.erase(freq);if (freq == minFreq) minFreq++;}// 若FK[freq + 1]存在,则直接添加if (freq2key.count(freq + 1)) freq2key[freq + 1]->addRecentKey(key);// 若FK[freq + 1]不存在,则初始化哈希链表else freq2key[freq + 1] = new HashList(key);}void removeMinFreq() {auto& hashList = freq2key[minFreq];// 1.删FK表int deleteKey = hashList->removeLongestUsed();if (hashList->isEmpty()) freq2key.erase(minFreq);// 2.删KV表 key2val.erase(deleteKey);// 3.删KF表 key2freq.erase(deleteKey);size--;  // 无需更新minFreq, 因为本方法仅在put()添加新键值对时调用,minFreq = 1}void insertNew(int key, int value) {key2val[key] = value;key2freq[key] = 1;// 若freq2key[1]已存在,则直接按时序添加到哈希链表中if (freq2key.count(1)) freq2key[1]->addRecentKey(key);// 若freq2key[1]不存在,则为此初始化新哈希链表else freq2key[1] = new HashList(key);minFreq = 1;size++;}
};
/*** 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 缓存(KV+KF+FK哈希链表+minFreq)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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作为缓存层的优势和缺点,并分析了六种缓存更新策略,包括超时剔除、先删缓存再更新数据库、旁路缓存、先更新数据库再删缓存、先更新数据库再更新缓存、读写穿透和异步... 目录缓存缓存优缺点缓存更新策略超时剔除先删缓存再更新数据库旁路缓存(先更新数据库,再删缓存)先更新数