問題鏈接

146.LRU緩存

問題描述

請你設計并實現一個滿足 LRU (最近最少使用) 緩存 約束的數據結構。
實現 LRUCache 類：

• LRUCache(int capacity) 以 正整數 作為容量 capacity 初始化 LRU 緩存
• int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。
• void put(int key, int value) 如果關鍵字 key 已經存在，則變更其數據值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導致關鍵字數量超過 capacity ，則應該 逐出 最久未使用的關鍵字。

函數 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

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10^5
• 最多調用 2 * 10^5 次 get 和 put

問題解答

要解決LRU（最近最少使用）緩存問題，我們需要設計一個數據結構，支持在O(1)平均時間復雜度內完成get和put操作。核心思路是結合哈希表（快速查找）和雙向鏈表（維護使用順序）。

解題思路

1. 數據結構選擇：

   • 哈希表（HashMap）：存儲鍵到雙向鏈表節點的映射，實現O(1)時間復雜度的查找。
   • 雙向鏈表：維護節點的使用順序，最近使用的節點放在鏈表頭部，最久未使用的節點放在尾部，支持O(1)時間復雜度的插入、刪除和移動操作。
   • 虛擬頭節點和虛擬尾節點：簡化邊界處理（如插入第一個節點或刪除最后一個節點時無需判斷null）。

2. 核心操作：

   • get(key)：若鍵存在，將對應節點移到鏈表頭部（標記為最近使用）并返回值；否則返回-1。
   • put(key, value)：若鍵存在，更新值并將節點移到頭部；若鍵不存在，創建新節點插入頭部，若容量超限，刪除鏈表尾部節點（最久未使用）并從哈希表中移除對應鍵。

代碼實現

import java.util.HashMap;
import java.util.Map;class LRUCache {// 雙向鏈表節點static class Node {int key;int value;Node prev;Node next;public Node(int key, int value) {this.key = key;this.value = value;}}private final Map<Integer, Node> cache; // 哈希表：key -> 節點private final Node head; // 虛擬頭節點private final Node tail; // 虛擬尾節點private final int capacity; // 緩存容量public LRUCache(int capacity) {this.capacity = capacity;cache = new HashMap<>(capacity);// 初始化虛擬節點并連接head = new Node(-1, -1);tail = new Node(-1, -1);head.next = tail;tail.prev = head;}public int get(int key) {if (!cache.containsKey(key)) {return -1; // 鍵不存在，返回-1}Node node = cache.get(key);moveToHead(node); // 訪問后移到頭部（最近使用）return node.value;}public void put(int key, int value) {if (cache.containsKey(key)) {// 鍵存在，更新值并移到頭部Node node = cache.get(key);node.value = value;moveToHead(node);} else {// 鍵不存在，創建新節點Node newNode = new Node(key, value);cache.put(key, newNode);addToHead(newNode); // 插入頭部// 若容量超限，刪除尾部節點（最久未使用）if (cache.size() > capacity) {Node tailNode = removeTail();cache.remove(tailNode.key);}}}// 將節點移到頭部（先刪除再插入頭部）private void moveToHead(Node node) {removeNode(node);addToHead(node);}// 從鏈表中移除節點private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}// 將節點插入到頭部（虛擬頭節點之后）private void addToHead(Node node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}// 移除尾部節點（虛擬尾節點之前的節點）并返回private Node removeTail() {Node res = tail.prev;removeNode(res);return res;}
}

復雜度分析

• 時間復雜度：get和put操作均為O(1)。哈希表保證了鍵的查找為O(1)，雙向鏈表保證了節點的插入、刪除和移動為O(1)。
• 空間復雜度：O(capacity)，最多存儲capacity個鍵值對。

該實現通過哈希表和雙向鏈表的結合，高效滿足了LRU緩存的約束，適用于需要頻繁訪問且對性能要求較高的場景。