Title

運用你所掌握的數據結構，設計和實現一個 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

Solve

自帶數據結構：

這尼瑪好熟悉啊，Python里不是有一種結合了哈希表和雙鏈表的數據結構叫OrderedDict么，幾行代碼就能解決戰斗。

class LRUCache(collections.OrderedDict):def __init__(self, capacity: int):super().__init__()self.capacity = capacitydef get(self, key: int) -> int:if key not in self:return -1self.move_to_end(key=key)return self[key]def put(self, key: int, value: int) -> None:if key in self:self.move_to_end(key=key)self[key] = valueif len(self) > self.capacity:self.popitem(last=False)

---

但顯然在面試的時候這不是面試官想要的結果，因此我們還是用哈希表+雙鏈表維護一個數據結構吧。

---

哈希表+雙鏈表：

LRU 緩存機制可以通過哈希表輔以雙鏈表維護所有在緩存中的鍵值對。

• 雙鏈表按照被使用的順序存儲鍵值對，靠近頭部的鍵值對是最近被使用的，靠近尾部的鍵值對是最久沒被使用過的。
• 哈希表即為普通的哈希映射（HashMap），通過緩存數據的鍵映射到其在雙鏈表中的位置。

這樣以來，首先使用哈希表進行定位，找出緩存項在雙鏈表中的位置，隨后將其移動到雙鏈表的頭部，即可在O(1)的時間內完成get或者put操作。

具體的方法如下：

• 對于get操作，首先判斷key是否存在：

  • 如果key不存在，返回-1；
  • 如果key存在，則key對應的節點是最近被使用的節點，通過哈希表定位到該節點在雙鏈表中的位置并將其移動到雙鏈表的頭部，最后返回該節點的值。

• 對于post操作，首先判斷key是否存在：

  • 如果key不存在，使用key和value創建一個新的節點，在雙鏈表的頭部添加該節點，并將key和該節點添加到哈希表中，然后判斷雙鏈表的節點數是否超出容量：
    • 如果超出容量，刪除雙鏈表的尾部節點，并刪除哈希表中對應的項
  • 如果key存在，則與get操作類似，先通過哈希表定位，再將對應的節點的值更新為value，并將該節點移動到雙鏈表的頭部。

上述各項操作中，訪問哈希表的時間復雜度為 O(1)，在雙向鏈表的頭部添加節點、在雙向鏈表的尾部刪除節點的復雜度也為 O(1)。而將一個節點移到雙向鏈表的頭部，可以分成「刪除該節點」和「在雙向鏈表的頭部添加節點」兩步操作，都可以在 O(1) 時間內完成。

小貼士

在雙向鏈表的實現中，使用一個偽頭部（dummy head）和偽尾部（dummy tail）標記界限，這樣在添加節點和刪除節點的時候就不需要檢查相鄰的節點是否存在。

復雜度分析

時間復雜度：對于 put 和 get 都是 O(1)。

空間復雜度：O(capacity)，因為哈希表和雙向鏈表最多存儲 capacity+1 個元素。

Code

class DoubleLinkNode:def __init__(self, key=0, value=0):self.key, self.value, self.prev, self.next = key, value, None, Noneclass LRUCache:def __init__(self, capacity: int):self.cache, self.capacity, self.size = dict(), capacity, 0self.head, self.tail = DoubleLinkNode(), DoubleLinkNode()self.head.next, self.tail.prev = self.tail, self.headdef get(self, key: int) -> int:if key not in self.cache:return -1# 如果 key 存在，先通過哈希表定位，再移到頭部node = self.cache[key]self.moveToHead(node)return node.valuedef put(self, key: int, value: int) -> None:if key not in self.cache:# 如果 key 不存在，創建一個新的節點node = DoubleLinkNode(key, value)# 添加進哈希表self.cache[key] = node# 添加至雙向鏈表的頭部self.addToHead(node)self.size += 1if self.size > self.capacity:# 如果超出容量，刪除雙向鏈表的尾部節點removed = self.removeTail()# 刪除哈希表中對應的項self.cache.pop(removed.key)self.size -= 1else:# 如果 key 存在，先通過哈希表定位，再修改 value，并移到頭部node = self.cache[key]node.value = valueself.moveToHead(node)def addToHead(self, node):node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef removeNode(self, node):node.prev.next = node.nextnode.next.prev = node.prevdef moveToHead(self, node):self.removeNode(node)self.addToHead(node)def removeTail(self):node = self.tail.prevself.removeNode(node)return node

總結

以上是生活随笔為你收集整理的146. LRU Cache的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。