146. LRU Cache

這題我一直都把他放著, 因為我在想我先不要寫系統實作題

但還是手癢, 因為他在高頻題的前幾題,

lru cache 的功用網上可以查得到, 這邊題目是希望get跟put都可以縮到O(1)的時間

不要O(1)我還有辦法做出來, 看到解答也是覺得蠻難的

這裡最重要的兩個概念用c++要會的兩個東西

1. list
2. splice 

平時我們在做題目幾乎都用vector, 就算要linkedlist的也都會提供struct 我們可以直接使用

這邊得要用到stl的list, 原因也是為了後面的splice

splice(拼接要看一下)http://www.cplusplus.com/reference/list/list/splice/

因為在這題的解法常常會有自己插自己, 常常搞不清楚要怎麼用

另外就是要用hashmap來紀錄list的pointer, 沒錯, 是pointer, 所以也格外複雜一點

get的方式是先找有無key, 沒有就返回-1, 有的話就把他在list的位置拼接到最前面去,

put首先先看有沒有值重複了, 有的話就把value給換掉就行了, 一樣在cache的位置也是要拼到最前面去

倘若cache滿了, 找到最後面一位, 把他從hashmap移除, 並且從list移走

最後就是從front加入即可, 雖然簡單但不熟list跟splice 很容易卡關

class LRUCache {
  public:
    LRUCache(int capacity) {
      capacity_ = capacity;
    }
int get(int key) {
      auto it = m.find(key);
      if(it == m.end()) return -1;
cache_.splice(cache_.begin(), cache_, it->second);
      return it->second->second;
    }
void put(int key, int value) {
        auto it = m.find(key);
        if(it != m.end()){
          // update value
          it->second->second = value;
          cache_.splice(cache_.begin(), cache_, it->second);
          return;
        }
        if(cache_.size() == capacity_){
          auto &node = cache_.back();
          m.erase(node.first);
          cache_.pop_back();
        }
        cache_.push_front({key, value});
        m[key] = cache_.begin();
    }
  private:
    int capacity_;
    list<pair<int, int>> cache_;
    unordered_map<int, list<pair<int, int>>::iterator > m;
};