zhangdizhangdi

146.LRU 缓存 🌟

题目

LeetCode 中等

题目

请你设计并实现一个满足 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) 的平均时间复杂度运行。

题解

Map O(1) O(capacity)

js
class LRUCache {
  capacity = 1
  data = new Map()
  constructor(capacity) {
    this.capacity = capacity
  }

  get(key) {
    if (this.data.has(key)) {
      const val = this.data.get(key)
      this.data.delete(key)
      this.data.set(key, val)
      return val
    } else {
      return -1
    }
  }

  put(key, value) {
    if (this.data.has(key)) {
      this.data.delete(key)
    }
    this.data.set(key, value)
    if (this.data.size > this.capacity) {
      const delKey = [...this.data.keys()][0]
      //this.data.keys() 是MapIterator {1,2,3}的结构
      //const delKey = this.data.keys().next().value
      this.data.delete(delKey)
    }
  }
}
const lRUCache = new LRUCache(2)
console.log(lRUCache.put(1, 1)) // 缓存是 {1=1}
console.log(lRUCache.data)
console.log(lRUCache.put(2, 2)) // 缓存是 {1=1, 2=2}
console.log(lRUCache.data)
console.log(lRUCache.get(1)) // 返回 1
console.log(lRUCache.data)
console.log(lRUCache.put(3, 3)) // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
console.log(lRUCache.data)
console.log(lRUCache.get(2)) // 返回 -1 (未找到)
console.log(lRUCache.data)
console.log(lRUCache.put(4, 4)) // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
console.log(lRUCache.data)
console.log(lRUCache.get(1)) // 返回 -1 (未找到)
console.log(lRUCache.get(3)) // 返回 3
console.log(lRUCache.get(4)) // 返回 4
执行结果
undefined
Map(1) { 1 => 1 }
undefined
Map(2) { 1 => 1, 2 => 2 }
1
Map(2) { 2 => 2, 1 => 1 }
undefined
Map(2) { 1 => 1, 3 => 3 }
-1
Map(2) { 1 => 1, 3 => 3 }
undefined
Map(2) { 3 => 3, 4 => 4 }
-1
3
4