Leetcode146. LRU 缓存(HOT100)

embedded/2024/11/26 23:12:17/

链接

代码:

class LRUCache {
private:struct Node{int key,val;Node* left,*right;Node(int _key,int _val):key(_key),val(_val){}}*L,*R;unordered_map<int,Node*> hash;int n;public:void remove(struct Node* p){p->left->right = p->right;p->right->left = p->left;//不要delete p;因为有可能我们只是更新一个Node,即:将它从list中remove,然后再insert进来,真正删掉一个节点是在超过capacity时}void insert(struct Node* p){p->right = L->right;p->left = L;L->right = p;p->right->left = p;}LRUCache(int capacity) {n = capacity;//capacity是一个形参,函数结束就销毁了,所以我们用一个n来记录L = new Node(-1,-1),R = new Node(-1,-1);//定义左右两个节点,用来管理双向链表。L->right = R,R->left = L;}int get(int key) {if(hash.count(key)==0)return -1;auto p = hash[key];//p是一个迭代器remove(p);insert(p);return p->val;}void put(int key, int value) {if(hash.count(key)){auto p = hash[key];p->val = value;remove(p);insert(p);}else{if(n==hash.size()){auto p = R->left;//p是一个Noderemove(p);hash.erase(p->key);//erase需要参数key,我们通过Node找到其中的keydelete p;}auto q = new Node(key,value);hash[key] = q;//not hash[key] = value;//hash的value是一个Nodeinsert(q);//在双向链表中插入时,别忘了在hash中也插入}}
};

图解:

L和R是两个指向虚拟左右节点的指针,它们中间管理所有已经在hash表中的key value值以及相邻节点的地址。 


http://www.ppmy.cn/embedded/140753.html

相关文章

Docker部署Canal实现将Mysql数据同步至ES

目录 Canal 是什么?一、安装docker1.安装2.启动二、安装docker-compose1.卸载旧版本2.下载最新版3.授权4.检查版本三、配置MySQL1.开启 Binlog 写入,配置 binlog-format 为 ROW 模式2.授权 canal 有 slave 的权限四、创建docker网络五、部署canal-admin1.在数据库中创建canal…

C++ —— 以真我之名 如飞花般绚丽 - 智能指针

目录 1. RAII和智能指针的设计思路 2. C标准库智能指针的使用 2.1 auto_ptr 2.2 unique_ptr 2.3 简单模拟实现auto_ptr和unique_ptr的核心功能 2.4 shared_ptr 2.4.1 make_shared 2.5 weak_ptr 2.6 shared_ptr的缺陷&#xff1a;循环引用问题 3. shared_ptr 和 unique_…

Linux的开发工具(二)

1.vim的基本操作 正常模式到插入模式 输入a 输入i 输入o 示例 输入iao下面的就会变成INSERT模式 插入模式到正常模式 按Esc键 正常模式到低行模式 shift&#xff1b; &#xff1a;w保存当前文件 &#xff1a;wq保存并退出 &#xff1a;q&#xff01;强制退出 2.vi…

一区北方苍鹰算法优化+创新改进Transformer!NGO-Transformer-LSTM多变量回归预测

一区北方苍鹰算法优化创新改进Transformer&#xff01;NGO-Transformer-LSTM多变量回归预测 目录 一区北方苍鹰算法优化创新改进Transformer&#xff01;NGO-Transformer-LSTM多变量回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab NGO-Transformer-LST…

【JavaEE初阶】多线程初阶下部

文章目录 前言一、volatile关键字volatile 能保证内存可见性 二、wait 和 notify2.1 wait()方法2.2 notify()方法2.3 notifyAll()方法2.4 wait 和 sleep 的对比&#xff08;面试题&#xff09; 三、多线程案例单例模式 四、总结-保证线程安全的思路五、对比线程和进程总结 前言…

基于YOLOv8深度学习的独居老人情感状态监护系统(PyQt5界面+数据集+训练代码)

本研究提出了一种创新的独居老人情感状态监护系统&#xff0c;基于YOLOV8深度学习模型&#xff0c;旨在通过对老年人面部表情的实时监测与分析&#xff0c;来精准识别其情感变化&#xff0c;从而提高独居老人的生活质量&#xff0c;确保其心理健康。本系统通过整合先进的YOLOV8…

Golang 反射

一、Go反射的应用场景 &#xff08;一&#xff09;对象序列化和反序列化 场景描述 在处理网络通信&#xff0c;数据存储等场景中&#xff0c;需要将对象转换为字节流&#xff08;序列化&#xff09;以便传输或存储&#xff0c;在接收端再将字节流转换回对象&#xff08;反序列…

Linux基础指令(汇总)

文章目录 1. ls指令2. pwd指令3. cd指令4. touch指令5. mkdir指令6. rmdir指令&&rm指令7. man指令8. cp指令8. mv指令9. cat指令10. more指令11. less指令12. head指令13. tail指令14. date指令15. cal指令16. find指令17. which指令18. whereis指令19. alias指令20. g…