没有合适的资源?快使用搜索试试~ 我知道了~
open-gap#Leetcode-Road#146.LRU缓存机制1
需积分: 0 0 下载量 194 浏览量
2022-07-25
14:28:42
上传
评论
收藏 4KB MD 举报
温馨提示
试读
解法一:使用哈希表与双向链表的组合结构,又称为哈希链表 (题解)//双链表的容量// 使用list的迭代器可以在O(1)时间内完成元素删除操作**// 访问的
资源推荐
资源详情
资源评论
# LRU缓存机制 #
`难度:中等`
运用你所掌握的数据结构,设计和实现一个 [LRU (最近最少使用)](https://baike.baidu.com/item/LRU) 缓存机制。它应该支持以下操作: 获取数据 `get` 和 写入数据 `put` 。
获取数据 `get(key)` - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 `put(key, value)` - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
**进阶**:
你是否可以在 **O(1)** 时间复杂度内完成这两种操作?
**示例**:
>```C++
>LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
>
>cache.put(1, 1);
>cache.put(2, 2);
>cache.get(1); // 返回 1
>cache.put(3, 3); // 该操作会使得密钥 2 作废
>cache.get(2); // 返回 -1 (未找到)
>cache.put(4, 4); // 该操作会使得密钥 1 作废
>cache.get(1); // 返回 -1 (未找到)
>cache.get(3); //
点击阅读更多
资源评论
乔木Leo
- 粉丝: 21
- 资源: 301
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功