146.LRU缓存

链接：146.LRU缓存
难度：Medium
标签：设计、哈希表、链表、双向链表
简介：根据逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

题解 1 - typescript

• 编辑时间：2020-05-25
• 执行用时：228ms
• 内存消耗：47.8MB
• 编程语言：typescript
• 解法介绍：利用哈希映射储存键值对，值为链表节点，利用链表的增删控制复杂度 O(1)。

class LinkedNode {
  public prev: LinkedNode = this;
  public next: LinkedNode = this;
  constructor(public key: number, public val: number, prev?: LinkedNode, next?: LinkedNode) {
    if (prev !== undefined) this.prev = prev;
    if (next !== undefined) this.next = next;
  }
}
class LRUCache {
  cache = new Map<number, LinkedNode>();
  firstNode: LinkedNode | null = null;
  get lastNode(): LinkedNode | null {
    return this.firstNode ? this.firstNode.prev : null;
  }
  get size(): number {
    return this.cache.size;
  }
  constructor(public capacity: number) {}
  get(key: number): number {
    if (this.capacity === 0) return -1;
    if (this.firstNode === null) return -1;
    const node = this.cache.get(key);
    if (node === undefined) return -1;
    const { key: k, val: v } = node;
    this.put(k, v);
    return v;
  }
  put(key: number, value: number): void {
    if (this.capacity === 0) {
    } else if (this.firstNode === null || this.lastNode === null) {
      const node = new LinkedNode(key, value);
      this.cache.set(key, node);
      this.firstNode = node;
    } else if (this.cache.has(key)) {
      const node: LinkedNode = this.cache.get(key)!;
      node.val = value;
      if (node === this.firstNode) this.firstNode = node.next;
      node.prev.next = node.next;
      node.next.prev = node.prev;
      node.prev = this.lastNode;
      node.next = this.firstNode;
      this.lastNode.next = node;
      this.firstNode.prev = node;
    } else if (this.size < this.capacity) {
      const node = new LinkedNode(key, value, this.lastNode, this.firstNode);
      this.cache.set(key, node);
      this.lastNode.next = node;
      this.firstNode.prev = node;
    } else {
      const delNode = this.firstNode;
      this.firstNode = delNode.next;
      this.firstNode.prev = delNode.prev;
      this.cache.delete(delNode.key);
      this.put(key, value);
    }
  }
}

题解 2 - python

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

class Node:
        def __init__(self, key=0, val: int = 0, prev=None, next=None):
            self.key = key
            self.val = val
            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
    
        def remove(self):
            if self.prev:
                self.prev.next, self.next.prev = self.next, self.prev
    
    
    class LRUCache:
        def __init__(self, capacity: int):
            self.cache = {}
            self.capacity = capacity
            self.size = 0
            self.head = Node()
            self.tail = Node()
            self.head.next = self.tail
            self.tail.prev = self.head
    
        def get(self, key: int) -> int:
            if key not in self.cache:
                return -1
            node = self.cache[key]
            node.remove()
            node.append(self.head)
            return node.val
    
        def put(self, key: int, value: int) -> None:
            if key not in self.cache:
                self.cache[key] = Node(key, value)
                self.size += 1
                if self.size > self.capacity:
                    self.size -= 1
                    del self.cache[self.tail.prev.key]
                    self.tail.prev.remove()
            node = self.cache[key]
            node.val = value
            node.remove()
            node.append(self.head)