460.LFU缓存

链接：460.LFU缓存
难度：Hard
标签：设计、哈希表、链表、双向链表
简介：请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。

题解 1 - javascript

• 编辑时间：2020-04-09
• 执行用时：1136ms
• 内存消耗：78.2MB
• 编程语言：javascript
• 解法介绍：使用 Node 储存次数和值，进行判断，难点没有就是细节需要考虑。

class Node {
  count = 0;
  value;
  constructor(value) {
    this.value = value;
  }
}
class LFUCache {
  _capacity;
  _cache = new Map();
  newest = [];
  constructor(capacity) {
    this._capacity = capacity;
  }
  get(key) {
    // console.log('====GET-' + key);
    // console.log(this._cache);
    if (this._capacity === 0 || !this._cache.has(key)) return -1;
    const node = this._cache.get(key);
    node.count++;
    this.setNewest(key);
    return node.value;
  }
  setNewest(key) {
    if (this.newest[this.newest.length - 1] === key) return;
    this.newest = this.newest.filter(v => v !== key);
    this.newest.push(key);
  }
  getMinKey() {
    const arr = [];
    let minValue = Number.MAX_VALUE;
    for (let [_, node] of this._cache) {
      if (node.count < minValue) {
        minValue = node.count;
      }
    }
    for (let [key, node] of this._cache) {
      if (node.count === minValue) arr.push(key);
    }
    return arr;
  }
  put(key, value) {
    // console.log('====PUT-' + key + '-' + value);
    // console.log(key, value);
    if (this._capacity === 0) return;
    if (this._cache.has(key)) {
      const node = this._cache.get(key);
      node.value = value;
      node.count++;
      this.setNewest(key);
      return;
    }
    const node = new Node(value);
    if (this._cache.size < this._capacity) {
      this._cache.set(key, node);
      this.setNewest(key);
      return;
    }
    const mins = this.getMinKey();
    if (mins.length === 1) {
      this._cache.delete(mins[0]);
      this._cache.set(key, node);
      this.setNewest(key);
      return;
    }
    // console.log('mins:' + mins);
    // console.log('newest:' + this.newest);
    for (let item of this.newest) {
      if (mins.includes(item)) {
        this._cache.delete(item);
        this._cache.set(key, node);
        this.setNewest(key);
        return;
      }
    }
  }
}

题解 2 - python

• 编辑时间：2023-09-25
• 执行用时：720ms
• 内存消耗：77.2MB
• 编程语言：python
• 解法介绍：链表。

class NodeBase:
    def __init__(self, prev, next):
        self.prev = prev
        self.next = next
    def append(self, prev):
        next = prev.next
        prev.next, next.prev, self.prev, self.next = self, self, prev, next
        return self
    def remove(self):
        if self.prev:
            self.prev.next, self.next.prev, self.next, self.prev = self.next, self.prev, None, None
class ListBase:
    def __init__(self, cstr):
        self.cstr = cstr
        self.head = cstr()
        self.tail = cstr()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def is_empty(self):
        return self.head.next == self.tail

class Node(NodeBase):
    def __init__(self, key=0, val=0, cnt=0, cntNode=None, prev=None, next=None):
        self.key = key
        self.val = val
        self.cnt = cnt
        self.cntNode = cntNode
        NodeBase.__init__(self, prev, next)

class CntNode(NodeBase, ListBase):
    def __init__(self, cnt = 0, prev=None, next=None):
        self.cnt = cnt
        ListBase.__init__(self, Node)
        NodeBase.__init__(self, prev, next)
class LFUCache(ListBase):
    def __init__(self, capacity: int):
        self.cntCache = {}
        self.cache = {}
        self.capacity = capacity
        self.size = 0
        ListBase.__init__(self, CntNode)
    def get_next_cntnode(self, node):
        if node.next.cnt == node.cnt + 1:
            return node.next
        next = CntNode(node.cnt + 1)
        next.append(node)
        self.cntCache[next.cnt] = next
        return next
    def check_cntnode_empty(self, node):
        if node.is_empty():
            node.remove()
            del self.cntCache[node.cnt]
    
    def upgrade_node(self, key: int, update):
        node = self.cache[key]
        update(node)
        node.cnt += 1
        nextCntNode = self.get_next_cntnode(node.cntNode)
        node.remove()
        if node.cntNode != self.head: self.check_cntnode_empty(node.cntNode)
        node.append(nextCntNode.head)
        node.cntNode = nextCntNode
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.upgrade_node(key, lambda node: node)
        return self.cache[key].val
    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            self.cache[key] = Node(key, value, 0, self.head)
            self.size += 1
            if self.size > self.capacity:
                self.size -= 1
                firstCntNode = self.head.next
                removeNode = firstCntNode.tail.prev
                removeNode.remove()
                del self.cache[removeNode.key]
                self.check_cntnode_empty(firstCntNode)
            if self.head.next.cnt != 1:
                self.cntCache[1] = CntNode(1).append(self.head)
        def update(node): node.val = value
        self.upgrade_node(key, update)