注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex46 LRU Cache  

2015-05-31 17:51:56|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.

我开始想的用数组来保存,不过貌似出现重复的元素的话就不容易搜索,网上思路是用的双端链表,删除的话,用一个map保存地址,这样删除就特别方便。剩下的就只是操作链表的头,删除链表的尾的问题了。
具体过程是这样的
来一个value,先判定他在不在cache里面,如果在的话,移动到头
如果不在,先判定链表满了没满
                   如果满了,删掉最后一个,将当前来的放到头
                   如果没有满,不用删除,直接放在头部

参考的百草园的代码,不过楼主的代码貌似有问题,改了一下就能过了,貌似是mlist的删除有问题。

class LRUCache{
private:
list<pair<int, int>> mlist; //双向链表
unordered_map<int, list<pair<int, int>>::iterator> mmap;
//通过元素映射到链表
int mcapacity;

public:
LRUCache(int capacity) {
mlist.clear();
mmap.clear();
mcapacity = capacity;
}

int get(int key) {
if (mmap.find(key) != mmap.end())
{
pair<int, int> tmp = *(mmap[key]);
mlist.splice(mlist.begin(), mlist, mmap[key]);
mmap[key] = mlist.begin();

return mlist.front().second;
}
else
{
return -1;
}
}

void set(int key, int value)
{

if (mmap.find(key) != mmap.end())
{
//设置的时候如果找到,原来的就删掉,直接把数据放在链表的头
//mlist.erase(mmap[key]);
//mlist.push_front(make_pair(key, value));
mlist.splice(mlist.begin(), mlist, mmap[key]);
mmap[key] = mlist.begin();
mlist.begin()->second = value;
}
else
{
//设置的时候如果没找到,需要判定链表的容量是否还够
//如果满了的话,先删除醉虎一个,然后再把这个key放到头上
//如果没有满的话,直接把这个key放在头
if (mlist.size() == mcapacity)
{
mmap.erase(mlist.back().first);
mlist.pop_back();
}
mlist.push_front(make_pair(key, value));
mmap[key] = mlist.begin();
}
}
};

有大神自己写双端链表操作,呵呵了,我就不恶心自己了
参考
http://www.cnblogs.com/easonliu/p/3651802.html
http://blog.csdn.net/ygrx/article/details/11105755
http://blog.csdn.net/doufei_ccst/article/details/23094987
http://www.cnblogs.com/x1957/p/3485053.html
  评论这张
 
阅读(19)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017