146. LRU Cache

问题:

设计类LRUCache,实现LRU Cache

Least Recently Used

优先度为:最近使用优先 的缓存。

  • 缓存大小一定,capacity
  • get(key):通过key查找value,若缓存中不存在key,返回-1
  • put(key, value):插入缓存key=value。
Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4
 

Constraints:

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 10^4
At most 3 * 10^4 calls will be made to get and put.

  

解法:LRU

c++中 利用 list 和 unordered_map 来实现:

  • cache:list:存储cache链表。
  • kl:unordered_map:存储对应key在list中的位置,方便直接访问。
  • kv:另:为了存储value,追加unordered_map保存key:value对应关系。

那么,对于cache,我们有以下两个基本操作:

  • 追加key:value对
    • update(key, value)【假设,此操作cache已经不超过最大容量】
      • 若key存在于cache中
        • 在list中找到key(定位:kl[key]),将key从list中删除:list.erase(kl[key])
        • 1. 重新加到list头:list.push_front(key),更新key在list中的位置:kl[key]=list.begin()
        • 2. 更新 kv[key]=value
      • 若key不存在于cache中
        • 1. 将key加到list头:list.push_front(key),更新key在list中的位置:kl[key]=list.begin()
        • 2. 更新 kv[key]=value
  • 删除最老的元素(当size超出cache容量)
    • outlast():last = list.back()
      • kl.erase(last)
      • kv.erase(last)
      • list.pop_back()

再看题目所求:

  • get(key):
    • update(key)
    • return kv[key]
  • put(key, value)
    • 若cache==最大容量:删除最老元素:outlast()
    • 此时,cache一定不超过最大容量:再进行:update(key, value)

 

代码参考:

 1 class LRUCache {
 2 public:
 3     LRUCache(int capacity) {
 4         size = capacity;
 5     }
 6     
 7     int get(int key) {
 8         if(kv.count(key)) {
 9             update(key);
10             return kv[key];
11         }
12         return -1;
13     }
14     
15     void put(int key, int value) {
16         if(!kv.count(key) && cache.size()==size) {
17             outlast();
18         }
19         update(key);
20         kv[key] = value;
21         return;
22     }
23 private:
24     list<int> cache;//key
25     unordered_map<int, list<int>::iterator> kl;//key->list
26     unordered_map<int, int> kv;//key->value
27     int size;
28     void update(int key) {
29         if(kv.count(key)) {
30             cache.erase(kl[key]);
31         }
32         cache.push_front(key);
33         kl[key] = cache.begin();
34     }
35     void outlast() {
36         auto last = cache.back();
37         kv.erase(last);
38         kl.erase(last);
39         cache.pop_back();
40     }
41 };
42 
43 /**
44  * Your LRUCache object will be instantiated and called as such:
45  * LRUCache* obj = new LRUCache(capacity);
46  * int param_1 = obj->get(key);
47  * obj->put(key,value);
48  */

 

上一篇:LRU缓存结构


下一篇:Lru cache不会写?看看Mybatis