极客时间对于推广渠道会有返利优惠,比如山月在极客时间买了一门课,再把课程分享给好友购买,这时极客时间会向山月返利20元左右。
而我现在做了一个返利平台,你可以在上边通过山月的链接购买课程,此时极客时间会向我返利。为了共同学习,而你可以添加我的微信 (shanyue94),我将把极客时间给我的返利发一个红包全部返给你

# 如何实现一个 LRU

Issue

欢迎在 Issue 中交流与讨论: Issue 94 (opens new window)

Author

回答者: manyyuri (opens new window)

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);
    }
};
  1. 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])
    }
};

关于山月

我的项目:
我的微信:shanyue94,欢迎交流
Last Updated: 5/14/2021, 1:48:53 PM