Least Recent Used Cache

用意

每次要重新熟悉或者学习一个新语言，我都会重新重新做一下这道题。因为这道题需要自己对语言如何自定义对象以及各种collection有一定的了解。 Leetcode link

C++ 解法

解法一： 构造一个tuple 用于保存在linkedlist里面，这种解法需要熟悉splice用法，我这里也用了emplace 相当于用了右值构造提速，避免反复创建销毁对象造成的额外开销。

static const auto s = [](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

class LRUCache {
private:
    typedef pair<int, int> Tuple; // <key, value>
    typedef list< Tuple > List;
    typedef unordered_map< int, List::iterator > HashMap;
    int capacity;
    List dbList;
    HashMap dbMap;
    // touch helps update it posisition 
    void touch(HashMap::iterator it){
        auto listIt = it->second;
        int key = listIt->first;
        int value = listIt->second;
        // Implementation 1
        dbList.splice(dbList.begin(), dbList, listIt);
    }
    
public:
    LRUCache(int capacity): capacity(capacity) {
        
    }
    
    int get(int key) {
        auto record = dbMap.find(key);
        if (record == dbMap.end()){
            return -1;
        }
        touch(record);
        return record->second->second;
    }
    
    void put(int key, int value) {
        auto record = dbMap.find(key);
        if (record != dbMap.end()){
            // just need to update
            touch(record);
            record->second->second = value;
            return;
        }
        
        if (dbMap.size() == capacity){
            // need to purge first 
            auto tuple = dbList.back();
            dbMap.erase(tuple.first);
            dbList.pop_back();
        }
        
        dbList.emplace_front(Tuple(key, value));
        dbMap[key] = dbList.begin();
        return;
    }
};

解法二： 也是用了tuple（pair），不过这里是map里存的对象，tuple first 为 key， tuple second 为对应list里的iterator。我个人其实觉得第一种解法更加好理解。

static const auto s = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

class LRUCache {
private:
    typedef list<int> List;
    typedef pair<int, List::iterator> Tuple;
    typedef unordered_map<int, Tuple> Cache;
    
    Cache dbMap;
    List dbList;
    int capacity;
    void moveToFront(Cache::iterator it){
        // update list 
        int key = it->first;
        dbList.erase(it->second.second);
        dbList.push_front(key);
        // update location
        it->second.second = dbList.begin();
        return;
    }
public:
    LRUCache(int capacity): capacity(capacity) {
        
    }
    
    int get(int key) {
        auto record = dbMap.find(key);
        if (record == dbMap.end()){
            return -1;
        }
        
        moveToFront(record);
        
        return record->second.first;
    }
    
    void put(int key, int value) {
        auto record = dbMap.find(key);
        if (record != dbMap.end()){
            // we just need to update
            moveToFront(record);
            // Implementation 1:
            record->second.first = value;
            // Implementation 2:
            // dbMap[key] = { value, dbList.begin() };
            return;
        } 
        
        if (dbMap.size() == capacity){
            // need to remove first 
            dbMap.erase(dbList.back());
            dbList.pop_back();
        }
        
        dbList.push_front(key);
        dbMap[key] = { value, dbList.begin() };
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

Go 解法

Golang需要使用container/list 这个库，一般人也不会去碰吧。

type LRUCache struct {
    dbMap map[int]*list.Element
    dbList *list.List
    capacity int
}

type tuple struct{
    key int
    value int
}


func Constructor(capacity int) LRUCache {
    return LRUCache{
        dbMap: make(map[int]*list.Element),
        dbList: list.New(),
        capacity: capacity,
    }
}


func (this *LRUCache) Get(key int) int {
    var ele *list.Element
    var ok bool
    if ele, ok = this.dbMap[key]; !ok{
        return -1
    }
    
    this.dbList.MoveToFront(ele)
    
    res := ele.Value.(tuple)
    return res.value
}


func (this *LRUCache) Put(key int, value int)  {
    var ele *list.Element
    var ok bool
    
    t := tuple{key: key, value: value}
    
    if ele, ok = this.dbMap[key]; ok{    
        // ele is in map
        ele.Value = t
        this.dbList.MoveToFront(ele)
        
        return
    }
    
    ele = this.dbList.PushFront(t)
    this.dbMap[key] = ele
    if this.dbList.Len() > this.capacity{
        removeEle := this.dbList.Back()
        this.dbList.Remove(removeEle)
        t := removeEle.Value.(tuple)
        delete(this.dbMap, t.key)
    }
    return 
}