3-9 146.LRU 缓存机制

Date：2022-03-13 16:18:00

标签：

• 哈希表和链表的组合

题目：146.LRU 缓存机制(opens new window) ( 中等😕 )

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

实现 LRUCache 类：

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

函数 get 和 put 必须以 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

分析

两个关键点：

• key-value结构，那么需要哈希表
• 维护一个最近 & 最少的一个结构
  • 随意移动、插入
  • 随机访问

很明显，难点在于维护这个最近&最少的一种结构，可以想到 栈、队列、链表等数据结构，这里我开始想到了用队列，但后面发现如果要移动元素到顶部，会影响到队列其他元素，无法满足O(n)，这时就想到链表，因为链表插入，移除元素，满足O(n)。但还有一个问题，链表如何满足随机访问呢？通过map存节点信息即可快速找到该节点。

题解

class DLinkedNode {
  key: number
  value: number
  prev: DLinkedNode | undefined
  next: DLinkedNode | undefined

  constructor(key?: number, value?: number) {
    this.key = key
    this.value = value
  }
}

class LRUCache {
  private capacity: number
  private size: number
  private cache = new Map<number, DLinkedNode>()
  private head: DLinkedNode
  private tail: DLinkedNode

  constructor(capacity: number) {
    this.capacity = capacity
    this.size = 0
    this.head = new DLinkedNode()
    this.tail = new DLinkedNode()

    this.head.next = this.tail
    this.tail.prev = this.head
  }

  get(key: number): number {
    const node = this.cache.get(key)

    if (node === undefined) {
      return -1
    } else {
      this.moveToHead(node)
      return node.value
    }
  }

  put(key: number, value: number): void {
    const node = this.cache.get(key)

    if (node === undefined) {
      // create node
      const newNode = new DLinkedNode(key, value)
      this.cache.set(key, newNode)
      this.addToHead(newNode)
        ++this.size

      if (this.size > this.capacity) {
        const last = this.removeTail()
        this.cache.delete(last.key)
          --this.size
      }
    } else {
      node.value = value
      this.moveToHead(node)
    }
  }

  addToHead(node: DLinkedNode) {
    // Insert elements in head, first prev, then next
    // Insert elements in tail, first next, then prev
    node.prev = this.head
    node.next = this.head.next
    this.head.next.prev = node
    this.head.next = node
  }

  removeNode(node: DLinkedNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
  }

  moveToHead(node: DLinkedNode) {
    this.removeNode(node)
    this.addToHead(node)
  }

  removeTail() {
    const last = this.tail.prev
    this.removeNode(last)

    // for finding the key, and remove the element in cache
    return last
  }
}

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

使用

function main() {
  const obj = new LRUCache(2)
  const param_1 = obj.get(0)
  obj.put(0, 1)
  const param_2 = obj.get(0)

  console.log('[param_1]:', param_1)
  console.log('[param_2]:', param_2)
}

main()