面试遇到算法题：实现LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

这是一道大厂面试高频出现的算法题，难度为⭐️⭐️⭐️，属于中等，老铁们来一起看看这个题该怎么解？

1. 原题再现

没有废话，翠花，上酸菜！

2. 具体实现

为了实现一个满足 LRU （最近最少使用）缓存约束的数据结构，我们需要一个能够快速访问、更新和删除的数据结构，V 哥想到了用哈希表，因为哈希表提供了快速的查找能力，但是它不能保持元素的顺序；而双向链表可以保持元素的顺序，并且可以在 O(1) 时间复杂度内进行插入和删除操作。因此， V哥采用结合使用哈希表和双向链表来实现LRU缓存。

以下是 Java 代码实现：

import java.util.HashMap;

class Node {
    int key;
    int value;
    Node prev;
    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache {
    private HashMap<Integer, Node> cache;
    private Node head, tail;
    private int capacity;
    private int count;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.count = 0;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addNode(newNode);
            count++;
            if (count > capacity) {
                Node toDel = popTail();
                cache.remove(toDel.key);
                count--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    private void addNode(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }

    private Node popTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

使用示例：

public class Main {
    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
        System.out.println(lRUCache.get(3));    // 返回 3
        System.out.println(lRUCache.get(4));    // 返回 4
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输出结果应该与题目中的示例输出一致。这个实现使用了哈希表来快速查找节点，同时使用双向链表来维护节点的顺序和实现快速插入和删除操作。这样，我们就可以在 O(1) 的时间复杂度内完成 get 和 put 操作。

实现过程和步骤如下：

1. 定义一个 Node 类，用于双向链表的节点，包含 key、value 以及前驱和后继节点的引用。

2. 在 LRUCache 类中，定义一个 capacity 表示缓存的最大容量，一个 count 表示当前缓存中的节点数量，一个 cache 哈希表用于存储键和节点的映射，以及 head 和 tail 虚拟节点用于简化双向链表的操作。

3. 实现 get 方法，首先在哈希表中查找键对应的节点，如果节点不存在，返回 -1。如果节点存在，则将该节点移动到链表的头部，表示最近被使用，然后返回节点的值。

4. 实现 put 方法，如果键在哈希表中不存在，创建一个新的节点，并将其添加到链表的头部，同时添加到哈希表中。如果插入后节点数量超过了容量，则需要移除链表尾部的节点，并从哈希表中删除对应的条目。如果键已经存在，则更新对应的节点值，并将其移动到链表头部。

5. addNode 方法用于将节点添加到链表头部，removeNode 方法用于从链表中移除节点，moveToHead 方法用于将节点移动到链表头部，popTail 方法用于移除链表尾部的节点。

6. 在 Main 类的 main 方法中，我们创建了一个 LRUCache 实例，并执行了一系列的 put 和 get 操作来演示其功能。

V哥认为这个实现确保了 get 和 put 操作的平均时间复杂度为O(1)。get 操作直接通过哈希表查找节点，而 put 操作中，无论是更新现有节点还是添加新节点，都涉及到对双向链表的操作，这些操作的时间复杂度都是 O(1)。当缓存达到容量上限时，put 操作会移除最久未使用的节点，这也是 O(1) 时间复杂度的操作。

3. 小结一下

V哥的这个实现的关键在于维护一个双向链表，它可以帮助我们快速地访问、更新和删除最近最少使用的节点，同时使用哈希表来提供快速的查找能力。这样，我们就可以在 O(1) 的时间复杂度内完成所有的缓存操作。哈哈干净利索，回答完毕。