首页 > 代码库 > LeetCode: LRU Cache
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.
地址：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 };