題目鏈接
難度：中等 ??????類型： 哈希表
運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)昔搂，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (最近最少使用) 緩存機(jī)制拍嵌。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫(xiě)入數(shù)據(jù) put 。
獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中潜索，則獲取密鑰的值（總是正數(shù)）臭增，否則返回 -1。
寫(xiě)入數(shù)據(jù) put(key, value) - 如果密鑰不存在竹习，則寫(xiě)入其數(shù)據(jù)值誊抛。當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫(xiě)入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值整陌，從而為新的數(shù)據(jù)值留出空間拗窃。
進(jìn)階:
你是否可以在 O(1) 時(shí)間復(fù)雜度內(nèi)完成這兩種操作？
示例
LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會(huì)使得密鑰 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會(huì)使得密鑰 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
解題思路
哈希表的存儲(chǔ)是無(wú)序的泌辫，用OrderedDict() 随夸，可以做到有序存儲(chǔ)，存儲(chǔ)的順序按照進(jìn)入字典的順序
通過(guò)pop(key)可以得到key所對(duì)應(yīng)的value
popitem()可以的到最后一個(gè)進(jìn)表的value震放，而popitem(last=False)可以得到第一個(gè)進(jìn)表的value
代碼實(shí)現(xiàn)
import collections
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.catch = collections.OrderedDict()
def get(self, key: int) -> int:
if key not in self.catch:
return -1
value = self.catch.pop(key)
self.catch[key] = value
return value
def put(self, key: int, value: int) -> None:
if key in self.catch:
self.catch.pop(key)
elif self.catch and self.capacity == 0:
self.catch.popitem(last=False)
else:
self.capacity -= 1
self.catch[key] = value
