LeetCode LRU Cache

 1 class LRUCache{
 2 private:
 3     int max_size;
 4     unordered_map<int, list<pair<int, int> >::iterator> hash;
 5     list<pair<int, int> > lru_stack;
 6 public:
 7     LRUCache(int capacity) {
 8         if (capacity < 1) capacity = 0;
 9         max_size = capacity;
10     }
11 
12     int get(int key) {
13         unordered_map<int, list<pair<int, int> >::iterator>::iterator miter = hash.find(key);
14         list<pair<int, int> >::iterator liter;
15         if (miter == hash.end()) {
16             return -1;
17         } else {
18             liter = miter->second;
19             int val = liter->second;
20             lru_stack.erase(liter);
21             miter->second = liter = lru_stack.insert(lru_stack.begin(), make_pair(key, val));
22             return liter->second;
23         }
24     }
25 
26     void set(int key, int value) {
27         if (max_size == 0) return;
28         unordered_map<int, list<pair<int, int> >::iterator>::iterator miter = hash.find(key);
29         list<pair<int, int> >::iterator liter;
30         if (miter == hash.end()) {   // key not exists in the cache
31             if (hash.size() == max_size) {
32                 // invalidate LRU item to avoid overflow
33                 hash.erase(lru_stack.back().first);
34                 lru_stack.pop_back();
35             }
36             liter = lru_stack.insert(lru_stack.begin(), make_pair(key, value));
37             hash.insert(make_pair(key, liter));
38         } else {    // key already exists, so replace the value with new one
39             liter = miter->second;
40             lru_stack.erase(liter);
41             miter->second = lru_stack.insert(lru_stack.begin(), make_pair(key, value));
42         }
43     }
44 };

用一个链表来维护LRU关系，map来做hash，用了std库，如果纯粹自己手工写可能会花多点时间

第二轮:

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.

最近在看Java集合发现LinkedHashMap自带LRU模式即使用LinkedHashMap(initialCapacity, loadFactor, accessOrder)构造函数指定accessOrder = true即使用访问顺序。不过本质上还是使用了hashmap加链表的形式来实现LRU过程。

import java.util.*;
public class LRUCache {
    private Map<Integer, Integer> storage;
    private int capacity;
    public LRUCache(int capacity) {
        storage = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true);
    
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Integer value = storage.get(key);
        if (value == null) {
            return -1;
        }
        return value;
    }
    
    public void set(int key, int value) {
        boolean hasin = storage.keySet().contains(key);
        
        if (!hasin && capacity <= storage.size()) {
            Iterator<Map.Entry<Integer, Integer> > iter = storage.entrySet().iterator();
            Map.Entry<Integer, Integer> first = iter.next();
            storage.remove(first.getKey());
        }
        storage.put(key, value);
    }
}