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)

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

  get(key: number): number {
    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: number, value: number): void {
    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

146.LRU 缓存 🌟 ​

题目 ​

题解 ​

146.LRU 缓存 🌟

题目

题解