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.
  • vectormay 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 };

Loading Disqus comments...
Table of Contents