146. LRU缓存机制

[YBFACC]

146. LRU缓存机制

思路1

利用js中的map特性=>Map 对象保存键值对，并且能够记住键的原始插入顺序。任何值(对象或者原始值) 都可以作为一个键或一个值。^MDN

map可以保存原始的插入顺序，降低了题目难度

var LRUCache = function (capacity) {
  this.capacity = capacity
  this.map = new Map()
}

LRUCache.prototype.get = function (key) {
  if (this.map.has(key)) {
    let value = this.map.get(key)
    this.map.delete(key) //删除重新设置，会更新位置
    this.map.set(key, value)
    return this.map.get(key)
  }
  return -1
}

LRUCache.prototype.put = function (key, value) {
  if (this.map.has(key)) {
    //存在则删除
    this.map.delete(key)
  }
  if (this.map.size == this.capacity) {
    //如果到达临界值就需要删除第一个
    const { value: key, done } = this.map.keys().next()
    this.map.delete(key)
  }
  this.map.set(key, value)
}

忘记copy谁的了😰

思路2

不使用map，改用对象基础key-value，和双向链表方便查找断链

dummyHead 和 dummyTail

亚头节点和伪节点方便链操作一般化

class ListNode {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.next = null
    this.pre = null
  }
}

class LRUCache {
  constructor(cache) {
    this.cache = cache
    this.count = 0
    this.map = {}
    this.dummyHead = new ListNode()
    this.dummyTail = new ListNode()
    this.dummyHead.next = this.dummyTail
    this.dummyTail.prev = this.dummyHead
  }
  get(key) {
    let node = this.map[key]
    if (!node) return -1
    this.moveToHead(node)
    return node.value
  }
  put(key, value) {
    let node = this.map[key]
    if (!node) {
      let newNode = new ListNode(key, value)
      this.map[key] = newNode
      this.addToHead(newNode)
      this.count++
      if (this.count > this.cache) {
        this.removeLater()
      }
    } else {
      node.value = value
      this.moveToHead(node)
    }
  }
  moveToHead(node) {
    this.removeFromList(node)
    this.addToHead(node)
  }
  removeFromList(node) {
    let temp_pre = node.pre
    let temp_next = node.next
    temp_pre.next = temp_next
    temp_next.pre = temp_pre
  }
  addToHead(node) {
    node.pre = this.dummyHead
    node.next = this.dummyHead.next

    this.dummyHead.next.pre = node
    this.dummyHead.next = node
  }
  removeLater() {
    let later = this.dummyTail.pre
    this.removeFromList(later)
    delete this.map[later.key]
    this.count--
  }
}

参考

❤双向链表的有序性 与 哈希表的快速查询 结合