LRU算法

[WanderHuang]

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.cap = capacity;
    // 缓存节点信息
    this.map = new Map();
    this.len = 0;

    this.head = new Node(0, 0);
    this.tail = new Node(0,0);
    this.head.next = this.tail;
    this.tail.prev = this.head;

    // node 插入尾部
    this.insertLast = function (node) {
        if (this.len === this.cap) {
            this.unshiftFirst();
        }
        node.prev = this.tail.prev;
        node.next = this.tail;
        this.tail.prev.next = node;
        this.tail.prev = node;

        // 添加进map
        this.map.set(node.key, node);
        this.len++
    }

    this.unshiftFirst = function () {
        if (this.head.next !== this.tail) {
            let node = this.head.next;
            this.head.next = node.next;
            node.next.prev = this.head;

            if (this.map.has(node.key)) {
                this.map.delete(node.key)
            }
            this.len--


            return node
        }
    }

    this.remove = function (node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        
        this.len--;
        this.map.delete(node.key)
    }
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (this.map.has(key)) {
        let node = this.map.get(key);
        this.remove(node)
        this.insertLast(node);

        return node.val
    }
    return -1;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    let node;
    if (this.map.has(key)) {
        node = this.map.get(key);
        node.val = value;
        this.remove(node);
        
    } else {
        node = new Node(key, value)
    }

    this.insertLast(node);
};

function Node(key, val) {
    this.key = key;
    this.val = val;

    this.prev = null;
    this.next = null;
}

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

[WanderHuang]

LRU缓存

1. 每次被使用时，数据成为最新的数据
2. 容量满了时，淘汰最久未被使用的数据
3. 新增的数据为最新
4. 每次被get到的数据也是最新

我们先考究一下操作

1. Constructor(capacity)。构造函数，允许设置缓存容量。
2. put(key, value)。放入数据，若存在，则更新value值
3. get(key)。获取数据

如果我们维护一个数组。则涉及到数组的几个操作

1. 查找。get或者put时，要根据key值查找到对应的value，数组的查找O(n)
2. 删除。如果容量满了，会有删除操作O(n)

所以单纯的用数组也不行。那我用一个额外的空间缓存数据呢(空间换时间)？

用一个map来记录每个key对应数组的index

那么每次put和get的时候也更新一下map。
这个方法挺不错的，查找的时间效率可以降为O(1)。但是删除还是那么慢O(n)，因为数组的特性，这里就要考虑换一下数据结构了。

链表的查找为O(n) 删除为O(1)
因为上面我们讲了，如果用一个map来存当前操作到的一些状态，那么可以把查询的时间降低，那么这个方法是否也适用于链表呢？

是的

比如我们在map中已经有(key, node)。在put的时候，就可以快速定位到一个node。因此这里我们的map需要存node信息。
但是又有另外一个麻烦。

单链表删除，已知链表和node，还是得遍历一次链表

因此，我们需要用双链表，因为双链表中的node保存了前后信息，删除时不需要遍历整个链表，真正的又快又好。

至此，我们利用一个map存储每个活动节点，把遍历操作改为了查map的操作，同时，由于map内存储的节点是双向指针，那么不管是增加和删除，时间复杂度都是O(1)

而对于map而言，set、has、get操作都是O(1)，因此整体结果

• 时间复杂度 O(1) -> get、put
• 空间复杂度 O(n) -> get、put

[holyliao]

厉害了，大佬

[holyliao]

leetcode 460