【Q093】如何实现一个 LRU

[shfshanyue]

No description provided.

[manyyuri]

leetcode149

1. 用双向链表+哈希。

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.cache = new DoubleList();
};
class Node {
    constructor(k, val) {
        this.k = k;
        this.val = val;
        this.pre = null;
        this.next = null;
    }
}
class DoubleList {
    constructor() {
        this.size = 0;
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.pre = this.head;
    }
    addLast(x) {
        const { head, tail } = this;
        x.pre = tail.pre;
        x.next = tail;
        tail.pre.next = x;
        tail.pre = x;
        this.size++;
    }
    remove(x) {
        x.pre.next = x.next;
        x.next.pre = x.pre;
        this.size--;
    }
    removeFirst() {
        const { head, tail } = this;
        if (head.next === tail) return null;
        let first = head.next;
        this.remove(first);
        return first;
    }
}

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    const { cache, map } = this;
    if (map.has(key)) {
        let x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
        return map.get(key).val;
    } else {
        return -1;
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    const { cache, map,size } = this;
    const addRecently = function(key,value){
        let x = new Node(key,value);
        cache.addLast(x);
        map.set(key,x);
    }
    if (map.has(key)) {
        let x = map.get(key);
        cache.remove(x);
        map.delete(key);
        addRecently(key,value);
    }else{
        if(cache.size=== this.capacity){
            let x = cache.removeFirst();
            map.delete(x.k);
        }
        addRecently(key,value);
    }
};

2. Map的巧妙使用
   map放入数据是按顺序的，最新放入的数据在迭代器最后
   而且map的entries方法，还有keys方法，会返回一个迭代器，迭代器调用next也是顺序返回，所以返回第一个的值就是最老的，找到并删除即可

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

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    const map = this.map;
    let val = map.get(key);
    if (val !== undefined) {
        map.delete(key);
        map.set(key, val);
        return val;
    } else {
        return -1;
    }

};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    const { map, capacity } = this
    if (map.has(key)) map.delete(key);
    map.set(key, value);
    if (map.size > capacity) {
        map.delete(map.entries().next().value[0])
    }
};