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](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
leetcode LRU缓存 Java 中最近最少使用 (LRU) 缓存。 测试 mvn test ------------------------------------------------------- T E S T S ------------------------------------------------------- Running ...