首页 > 其他 > 详细

LeetCode: LRU Cache

时间:2014-07-29 11:43:36      阅读:352      评论:0      收藏:0      [点我收藏+]

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.

地址:https://oj.leetcode.com/problems/lru-cache/

算法:根据题目的意思是让我们模拟LRU算法(最近最常使用算法)。采用一个链表list来表示cache,这样方便删除链表中的任意元素,以及插入头节点元素。另外使用一个map来索引链表中的每一个关键值,这样能够快速的找到链表中关键值相对应的位置。算法实现三个函数:第一个为构造函数,用来设置cache的容量;第二个get函数,用于取得关键值key对应的value值,首先查找cache,如果未找到该key值,返回-1,如果找到该key值,则将该key对应的元素移到链表的头节点,并更新索引值;第三个函数为set函数,用于设置关键值key对应的value值,首先查找cache,如果找到该key值,则设置该key值对应的value值,并把该key值移到链表的头部,并更新索引值,如果没找到且cache容量还未到达最大值,则在链表的头部插入该key值,并且插入该key值对应的索引值,如果没找到且cache容量已经达到最大值,则根据LRU算法原则,删除链表的最后一个节点同时删除其索引值,然后将该key值插入链表头部,并插入索引值。代码:

 1 class LRUCache{
 2 public:
 3     LRUCache(int capacity) {
 4         cap = capacity;
 5     }
 6     
 7     int get(int key) {
 8         map<int,Iter>::iterator it = index_map.find(key);
 9         if(it == index_map.end()){
10             return -1;
11         }
12         Iter p = it->second;
13         int val = it->second->second;
14         cache.push_front(*p);
15         it->second = cache.begin();
16         cache.erase(p);
17         return val;
18     }
19     
20     void set(int key, int value) {
21         map<int,Iter>::iterator it = index_map.find(key);
22         if (it != index_map.end()){
23             cache.push_front(make_pair(key,value));
24             cache.erase(it->second);
25             it->second = cache.begin();
26             return ;
27         }
28         if (cap > cache.size()){
29             cache.push_front(make_pair(key,value));
30             index_map[key] = cache.begin();
31             return ;
32         }
33         index_map.erase(cache.back().first);
34         cache.pop_back();
35         cache.push_front(make_pair(key,value));
36         index_map[key] = cache.begin();
37     }
38     typedef list<pair<int,int> >::iterator Iter;
39     list<pair<int,int> > cache;
40     map<int,Iter> index_map;
41     int cap;
42 };

 

 

LeetCode: LRU Cache,布布扣,bubuko.com

LeetCode: LRU Cache

原文:http://www.cnblogs.com/boostable/p/leetcode_lru_cache.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!