【LeetCode】146. LRU Cache
LeetCode cache LRU
2023-09-11 14:20:27 时间
LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get
and set
.
get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
这题关键在于,怎样判断每个value是否算“最近使用”?
一个简单的想法是对每个键值对保留一个年龄,当cache满时,删除最“老”的键值对。
然而在删除节点时,寻找最“老”节点需要O(n)时间。
因此建立一个双向链表,最近使用的调整到头部,需要删除则删除尾部。
这样寻找最“老”节点就为O(1)时间。
然而在get函数时查找所需节点仍为O(n)时间。
因此再加入映射表m,空间换时间,查找变为O(1)。
struct Node { int key; int val; Node* prev; Node* next; Node(int k, int v): key(k), val(v), prev(NULL), next(NULL) {} }; class LRUCache{ public: Node* head; //most recently used Node* tail; //least recently used unordered_map<int, Node*> m; int curcap; int maxcap; LRUCache(int capacity) { head = new Node(-1, -1); tail = new Node(-1, -1); head->next = tail; tail->prev = head; curcap = 0; maxcap = capacity; } int get(int key) { if(m[key] == NULL) return -1; else { Node* node = m[key]; delnode(node); addtohead(node); return node->val; } } void set(int key, int value) { if(m[key] == NULL) { if(curcap == maxcap) { m[tail->prev->key] = NULL; delnode(tail->prev); } Node* node = new Node(key, value); addtohead(node); m[key] = node; if(curcap < maxcap) curcap ++; } else { Node* node = m[key]; node->val = value; delnode(node); addtohead(node); } } void delnode(Node* node) { Node* prev = node->prev; Node* next = node->next; prev->next = next; next->prev = prev; } void addtohead(Node* node) { node->next = head->next; node->prev = head; head->next->prev = node; head->next = node; } };
相关文章
- leetcode 之LRU Cache(26)
- Java实现 LeetCode 667 优美的排列 II(暴力)
- Java实现 LeetCode 438 找到字符串中所有字母异位词
- Java实现 LeetCode 179 最大数
- Java实现 LeetCode 60 第k个排列
- Java实现 LeetCode 131 分割回文串
- 【LeetCode算法-38】Count and Say
- SAP BSP set server cache via CL_BSP_UTILITY-SET_BROWSER_CACHE
- HTTP 头部字段 Cache Control max-age = 0 和 no-cache 的区别
- ATITIT db perf enhs 数据库性能优化 目录 第一章 Cache类1 第一节 查询cache1 第二节 Update cache2 第三节 内存表机制 零时表2 第四节 雾
- 【LeetCode 76】最小覆盖子串
- LeetCode - 10 正则表达式匹配
- [LeetCode] 523. 连续的子数组和 ☆☆☆(动态规划)
- [LeetCode] 19. 删除链表的倒数第N个节点 ☆☆☆
- leetcode 15. 三数之和 js实现
- LeetCode之LRU Cache 最近最少使用算法 缓存设计
- 005-spring cache-原理、缓存AOP机制、Spring Cache抽象集成机制、springboot自动配置机制
- 【Leetcode刷题Python】113. 路径总和 II