leetcode 146.LRU 缓存机制 | 刷题打卡

题目链接

哈希表加双链表

思路

其实这道题主要是考察数据结构的使用，为保证存和取的时间复杂度为O(1)，需要用到哈希表和双链表。如果你对这两种数据结构的特性都很熟悉，那不难想到：

• 使用哈希表存储值，可以保证取的时间复杂度为O(1)
• 使用双向链表存储数据的先后顺序，可以保证插入的时间复杂为O(1)

数据结构如下图所示：

知道数据结构之后，代码就好写了。

代码

/**
 * 双向链表
 */
class DLinkedNode {
    key: number;
    value: number;
    prev: DLinkedNode;
    next: DLinkedNode;

    constructor(key?: number, value?: number) {
        this.key = key;
        this.value = value;
    }

    static addToHead(head: DLinkedNode, node: DLinkedNode) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    static removeNode(node: DLinkedNode) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    static moveToHead(head: DLinkedNode, node: DLinkedNode) {
        this.removeNode(node);
        this.addToHead(head, node);
    }

    static removeTail(tail: DLinkedNode): DLinkedNode {
        const res = tail.prev;
        this.removeNode(res);
        return res;
    }
}

class LRUCache {
    cache: Map<number, DLinkedNode>; // map
    capacity: number; // LRU容量
    head: DLinkedNode; // 链表伪头结点
    tail: DLinkedNode; // 链表伪尾结点

    constructor(capacity: number) {
        this.cache = new Map();
        this.capacity = capacity;
        // 初始化双向链表
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    get(key: number): number {
        if (this.cache.has(key)) {
            const node = this.cache.get(key);
            DLinkedNode.moveToHead(this.head, node);
            return node.value;
        }
        return -1;
    }

    put(key: number, value: number): void {
        const node = this.cache.get(key);
        if (this.cache.has(key)) {
            node.value = value;
            DLinkedNode.moveToHead(this.head, node);
        } else {
          	// 容量不够
            if (this.capacity === this.cache.size) {
                // 删除结点
                const removeNode = DLinkedNode.removeTail(this.tail);
                this.cache.delete(removeNode.key);
            }
            // 插入结点
            const newNode = new DLinkedNode(key, value);
            DLinkedNode.addToHead(this.head, newNode);
            this.cache.set(key, newNode);
        }
    }
}
复制代码