首页 > 代码库 > Leetcode LRU Cache
Leetcode 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.
LRU是近期最少使用算法，其一个例子为：
假设 序列为 4 3 4 2 3 1 4 2
物理块有3个 则
首轮 4调入内存 4
次轮 3调入内存 3 4
之后 4调入内存 4 3
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）
之后 4调入内存 4 1 3（原理同上）
最后 2调入内存 2 4 1
对于
set(key, value) ，如果不存在该cache
如果cache已经达到了它的容量，则把最近最少使用的cache删除，然后插入新的cache
否则直接插入新的cache
如果存在该cache
将该cache移动到前面，表示刚被使用
对于get(key)，
如果不存在该cache，则返回-1
否则将该cache移动到前面，表示刚被使用
由于涉及到查找，由于hash_map的查找时间复杂度为O(1)，故考虑用hash_map
由于涉及到插入和删除，由于链表的插入删除时间复杂度为O(1)，故考虑用list
故将hash_map和list相结合
class LRUCache{public: typedef pair<int,int> CacheItem; typedef list<CacheIterm>::iterator CacheItemIterator; typedef unordered_map<int,list<CacheItem>::iterator > CacheMap; typedef CacheMap::iterator CacheMapIterator; LRUCache(int capacity){ m_capacity = capacity; } int get(int key){ if(m_map.find(key) == m_map.end()) return -1; else{ moveToFirst(key); return m_map[key]->second; } } void set(int key, int value){ if(m_map.find(key) == m_map.end()){ if(m_cache.size() >= m_capacity){ m_map.erase(m_cache.back().first); m_cache.pop_back(); } m_cache.push_front(CacheItem(key,value)); m_map[key]=m_cache.begin(); }else{ m_map[key]->second = value; moveToFirst(key); } } void moveToFirst(int key){ CacheItemIterator itemIter = cacheMap[key]; m_cache.erase(itemIter); m_cache.push_front(*itemIter); m_map[key] = m_cache.begin(); } private: int m_capacity; CacheMap m_map; list<CacheItem> m_cache; };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。