Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:get
andset
.
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.
五星级难度的题目。
这里的get和set操作都要求时间复杂度为O(1)。
思考了好久才想到要用一个双向链表数据结构来保存优先级列表,代表这里的LRU Cache。这个是本题的关键。
如果使用其他方法,例如堆操作,好像最多能使得get或者set其中一个是O(1),一个需要O(lgn),会超时。
因为这里需要利用key快速定位value,要频繁修改优先级,即也要利用key快速定位优先级,并能修改优先级。原来要考指针的熟练使用。
关键点:
1 建立一个新数据结构:双向链表,包含数据key和value
2 使用一个map,可以快速定位这个数据结构节点,这样可以快速得到value和修改节点指针
3 保存好头指针和尾指针,代表优先级最高和最低的节点
struct LRUstruct
{
int value;
int key;
LRUstruct *pre;
LRUstruct *next;
LRUstruct(int v=0,int k=0, LRUstruct *p=NULL, LRUstruct *n=NULL)
:value(v), key(k), pre(p), next(n){}
};
struct HeadTail
{
LRUstruct head;
LRUstruct tail;
HeadTail(LRUstruct h, LRUstruct t):head(h), tail(t){}
};
class LRUCache{
public:
int size;
unordered_map<int, LRUstruct *> keyMap;
HeadTail ht;
LRUCache(int capacity):ht(LRUstruct(),LRUstruct())
{
size = capacity;
}
int get(int key)
{
if (keyMap.empty() || !keyMap.count(key)) return -1;
LRUstruct *ls = keyMap[key];
//拆除ls
ls->pre->next = ls->next;
ls->next->pre = ls->pre;
insertTail(ls);
return ls->value;
}
void set(int key, int value)
{
if (keyMap.empty())
{
LRUstruct *ls = new LRUstruct(value, key);
ht.head.next = ls;
ls->pre = &ht.head;
ht.tail.pre = ls;
ls->next = &ht.tail;
keyMap[key] = ls;
return;
}
if (keyMap.count(key))
{
LRUstruct *ls = keyMap[key];
ls->value = value;
//拆除ls
ls->pre->next = ls->next;
ls->next->pre = ls->pre;
insertTail(ls);
}
else
{
if (keyMap.size() < size)
{
LRUstruct *ls = new LRUstruct(value, key);
//插入后面
insertTail(ls);
//更新map表
keyMap[key] = ls;
}
else
{
LRUstruct *p_tmp = ht.head.next;
keyMap.erase(p_tmp->key);
deleteHead();
LRUstruct *ls = new LRUstruct(value, key);
insertTail(ls);
keyMap[key] = ls;
delete p_tmp;
}
}
}
void insertTail(LRUstruct *ls)
{
ls->pre = ht.tail.pre;
ht.tail.pre->next = ls;
ls->next = &ht.tail;
ht.tail.pre = ls;
}
void deleteHead()
{
ht.head.next = ht.head.next->next;
ht.head.next->pre = &ht.head;
}
};
曾经令人望而却步的题目,征服她!
更新:
使用环形双链表数据结构的精炼的代码:
转载注明出处:http://blog.csdn.net/kenden23/article/details/18693921
//2014-2-20 update
struct douLink
{
int key;
int val;
douLink *pre;
douLink *post;
douLink(int k, int v):key(k), val(v){}
};
class LRUCache{
public:
//2014-2-20 update
douLink head_tail;
unordered_map<int, douLink *> key_to_nodes;
int size;
LRUCache(int capacity):head_tail(0, 0)
{
size = capacity;
head_tail.pre = head_tail.post = &head_tail;
}
int get(int key)
{
if (!key_to_nodes.count(key)) return -1;
douLink *t = key_to_nodes[key];
unchainNode(t);
insertHead(t);
return t->val;
}
void set(int key, int value)
{
if (!key_to_nodes.count(key))
{
if (key_to_nodes.size() >= size)
{
douLink *t = head_tail.pre;
unchainNode(t);
key_to_nodes.erase(t->key);
delete t;
}
douLink *p = new douLink(key, value);
insertHead(p);
key_to_nodes[key] = p;
}
else
{
douLink *t = key_to_nodes[key];
t->val = value;
unchainNode(t);
insertHead(t);
}
}
void insertHead(douLink *&p)//构成一个环形双链表数据结构
{
p->post = head_tail.post;
head_tail.post = p;
p->pre = &head_tail;
p->post->pre = p;//不用考虑单个head_tail的情况了!!!环形双链表数据结构更方便!
}
void unchainNode(douLink *&t)
{
t->pre->post = t->post;
t->post->pre = t->pre;
}
};
分享到:
相关推荐
Cache in Java 我很喜欢这个问题。 我在康奈尔大学的第一个 CS 课程涉及队列和其他数据结构。 对于其中一个课堂项目,我们必须开发基于队列的模拟。 在工作中,我开发了广泛的队列库。 我能说什么; 我喜欢队列和...
leetcode LRU Cache Algorithm (LRU缓存算法) C++版本,适用于 ##LRU算法介绍 引自: Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is ...
lru缓存leetcode 问题描述 设计一个遵循最近最少使用 (LRU) 缓存约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity)使用正大小容量初始化 LRU 缓存。 int get(int key)如果键存在则返回键的值,否则返回-1...
LRU_cache (Leetcode 146) 设计和实现最近最少使用 (LRU) 缓存的数据结构。 它应该支持以下操作:get 和 set。 get(key) – 如果键存在于缓存中,则获取键的值(将始终为正),否则返回 -1。 set(key, value) – ...
lru缓存leetcode LRU_Cache LRU_Cache 是一个 leetcode 问题,需要深入了解数据结构。 在 LRU_Cache 的实现中,使用了 LinkedHashTable。
lru缓存leetcode LRU_Cache 灵感来自 LeetCode OJ:
lru缓存leetcode LRU缓存 受启发的简单 LRU 缓存实现 发展 建造 ./gradlew build 测试 ./gradlew test 使用示例 LRUCache< String , String > cache = new LRUCache<> ( 2 /* capacity */ ); cache . put( " ...
Leetcode-LRU-cache LRU缓存 设计和实现最近最少使用 (LRU) 缓存的数据结构。 它应该支持以下操作:get 和 put。 get(key) - 如果键存在于缓存中,则获取键的值(将始终为正),否则返回 -1。 put(key, value) - ...
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) – Get the value (will always be positive) of the key if ...
LeetCode_LRU_Cache 问题: 最近最少使用的缓存 目标是设计一种称为最近最少使用 (LRU) 缓存的数据结构。 LRU 缓存是一种缓存类型,当缓存内存达到其限制时,我们会删除最近最少使用的条目。 对于当前问题,将 get ...
lru leetcode LRU缓存的实现 LRU - 最近最少使用。 完成清单: C C++ 去 JAVA(进行中) C 实现是完整的,并通过 Leetcode 上的 LRU 缓存问题进行了检查。 (C 实现是为了重新熟悉 C 并“回归基础”) C++ 中的实现...
lru 隐藏 leetcode lru缓存
lru缓存leetcode lru_cache_example 在 Python 中使用 lru_cache 的非常简单的代码片段(供我参考)。 如何使用Python中提供的。 它允许将递归函数“转换”为 DP 方法(使用记忆化)。 示例代码解决了 Leetcode 中题...
lru缓存leetcode LRU缓存 看问题- 设计和实现最近最少使用 (LRU) 缓存的数据结构。 它应该支持以下操作:get 和 put。 get(key) - 如果键存在于缓存中,则获取键的值(将始终为正),否则返回 -1。 put(key, value) ...
LRU-Cache 键值对的 LRU 缓存实现。 Leetcode #146。 使用简单的 int32 数据类型的 LRU 缓存实现。 复杂度 O(1)。 空间 O(N)。 数据结构:双链表头尾节点,加上哈希查找表。 对双链表使用抽象。
缓存的英文是cache,最早其实指的是用于CPU和主存数据交互的。早年这块存储被称为高速缓存,最近已经听不到这个词了,不知道是不是淘汰了。因为缓存的读写速度要高于CPU低于主存,所以是用来过渡数据用的。CPU从缓存...
lru缓存leetcode LRU-缓存-实现 C++ 中最近最少使用的缓存实现 此实现支持以下操作:get 和 put get(key) - 如果键存在于缓存中,则获取键的值(将始终为正),否则返回 -1。 put(key, value) - 如果键不存在,则...
leetcode 《算法面试通关 40 讲》挑战 数组、链表 Easy Easy Medium Medium Hard 堆栈、队列 Easy Easy Easy 优先队列 Easy Hard 哈希表 Easy Easy Medium Medium 树、二叉树、二叉搜索树 Medium Easy Medium 递归、...
leetcode LRU缓存 Java 中最近最少使用 (LRU) 缓存。 测试 mvn test ------------------------------------------------------- T E S T S ------------------------------------------------------- Running ...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...