LRU 缓存

如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

题目描述

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

• get(key)- 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
• put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。

输入：
[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
返回值：
[1,-1]
说明：
第一次操作后：最常使用的记录为(“1”, 1)
第二次操作后：最常使用的记录为 (“2”, 2)，(“1”, 1) 变为最不常用的
第三次操作后：最常使用的记录为 (“3”, 2)，(“1”, 1) 还是最不常用的
第四次操作后：最常用的记录为 (“1”, 1)，(“2”, 2) 变为最不常用的
第五次操作后：大小超过了 3，所以移除此时最不常使用的记录 (“2”, 2)，加入记录(“4”, 4)，并且为最常使用的记录，然后(“3”, 2) 变为最不常使用的记录

使用单链表

单链表便于频繁的插入删除操作。
只需要在链表头部插入，尾部删除。
为了在头部插入方便，代码使用了无数据的头结点 head。

/**
 * lru design
 * @param operators int 整型二维数组 the ops
 * @param k int 整型 the k
 * @return int 整型一维数组
 */
function LRU(operators, limit) {
    // 定义链表数据结构
    class Node {
        constructor(key, value, next = null) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    // head 不计入链表总个数，其 next 指向第一个 node
    let head = new Node(Number.MIN_VALUE, Number.MIN_VALUE);
    const resArr = [];
    for (const [op, k, v] of operators) {
        let temp = head.next;
        let pre = head;
        if (v) { // put
            while (temp) {
                // key 已经存在
                if (temp.key === k) {
                    let node = new Node(k, v);
                    // 删除此节点
                    pre.next = temp.next;
                    // 插入新节点
                    let t = head.next;
                    head.next = node;
                    node.next = t;
                    break;
                }
                pre = pre.next;
                temp = temp.next;
            }

            if (temp === null) {  // key 不存在，插入这个 key 的节点时，需要判断整个链表是否是满的！
                let node = new Node(k, v);
                let t = head.next;
                head.next = node;
                node.next = t;
            }
        } else { // get 操作
            while (temp) {
                // key 存在
                if (temp.key === k) {
                    // console.log(temp.value);
                    resArr.push(temp.value);
                    let node = new Node(k, temp.value);
                    // 删除此节点
                    pre.next = temp.next;
                    // 插入新节点
                    let t = head.next;
                    head.next = node;
                    node.next = t;
                    break;
                }
                pre = pre.next;
                temp = temp.next;
            }
            // 没找到，返回 - 1
            if (temp === null) {
                // console.log(-1);
                resArr.push(-1);
            }
        }

        // 截断链表
        let i = 1;
        temp = head;
        while (i <= limit && temp) {
            temp = temp.next;
            i += 1;
        }
        if (temp) {
            temp.next = null;
        }
    }

    return resArr;
}

时间复杂度：O(N)，因为查找 key 需要遍历链表。
空间复杂度：O(limit)

参考链接：

https://juejin.cn/post/6844903855726002189