146. LRU Cache -------M !!!!!!!!!!!

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

A:

------------------用doubly-linked list做更新 + HashMap 来做cache---------

class LRUCache {
public:
    LRUCache(int capacity) {        
        cap = capacity;
        header = new Node(0,0);
        tail = new Node(0,0);
        header->next = tail;
        tail->pre = header;
    }
    
    int get(int key) {
        if(map.find(key)==map.end()){
            return -1;
        }
        Node* tmp = map[key];
        detachAndPutBegin(tmp);
        return tmp->val;
    }
    
    void put(int key, int value) {
        Node * tmp;
        if(map.find(key) == map.end()){
            tmp = new Node(key, value);
            if(map.size()==cap){
                auto delNode = tail->pre;
                delNode->pre->next = tail;
                tail->pre = delNode->pre;
                map.erase(delNode->key);
                delete(delNode);
            }
            map.insert({key, tmp});
            // insert at the begining of the list
            detachAndPutBegin(tmp);
        }else{
            map[key]->val = value;
            tmp = map[key];
            detachAndPutBegin(tmp);
        }
    }
private:    
    struct Node{
        int key, val; // need key to point back to delete the last Node* from map
        Node *pre, *next;
        Node(int key, int v):key(key), val(v), pre(NULL),next(NULL){}
    };
    Node *header, *tail;
    int cap =0;
    unordered_map<int,Node*> map;
    
    int detachAndPutBegin(Node * tmp){
        if(tmp->next){ // if in the list
            tmp->pre->next = tmp->next;
            tmp->next->pre = tmp->pre;
        }        
        // insert into the beginning of the list
        tmp->next = header->next;
        tmp->pre = header;
        header->next->pre = tmp;
        header->next = tmp;
        return tmp->val;
    }
};

/**
 * 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);
 */

Mistakes：
1：刚开始 删除list的时候，是在Dlist中做的。  可是，还需要把HashMap里的也删掉。

2：   考虑到要在Map中删除节点， 可是，Map只能按照Key 来删。
而我们在ListNode中，每次要删的是最后一个Node，  因此，我们需要在Node中保存每个点的key 值。

还有一个trick 就是double linked list 的前后都加了dummy 节点。这样就不需要处理边界情况。