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

leetcode 面试150之 156.LUR 缓存

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

题目重点:O(1)实现查找和删除

O(1)查找我们可以通过unordered_map底层哈希表来实现
这里我们如果缓存满了还得删除最久未使用关键字 ,所以我们得使用一个O(1)维护的“使用队列”,数组我们无法实现O(1)删除,而双向链表能实现O(1)删除,但是无法实现O(1)查询

所以我们这里用到了unordered_map<int,listnode*>映射为listnode*,通过map去实现O(1)查询
而listnode*双向链表实现O(1)插入和删除

起初我并未想到用双向链表而是用deque去维护“使用队列”,后者在维护队列无法做到O(1),包超时的

上代码:

class LRUCache {
public:struct listnode{int key;int val;listnode* pre;listnode* next;listnode(int k,int v):key(k),val(v),pre(nullptr),next(nullptr){}};int max_;                          //最大空间listnode* head;                    //头哨兵节点listnode* tail;                    //尾哨兵节点unordered_map<int,listnode*> dp;   //精华//初始化    LRUCache(int capacity) {max_=capacity;head=new listnode(0,0);tail=new listnode(0,0);head->next=tail;tail->pre=head;}//双向链表头插法 将处理的node节点 使用优先级提高void addnode(listnode* node){node->next=head->next;head->next->pre=node;head->next=node;node->pre=head;}//断开node节点 并未delete  void remove_node(listnode* node){node->pre->next=node->next;node->next->pre=node->pre;}//查询数据int get(int key) {if(dp.count(key))          //查询成功 提高该节点的“使用队列”优先级{remove_node(dp[key]);addnode(dp[key]);return dp[key]->val;}else return -1;}//插入数据void put(int key, int value) {if(dp.count(key)){dp[key]->val=value;    //已经存在   更新val后,取走节点后插入头  提高优先级remove_node(dp[key]);addnode(dp[key]);}//key不存在else{if(max_==dp.size())          //空间已满  删除优先级低节点 也就是 tail->pre{listnode* temp=tail->pre;remove_node(temp);dp.erase(temp->key);delete temp;               //释放内存}//无论空间是否够 都需要插入这个key节点listnode* node=new listnode(key,value); addnode(node);dp.insert({key,node});}}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/

http://www.lryc.cn/news/488798.html

相关文章:

  • 启发式搜索算法复现
  • 【IDE】使用指南
  • 设计编程网站集:简述可扩展性系统设计(笔记)
  • 「Mac玩转仓颉内测版25」基础篇5 - 布尔类型详解
  • Fashion-VDM:引领视频虚拟试穿技术的新篇章
  • Scala中的集合复习(1)
  • Java依赖包漏洞检测命令
  • 【Java】强制类型转换
  • RabbitMQ消息可靠性保证机制4--消费端限流
  • 查找萤石云IOS Sdk中的编解码接口
  • erchas
  • 【网络安全】SSL(一):为什么需要 Keyless SSL?
  • ggplot2 分面图等添加注释文字,相加哪里加哪里: 自定义函数 AddText()
  • 解读缓存问题的技术旅程
  • 洛谷P1597
  • 2411rust,76~79
  • vue2.0前端管理系统界面布局设置
  • 4. SQL视图
  • Simulink学习笔记【PID UG联动仿真】
  • 【Python】30个Python爬虫的实战项目!!!(附源码)
  • uni-app 界面TabBar中间大图标设置的两种方法
  • 什么是Sass,有什么特点
  • 服务器端渲染 (SSR) 与客户端渲染 (CSR)
  • 数据结构(Java版)第一期:时间复杂度和空间复杂度
  • 基于web的音乐网站(Java+SpringBoot+Mysql)
  • 用go语言后端开发速查
  • GeekChallenge 2024 第十五届极客大挑战 pwn AK
  • 禅道是什么,nas是什么,ssh是什么,finalshell是什么,git命令feat 、fix分别什么意思
  • 点云-半径搜索法-Radius Search
  • P11290 【MX-S6-T2】「KDOI-11」飞船