LeetCode 刷题教程之二

大纲

• LeetCode 刷题教程之一
• LeetCode 刷题教程之二

第 146 道题 - LRU 缓存

题目来源

这是 LeetCode 的 第 146 道算法题 - LRU 缓存，难度为中等。

题目描述

请设计并实现一个满足 LRU（最近最少使用）缓存约束的数据结构。实现 LRUCache 类：

• LRUCache(int capacity)：以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
• void put(int key, int value)：如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字 - 值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

函数 get 和 put 必须以 O (1) 的平均时间复杂度运行。输入 / 输出示例如下：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

大厂面试题变种

在大厂的笔试中，有像腾讯、百度直接考原题的，也有像字节跳动那样考变种的题目，比如在 LRU 的基础上要求增加过期时间，过期的 key 要删除掉。实现思路可以参考 Redis 中 Key 的惰性删除。给每个节点增加一个 expire 属性（时间戳），表示节点的过期时间。当创建或更新节点时，基于当前时间加上设定的生存时间（TTL）计算得到时间戳。当尝试获取一个节点时，首先检查该节点是否存在，然后判断它的 expire 属性是否小于当前时间（即节点是否已经过期）。这样，每次访问节点时只会检查该节点，而不需要轮询所有节点。

题目分析

• LRU 算法最常见的实现方法是使用一个双向链表或类似的数据结构，最近访问的数据会被移动到链表头部，链表尾部的节点就是最久未被访问的数据。
• LRU 算法可以使用双向链表实现，也就是在各个 Node 节点之间增加 prev 指针和 next 指针，以此构成双向链表。将新增或者访问到的节点移动到链表的头部，超出容量时则从链表的尾部删除节点。
• 要满足 O (1) 时间复杂度，可以使用 HaspMap，里面储存的是 key 与链表节点，这样可以快速查找节点，然后将它删除或者移动到链表的头部。
• LRU 的算法核心是哈希链表，本质就是哈希表 + 双向链表的结合体 (HashMap + DoubleLinkedList)，时间复杂度是 O (1)，底层的数据结构如下图所示：

• 下面这幅动图完美诠释了 HashMap + DoubleLinkedList 的工作原理，其中 key2 是最近访问的数据（可以将其移动到双向链表的尾部或者头部）。

题目答案

/**
 * 基于哈希表（HashMap） + 双向链表（DoubleLinkedList）实现 LRU 缓存
 */
public class LRUCache {

    private int cacheSize;
    private Map<Integer, Node<Integer, Integer>> map;
    private DoubleLinkedList<Integer, Integer> doubleLinkedList;

    public LRUCache2(int cacheSize) {
        this.cacheSize = cacheSize;
        this.map = new HashMap<>();
        this.doubleLinkedList = new DoubleLinkedList<>();
    }

    /**
     * PUT操作
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        // 将最近使用到的节点移动到链表的头部
        Node<Integer, Integer> node = map.get(key);
        doubleLinkedList.remove(node);
        doubleLinkedList.addHead(node);
        return node.value;
    }

    /**
     * GET操作
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // 更新节点的值，并将最近使用到的节点移动到链表的头部
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            doubleLinkedList.remove(node);
            doubleLinkedList.addHead(node);
        } else {
            // 位置满了，删除数据
            if (map.size() == this.cacheSize) {
                Node<Integer, Integer> lastNode = doubleLinkedList.getLast();
                doubleLinkedList.remove(lastNode);
                map.remove(lastNode.key);
            }
            // 插入新的节点
            Node<Integer, Integer> newNode = new Node<>(key, value);
            doubleLinkedList.addHead(newNode);
            map.put(key, newNode);
        }
    }

    /**
     * Node节点
     */
    class Node<K, V> {

        K key;
        V value;
        Node<K, V> prev;    // 前驱节点
        Node<K, V> next;    // 后驱节点

        public Node() {
            this.key = null;
            this.value = null;
            this.prev = null;
            this.next = null;
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    /**
     * 虚拟的双向链表
     */
    class DoubleLinkedList<K, V> {

        Node<K, V> head;    // 头节点
        Node<K, V> tail;    // 尾节点

        public DoubleLinkedList() {
            this.head = new Node<>();
            this.tail = new Node<>();
            // 初始状态是头尾相连
            this.head.next = tail;
            this.tail.prev = head;
        }

        /**
         * 添加到头部
         * <p> 将最近使用到的节点移动到链表的头部
         */
        public void addHead(Node<K, V> node) {
            node.prev = this.head;
            node.next = this.head.next;
            this.head.next.prev = node;
            this.head.next = node;
        }

        /**
         * 删除节点
         */
        public void remove(Node<K, V> node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
            // GC
            node.prev = null;
            node.next = null;
        }

        /**
         * 获取最后一个节点
         */
        public Node<K, V> getLast() {
            return this.tail.prev;
        }
    }

}

单元测试代码：

public class LRUCacheTest {

    public static void main(String[] args) {
        LRUCache2 lruCache = new LRUCache2(3);

        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        System.out.println(lruCache.map.keySet());

        lruCache.put(4, 4);
        System.out.println(lruCache.map.keySet());

        lruCache.put(3, 3);
        System.out.println(lruCache.map.keySet());
        lruCache.put(3, 3);
        System.out.println(lruCache.map.keySet());
        lruCache.put(3, 3);
        System.out.println(lruCache.map.keySet());
        lruCache.put(5, 5);
        System.out.println(lruCache.map.keySet());
    }

}

测试输出结果：

[1, 2, 3]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[2, 3, 4]
[3, 4, 5]

在上述单元测试的输出结果中，Key 的打印顺序是有误的（但 LRU 算法的实现是正确的），因为这是 HashMap 中 Key 的顺序（HashMap 是无序的），并不是 DoubleLinkedList 中 Key 的顺序，但至少可以说明最近最少使用的数据已经被删除了。