LRU cache

LRU cache

Most interesting thing in leetcode

Design the lru cache algorithm. Three parts of this.

• `LRUcaache` Init the cache with the capacity.
• `get` Get the value if the key is legl.
• `set` If there is enough space, set the key with its value, else find out the lest recently used page and set the key and value.

Solution

This problem actully is asking me to create a data structure with high performance. And there are two operations in this data structure. One of them is find, we can resolve this using hashmap easily with the time complexity of O(1). The other is edit, which seems little harderto find a good way to kep the time complexity O(1). We can use a list to finish this job. When a element is visited or edited, we put it in the front of the list. As a result, the last one of the list must be the least recently used item. And we use our hashmap to save each key's position in list. The problem is resolved.

Mistakes

• Do not forget to put the element to right position when you applying the `get` function.
• `set` is not so easy to code, need think little more carefully.
• `vector`may not good enough to use, `list` is better.

Code

``````1 struct Node {
2     int key;
3     int val;
4     Node( int _key, int _val ) : key(_key), val(_val){}
5 };``````
`````` 1 class LRUCache {
2 private:
3     int size;
4     list <Node> cache;
5     map <int, list<Node> :: iterator > cacheMap;
6 public:
7     LRUCache( int capacity ) {
8         cacheMap.clear();
9         cache.clear();
10         size = capacity;
11     }
12
13     int get(int key) {
14         if ( cacheMap.find(key) == cacheMap.end() ) {
15             return -1;
16         }
17         auto i = cacheMap[key];
18         int val = i->val;
19         cache.erase(i);
20         cache.push_front(Node(key,val));
21         cacheMap[key] = cache.begin();
22         return val;
23     }
24
25     void set(int key, int value) {
26         if ( cacheMap.find(key) == cacheMap.end() ) {
27             if ( cacheMap.size() == size ) {
28                 cacheMap.erase(cache.back().key);
29                 cache.pop_back();
30             }
31             cache.push_front(Node(key,value));
32             cacheMap[key] = cache.begin();
33         } else {
34             auto i = cacheMap[key];
35             cache.erase(i);
36             cache.push_front(Node(key,value));
37             cacheMap[key] = cache.begin();
38         }
39     }
40
41
42 };``````