Leetcode-146-LRU缓存📌

Licodeao2023-5-26AlgorithmAlgorithm

146. LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 O(1) 的平均时间复杂度运行。

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105getput

解题思路

什么是LRU?open in new window

思路:单链表

  • put操作:
    • 如果节点不存在,直接把节点插入到头部
    • 如果节点存在,则把这个节点从链表中删除,并且更新值再插入到头部
    • 如果插入时,超过最大容量,则将链表的最后一个节点删除,并且将新节点插入到头部
  • get操作:
    • 如果节点存在,则返回,并且将节点删除以及插入到链表头部
    • 如果节点不存在,则直接返回-1,没有额外操作
  • 该方法下,put和get操作的时间复杂度都为O(n),并不符合题目所要求的O(1)
  • 那么,如何优化?
    • 加哈希表,省去get操作遍历的过程;但实际上,时间复杂度还是O(n)。
      • 为什么?
        • 因为不管是put操作还是get操作,都有删除操作,虽然加入哈希表能够省去遍历的过程,但是不能优化删除操作。删除节点需要找到其前驱节点,那么这个寻找前驱节点的过程也需要O(n)的时间复杂度。
      • 如何省去寻找节点的前驱节点这个过程呢?
        • 可以使用双向链表,从而节点本身就包含了其前驱节点和后驱节点的信息,不用再去寻找了,以此达到O(1)的要求。
    • 双向链表 + 哈希表(最终的解决方案)
class ListNode {
    constructor(key, value) {//双向链表的单个节点
        this.key = key
        this.value = value
        this.next = null //指向后一个节点
        this.prev = null //指向前一个节点
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity //容量
        this.hashTable = {} //存放键值对信息
        this.count = 0 //键值对数量
        this.dummyHead = new ListNode() //dummy头节点 方便在链表从开始的地方插入
        this.dummyTail = new ListNode()	//dummy尾节点 方便在链表从末尾删除
        this.dummyHead.next = this.dummyTail //dummyHead和dummyTail相互连接
        this.dummyTail.prev = this.dummyHead
    }

    get(key) {
        let node = this.hashTable[key]//查找哈希表中的键值对
        if (node == null) return -1 //不存在该键值对 返回-1
        this.moveToHead(node) //移动到链表头
        return node.value
    }

    put(key, value) {
        let node = this.hashTable[key] //哈希表中查找该键值对
        if (node == null) {
            let newNode = new ListNode(key, value) //不存在就创建节点
            this.hashTable[key] = newNode //加入哈希表
            this.addToHead(newNode) //加入链表头
            this.count++ //节点数+1
            if (this.count > this.capacity) { //超过容量 从队尾删除一个
                this.removeLRUItem()
            }
        } else {
            node.value = value //键值对存在于哈希表中 就更新
            this.moveToHead(node) //移动到队头
        }
    }

    moveToHead(node) {
        this.removeFromList(node)//从链表中删除节点
        this.addToHead(node)//将该节点添加到链表头
    }

    removeFromList(node) {//删除的指针操作
        let tempForPrev = node.prev
        let tempForNext = node.next
        tempForPrev.next = tempForNext
        tempForNext.prev = tempForPrev
    }

    addToHead(node) {//加入链表头的指针操作
        node.prev = this.dummyHead
        node.next = this.dummyHead.next
        this.dummyHead.next.prev = node
        this.dummyHead.next = node
    }

    removeLRUItem() {
        let tail = this.popTail()//从链表中删除
        delete this.hashTable[tail.key]//从哈希表中删除
        this.count--
    }

    popTail() {
        let tailItem = this.dummyTail.prev//通过dummyTail拿到最后一个节点 然后删除
        this.removeFromList(tailItem)
        return tailItem
    }
}
class DoubleSide {
    key: number;
    value: number;
    next: DoubleSide;
    prev: DoubleSide;

    // 双向链表的单个节点
    constructor(key: number, value: number) {
        this.key = key
        this.value = value
        this.next = null //指向后一个节点
        this.prev = null //指向前一个节点
    }
}

class LRUCache {
    // 哈希表
    hash = {}
    // 容量
    capacity: number
    // 真实大小
    size: number
    // 头指针
    head: DoubleSide;
    // 尾指针(用来删除最后一个节点)
    tail: DoubleSide;

    constructor(capacity: number) {
        this.capacity = capacity
        this.size = 0
        // 虚拟头结点(方便删除)
        this.head = new DoubleSide(-1, -1)
        // 虚拟尾节点(方便删除)
        this.tail = new DoubleSide(-2, -2)
        // 组成双向链表
        this.head.next = this.tail
        this.tail.prev = this.head
    }

    get(key: number): number {
        // 判断节点是否存在
        let temp: DoubleSide = this.hash[key]
        // 如果存在,则删除
        if (temp !== null) {
            // 删除节点
            this.deleteNode(temp)
            // 插入到头部
            this.insertHead(temp)

            return temp.value
        }
        // 不存在
        return -1
    }

    put(key: number, value: number): void {
        // 判断节点是否存在
        let temp: DoubleSide = this.hash[key]
        // 如果存在,删除并插入头部
        if (temp !== null) {
            // 删除
            this.deleteNode(temp)
            // 更新值并插入头部
            temp.value = value
            this.insertHead(temp)
            return
        }
        // 如果不存在,直接插入头部
        let newHead = new DoubleSide(key, value)
        this.insertHead(newHead)
        this.size++
        // 判断大小是否超过容量,超过则删除尾节点
        if (this.size > this.capacity) {
            // 最后一个节点
            let last = this.tail.prev
            this.deleteNode(last)
            // hash表中清除这个key
            delete this.hash[last.key]
            this.size--
        }
    }

    // 删除节点
    deleteNode(temp: DoubleSide) {
        let tempForPrev = temp.prev
        let tempForNext = temp.next
        tempForPrev.next = tempForNext
        tempForNext.prev = tempForPrev
    }
    
    // 插入到头部
    insertHead(temp: DoubleSide) {
        // 先与后驱节点连接
        temp.next = this.head.next
        this.head.next.prev = temp
        // 与head连接
        this.head.next = temp
        temp.prev = this.head
    }
}