146. LRU缓存机制

[linqibin]

原题目描述有问题，修改了一下

运用你所掌握的数据结构，设计和实现一个 LRU (最久未使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。若存在，则更新value值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

思路：需要在满的时候删除最久未使用。利用数组，每次PUT和GET时，把元素放在数组最前面，这样数组最后一个元素必定是最久未被使用的。当满的时候就删除最后一个元素。
附加题说要O(1)复杂度。因此不能用数组，要改成双向链表，这样就可以不遍历修改指定元素位置。再使用Map，存key与元素，就可以凭key取出元素，然后进行移除/移位操作。
不想实现双向链表，只用数组+Map意思意思好了。

/**
 * @param {number} capacity
 */
function LRUCache(capacity) {
    this.capacity = capacity;
    this.list = [];
    this.map = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    let value = this.map.get(key);
    
    if(!value) return -1

    this.moveToHead(key);
    return value;
};

LRUCache.prototype.moveToHead = function(key){
    const list = this.list;

    for(var i = 0; i < list.length; i++){
        if(list[i] == key) break;
    }

    list.unshift(list.splice(i,1)[0]);
}

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {

    if(this.map.has(key)) {
        this.map.set(key, value);
        this.moveToHead(key);
        return;
    };
    
    if(this.list.length < this.capacity) return put(this.list, this.map);

    let k = this.list.pop();
    this.map.delete(k);

    put(this.list, this.map);
    
    function put(list, map){
        list.unshift(key);
        map.set(key, value);
    }
    
};
    
/** 
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */