【数据结构】LRU

[miracles1919]

146. LRU 缓存

参考：算法就像搭乐高：带你手撸 LRU 算法

• 双向链表：增加/删除/移动都是 O(1)
• 哈希表：查找为 O(1)

[miracles1919]

创建一个双向链表

function Node(key, val, next, prev) {
    this.key = key === undefined ? null : key
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
    this.prev = prev === undefined ? null : prev
}

class DoubleList {
    constructor() {
        this.head = new Node()
        this.tail = new Node()
        this.head.next = this.tail
        this.tail.prev = this.head
        this.size = 0
    }

   // 添加至尾部
    add(node) {
        node.prev = this.tail.prev
        node.next = this.tail
        this.tail.prev.next = node
        this.tail.prev = node
        this.size++
    }

    // 删除某个节点
    remove(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
        this.size--
    }

    // 删除头部节点
    removeFirst() {
        if (this.head.next === this.tail) return null
        const first = this.head.next
        this.remove(first)
        return first
    }
}

[miracles1919]

抽象一层方法，统一操作 list 和 map

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

// 更新为最近使用的节点
LRUCache.prototype.update = function (key) {
    const node = this.map.get(key)
    this.list.remove(node)
    this.list.add(node)
    return node
}

// 添加节点
LRUCache.prototype.add = function (key, val) {
    const node = new Node(key, val)
    this.list.add(node)
    this.map.set(key, node)
}

// 删除节点
LRUCache.prototype.delete = function (key) {
    const node = this.map.get(key)
    this.list.remove(node)
    this.map.delete(key)
}

// 删除最久未使用的节点
LRUCache.prototype.deleteLast = function () {
    const node = this.list.removeFirst()
    this.map.delete(node.key)
}

[miracles1919]

LRUCache.prototype.get = function (key) {
    if (!this.map.has(key)) return -1
    const node = this.update(key)
    return node.val
};

LRUCache.prototype.put = function (key, value) {
    if (this.map.has(key)) {
        this.delete(key)
        this.add(key, value)
        return
    }

    if (this.capacity === this.map.size) {
        this.deleteLast()
    }
    this.add(key, value)
};

[miracles1919]

用 map 更简单

class LRUCache {
  capacity: number
  map: Map<number, number>
  constructor(capacity: number) {
    this.capacity = capacity
    this.map = new Map()
  }

  get(key: number): number {
    if (this.map.has(key)) {
      const value = this.map.get(key)
      this.map.delete(key, value)
      this.map.set(key, value)
      return value
    }
    return -1
  }

  set(key: number, value: number): void {
    if (this.map.has(key)) {
      this.map.set(key, value)
    }
    this.map.set(key, value)

    if (this.capacity > this.map.size) {
      this.map.delete(this.map.keys().next().value)
    }
  }
}