创建了一个 “重学TypeScript” 的微信群,想加群的小伙伴,加我微信 “semlinker”,备注 “1” 。阿里、京东、腾讯的大佬都在群里等你哟。
semlinker/awesome-typescript 1.6K
一、题目描述
运用你所掌握的数据结构,设计和实现一个 LRU(最近最少使用)缓存机制。它应该支持以下操作:
- 获取数据 get(key):如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
- 写入数据 put(key, value) :如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作?
示例:
1 2 3 4 5 6 7 8 9 10 11
| LRUCache cache = new LRUCache( 2 );
cache.put(1, 1); cache.put(2, 2); cache.get(1); cache.put(3, 3); cache.get(2); cache.put(4, 4); cache.get(1); cache.get(3); cache.get(4);
|
二、题解
LRU 是 Least Recently Used 的缩写,这种算法认为最近使用的数据是热门数据,下一次很大概率将会再次被使用。而最近很少被使用的数据,很大概率下一次不再用到。当缓存容量满的时候,优先淘汰最近很少使用的数据。
实现 LRU 缓存的常用方法是使用有界队列。实现 LRU 的关键是将所有最近使用的数据放在队列的开头。在每次插入之前,我们检查队列是否已满。如果队列已满,我们将删除其最后一个元素,并将新节点插入队列的开头。如果队列未满,我们只需将数据添加到队列的开头。
为了方便理解,我们借助前面的示例来演示一下上述的处理流程:

当我们想要删除节点或更新节点时,我们需要快速找到该节点在队列中的位置。因此,可以使用 HashMap 支持快速查找操作。在这种情况下,get 操作的时间复杂度为 O(1)。
由于我们还需要有效地删除队列中间的节点,因此需要一个双向链表。在两种情况下,我们需要删除队列中间的节点:
- 客户端指定需要删除一个节点。
- 节点已更新,需要将其删除并插入队列的开头。
通过使用双向链表,一旦我们通过 HashMap 定位了要删除的节点的位置,就可以在 O(1) 时间从队列中删除该节点。
当我们需要更新键的缓存时,我们首先使用 HashMap 定位相应的节点,更新值,然后从队列中删除该节点,并将该节点放置在 Doubly Linked List 的开头。

LRU 算法 Java 实现
下面我们先用 Java 来实现 LRU 缓存算法。
首先定义个双向链表的节点:
1 2 3 4 5 6 7 8 9 10 11
| class Node { int key; int value; Node pre; Node next;
public Node(int key, int value) { this.key = key; this.value = value; } }
|
每次执行操作时,我们都使用 HashMap 定位节点在队列中的位置,然后删除该节点并将其插入链表头。因此最好定义两个方法:
- remove(node):从双向链表中删除指定 node 节点;
- setHead(node):把指定 node 节点插入到双向链表表头。
定义 LRUCache 类
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 81 82 83 84 85 86 87
| public class LRUCache { int capacity; Map<Integer, Node> map = new HashMap<>(); Node head = null; Node tail = null;
public LRUCache(int capacity) { this.capacity = capacity; }
public int get(int key) { if (map.containsKey(key)) { Node node = map.get(key); remove(node); setHead(node); return node.value; } return -1; }
public void remove(Node n) { if (n.pre != null) { n.pre.next = n.next; } else { head = n.next; } if (n.next != null) { n.next.pre = n.pre; } else { tail = n.pre; } }
public void setHead(Node n) { n.next = head; n.pre = null; if (head != null) head.pre = n; head = n; if (tail == null) tail = head; }
public void put(int key, int value) { if (map.containsKey(key)) { Node old = map.get(key); old.value = value; remove(old); setHead(old); } else { Node created = new Node(key, value); if (map.size() >= capacity) { map.remove(tail.key); remove(tail); setHead(created); } else { setHead(created); } map.put(key, created); } } }
|
定义 LRUCacheDemo 测试类
1 2 3 4 5 6 7 8 9 10 11 12
| public class LRUCacheDemo { public static void main(String[] args) { LRUCache cache = new LRUCache(2);
cache.put(1, 1); cache.put(2, 2); System.out.println("cache.get(1): " + cache.get(1)); cache.put(3, 3); System.out.println("cache.get(2): " + cache.get(2)); System.out.println("cache.get(3): " + cache.get(3)); } }
|
以上代码成功运行后,输出以下结果:
1 2 3
| cache.get(1): 1 cache.get(2): -1 cache.get(3): 3
|
三、参考资源
欢迎小伙伴们订阅全栈修仙之路,及时阅读 TypeScript、Node/Deno、Angular 技术栈最新文章。