潮州网站建设推广,psd素材,财政局网站建设自查报告,wordpress全站搜索原题链接
难度#xff1a;middle\color{orange}{middle}middle 题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCacheLRUCacheLRUCache 类#xff1a; LRUCache(intcapacity)LRUCache(int capacity)LRUCache(intcapacity) 以 正整数 …原题链接
难度middle\color{orange}{middle}middle 题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCacheLRUCacheLRUCache 类
LRUCache(intcapacity)LRUCache(int capacity)LRUCache(intcapacity) 以 正整数 作为容量 capacitycapacitycapacity 初始化 LRU 缓存intget(intkey)int get(int key)intget(intkey) 如果关键字 keykeykey 存在于缓存中则返回关键字的值否则返回 −1-1−1 。voidput(intkey,intvalue)void put(int key, int value)voidput(intkey,intvalue) 如果关键字 keykeykey 已经存在则变更其数据值 valuevaluevalue 如果不存在则向缓存中插入该组 key−valuekey-valuekey−value 。如果插入操作导致关键字数量超过 capacitycapacitycapacity 则应该 逐出 最久未使用的关键字。
函数 getgetget 和 putputput 必须以 O(1)O(1)O(1) 的平均时间复杂度运行。
示例
输入
[LRUCache, put, put, get, put, get, put, get, get, get]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {11}
lRUCache.put(2, 2); // 缓存是 {11, 22}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4提示
1capacity30001 capacity 30001capacity30000key100000 key 100000key100000value1050 value 10^{5}0value105最多调用 2∗1052 * 10^{5}2∗105 次 getgetget 和 putputput 算法
(双链表 哈希) O(1)O(1)O(1)
使用一个双链表和一个哈希表
使用双链表存储节点哈希表动态存储key对应的链表中的节点地址
初始化
双链表插入 n 个节点n 是缓存大小 哈希表为空
get(key)
首先用哈希表判断key是否存在
如果key存在则返回对应的value同时将key对应的节点在当前位置输出并且放到双链表的最左侧如果key不存在则返回-1
set(key, value)
首先用哈希表判断key是否存在
如果key存在则修改对应的value同时将key对应的节点放到双链表的最左侧如果key不存在 如果缓存已满则删除双链表最右侧的节点上次使用时间最老的节点同时更新三个数据结构否则插入(key, value)创建一个新的节点并对其赋值(key, val)然后插入到双链表的最左侧同时个别更新哈希表。
时间复杂度
双链表和哈希表的增删改查操作的时间复杂度都是 O(1)O(1)O(1)所以 get 和 set 操作的时间复杂度也都是 O(1)O(1)O(1)
C 代码
class LRUCache {
public:struct Node {int key, val;Node *left, *right;Node(int _key, int _val): key(_key), val(_val), left(NULL), right(NULL) {}}*L, *R;unordered_mapint, Node* hash;int n;//从当前位置删除该节点void remove(Node* p) {p-right-left p-left;p-left-right p-right;}//把节点插入在双链表的最前端void insert(Node* p) {p-right L-right;p-left L;L-right-left p;L-right p;}LRUCache(int capacity) {n capacity;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];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 (hash.size() n) {auto p R-left;remove(p);hash.erase(p-key);delete p;}auto p new Node(key, value);hash[key] p;insert(p);}}
};/*** 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);*/
