146. LRU Cache

Leetcode link

题目简介

本题是一道系统设计的题目，要求我们实现一个最近最少使用缓存 LRU

LRU 的初始化传入一个参数 capacity，声明此缓存的容量

LRU 支持两个方法： put 与 get

其中 put 支持插入/更新一个数据，这个数据会被标记为最新被使用数据，如果插入的数据超过了缓存数量，最久没有被使用的数据会被删除

get 支持读取当前缓存的特定值，被读取的会被标记为最新被使用数据，如果读取的数据不在缓存中则返回 -1

解题思路

由于题目要求我们 get 与 put 都需要 O(1) 的复杂度，所以我们可以用链表配合 map 来做

链表负责维护当前数据的新旧、map 用来判断当前数据是否存在，以及读取数据的值

具体而言，当一个数据越靠近链表头，我们认为它越久没有被使用；当一个数据越靠近链表尾，我们认为它上次被使用时间离现在越近

对于 get 方法来说有两种可能：

1. get 的数据不存在缓存中：此时我们无需操作链表
2. get 的数据在缓存中：我们需要把链表对应到该数据的元素移动到链表尾

对于 put 方法来说，也有两种可能：

1. 当前数据在缓存中，需要更新：此时与 get 的数据在缓存中的场景一致，需要把链表对应到该数据的元素移动到链表尾
2. 当前数据不在缓存中，需要插入：此时我们需要创建一个链表元素，并放置在链表尾；需要注意的是，如果此时缓存容量超了，需要从链表头删除一个数据

总结一下，我们需要对链表进行两种操作：

1. 删除链表中任意元素
2. 添加元素到链表尾

为了让这两个操作复杂度最低，我们需要双向链表 Double-linked list

Javascript

class DLN {
    constructor(key, value) {
        this.key = key
        this.value = value
        this.prev = null
        this.next = null
    }
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.capacity = capacity
    this.map = new Map()
    // head.next points to the least recent used node(the most possible removed node)
    this.head = new DLN()
    // tail.prev points to the last recent used node
    this.tail = new DLN()

    // we use 2 empty nodes to cover all nodes, so we can modify the link easily
    this.head.next = this.tail
    this.tail.prev = this.head
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (!this.map.has(key)) {
        return -1
    }
    const node = this.map.get(key)
    this.remove(node)
    this.add(node)

    return node.value
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.get(key) !== -1) {
        this.tail.prev.value = value
        return
    }

    if (this.map.size === this.capacity) {
        this.map.delete(this.head.next.key)
        this.remove(this.head.next)
    }

    const node = new DLN(key, value)
    this.map.set(key, node)
    this.add(node)
};

// add the node too the tail of the link
LRUCache.prototype.add = function (node) {
    const prevNode = this.tail.prev
    const nextNode = this.tail
    prevNode.next = node
    node.prev = prevNode
    node.next = this.tail
    this.tail.prev = node
}

// remove the node from the link
LRUCache.prototype.remove = function (node) {
    node.next.prev = node.prev
    node.prev.next = node.next
}

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