0460-lfu-cache.js

// https://leetcode.com/problems/lfu-cache/

class ListNode {
    constructor(val, next, prev) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
        this.prev = next === undefined ? null : prev;
    }
}

class LinkedList {
    constructor() {
        this.map = new Map();
        this.Right = new ListNode(null);
        this.Left = new ListNode(null, this.Right);
        this.Right.prev = this.Left;
    }

    len() {
        return this.map.size;
    }

    pop(val) {
        if (this.map.has(val)) {
            let node = this.map.get(val);

            // save
            let prevNode = node.prev;
            // delete
            prevNode.next = node.next;
            prevNode.next.prev = prevNode;
            this.map.delete(val);
        }
    }

    popleft() {
        let data = this.Left.next.val;
        this.Left.next = this.Left.next.next;
        this.Left.next.prev = this.Left;
        this.map.delete(data);
        return data;
    }

    pushRight(val) {
        let newNode = new ListNode(val, this.Right);
        newNode.prev = this.Right.prev;
        newNode.prev.next = newNode;
        this.Right.prev = newNode;
        this.map.set(val, newNode);
    }

    update(val) {
        this.pop(val);
        this.pushRight(val);
    }
}

/**
 * @param {number} capacity
 */
var LFUCache = function (capacity) {
    this.capacity = capacity;
    this.valueMap = new Map();
    this.countMap = new Map();
    this.lftCount = 1;
    this.lists = [];
    this.counter = (key) => {
        let count = this.countMap.get(key) || 0;
        if (this.lists[count]) {
            this.lists[count].pop(key);
        }
        if (!this.lists[count + 1]) {
            this.lists[count + 1] = new LinkedList();
        }
        this.lists[count + 1].pushRight(key);
        this.countMap.set(key, count + 1);
        // console.log(this.lftCount == count, count, this.lists[count].len())
        if (
            this.lftCount == count &&
            this.lists[count] &&
            this.lists[count].len() === 0
        ) {
            this.lftCount++;
        }
    };
};

/**
 * @param {number} key
 * @return {number}
 */
LFUCache.prototype.get = function (key) {
    if (!this.valueMap.has(key)) {
        return -1;
    }

    this.counter(key);
    return this.valueMap.get(key);
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LFUCache.prototype.put = function (key, value) {
    if (!this.valueMap.has(key) && this.valueMap.size == this.capacity) {
        // we need to evict
        // console.log(this.lists[this.lftCount])
        let evictedKey = this.lists[this.lftCount].popleft();
        this.valueMap.delete(evictedKey);
        this.countMap.delete(evictedKey);
    }

    this.valueMap.set(key, value);
    this.counter(key);
    this.lftCount = Math.min(this.countMap.get(key), this.lftCount);
};
/**
 * Your LFUCache object will be instantiated and called as such:
 * var obj = new LFUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */