LeetCode 热题 HOT 100 Java题解——146. LRU缓存机制

LeetCode 热题 HOT 100 Java题解

146. LRU缓存机制哈希表+双向链表复杂度分析

146. LRU缓存机制

题目：

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：

你是否可以使用 O(1) 空间解决此题？

示例：

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得关键字 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得关键字 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4

哈希表+双向链表

要求O(1)时间完成插入，获取，移动操作，一定是需要使用哈希表来定位元素的位置，为了能更快的移动、删除节点，使用双向链表来完成，这里最好是自己来实现一个简单的双向链表。比较值得注意的是，如何比较优雅的来完成链表节点的删除、移动操作，$next$以及$prev$按照怎样的顺序来修改。

class LRUCache { class LinkedNode { int key; int value; LinkedNode prev; LinkedNode next; public LinkedNode(){} public LinkedNode(int key, int value) { this.key = key; this.value = value; } } int capacity; Map<Integer, LinkedNode> map = new HashMap<>(); LinkedNode head, tail; public LRUCache(int capacity) { this.capacity = capacity; head = new LinkedNode(); tail = new LinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { LinkedNode node = map.get(key); if (node == null) return -1; moveToFirst(node); return node.value; } public void put(int key, int value) { LinkedNode node = map.get(key); if (node == null) { node = new LinkedNode(key, value); if (map.size() == capacity) { map.remove(removeLast().key); } map.put(key, node); addFirst(node); } else { moveToFirst(node); node.value = value; } } public void addFirst(LinkedNode node){ node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } public void removeNode(LinkedNode node){ node.prev.next = node.next; node.next.prev = node.prev; } public void moveToFirst(LinkedNode node){ removeNode(node); addFirst(node); } public LinkedNode removeLast() { LinkedNode res = tail.prev; removeNode(res); return res; } }

复杂度分析

时间复杂度：$O(1)$

每种操作的复杂度都为$O(1)$。

空间复杂度：$O(capacity)$

占用规定容量级别的存储空间。