AM/FB 134. LRU Cache

least recent usage cache 

缘起：

hash可以实现get和set的O(1)操作，但是如何实现least recent，

也就是需要移动元素，把每次get或set的元素移动到一个地方，也就是

按就近使用排列，最早使用的要在超过cap后去掉。

实现移动的O(1)操作就是要借助doubly linked list。

步骤：

1，建立doubly linked list，里面存放key和value信息。用于实现移动。

2，hash map, key 到 linked list node的映射。用于实现查找。

3，每次get，把key 对应的node移到开头，返回key对应node中的value值。

4，每次set，是否key在hash中？是，更新value，把key对应node移到开头；

                                                     否，在hash和doubly list中添加新元素，

                                                     如超过cap，去掉tail处，同时对应去掉hash中key。

注意和出错点：

1，这种hash和其他数据结构一起使用时，一定要在添加和删除元素时，同时对

hash和其他数据结构一起操作。

2，linked list node里没有存key信息，导致去掉tail处节点时，无法得到hash中

应该删除的key值。

Code(Language:C++) (Judger:ip-172-31-5-19)

class node{
public:    
    node *left, *right; 
    int val, key; 
    node(int val, int key){
        this->val = val; 
        this->key = key; 
        this->left = NULL; 
        this->right = NULL; 
    }
};
class LRUCache {
public:
    /*
    * @param capacity: An integer
    */
    int cap; 
    unordered_map<int, node*> hmap;
    int cnt; 
    node *head; 
    node *tail; 
    LRUCache(int capacity) {
        // do intialization if necessary
        cap = capacity;
        cnt = 0; 
        head = new node(0, 0);
        tail = new node(0, 0);
        head->right = tail; 
        tail->left = head; 
    }

    /*
     * @param key: An integer
     * @return: An integer
     */
    int get(int key) {
        // write your code here
        if(hmap.count(key)){
            //先把hmap[k]地方断开（建立新的连接）
            node *valNode = hmap[key];
            node* right = valNode->right; 
            valNode->left->right = right;
            right->left = valNode->left; 
            // 把hmap[k] node放到开头
            moveToHead(valNode); 
            return valNode->val; 
        }
        return -1; 
    }
    
    void moveToHead(node* nd){
        node* right1 = head->right; 
        head->right = nd; 
        nd->right = right1; 
        nd->left = head; 
        right1->left = nd; 
        return; 
    }

    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    void set(int key, int value) {
        // write your code here
        if(hmap.find(key) != hmap.end()){
           hmap[key]->val = value; 
           //不要忘记先把hmap[key]地方断开。
            node *valNode = hmap[key];
            node* right = valNode->right; 
            valNode->left->right = right;
            right->left = valNode->left; 
           //移到开头
           moveToHead(hmap[key]);
        }
        else{
            node *add = new node(value, key);
            hmap[key] = add; 
            moveToHead(add); 
            cnt++; 
            if(cnt > cap){
                //去掉尾巴
                //node *tmp = tail->left; 
                //node *pre = tail->left->left; 
                //pre->right = tail; 
                //tail->left = pre; 
                //更简洁的写法
                hmap.erase(tail->left->key);
                tail->left->left->right = tail; 
                tail->left = tail->left->left; 
                cnt = cap; 
            
            }
        }
        return; 
    }
};