資訊專欄INFORMATION COLUMN
摘要：當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。但是無法保證是，也無法保證更新數(shù)據(jù)時是，因?yàn)檫@兩個操作必然要遍歷隊列。因?yàn)榭梢酝ㄟ^來判斷是否有這個節(jié)點(diǎn)。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計和實(shí)現(xiàn)一個 LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。
獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)），否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在，則寫入其數(shù)據(jù)值。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。
進(jìn)階:
你是否可以在 O(1) 時間復(fù)雜度內(nèi)完成這兩種操作？
示例:
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
解答：
這一題就是實(shí)現(xiàn)一個最近最少使用的緩存。我們根據(jù)操作系統(tǒng)的定義可以想出一個比較樸素的方法：
利用隊列(基于鏈表的隊列),每放入一個數(shù)據(jù)就入隊列(尾部插入)，而淘汰一個數(shù)據(jù)就出隊列(從頭部淘汰)。
而更新一個數(shù)據(jù)就把這個數(shù)據(jù)先刪除，然后再入隊列。這樣就能夠保證最近最少使用。
這種做法，如果永遠(yuǎn)不更新數(shù)據(jù)，每次插入的數(shù)據(jù)都一定是不在隊列里的，那么能夠保證put()是O(1)。
但是無法保證get()是O(1)，也無法保證更新數(shù)據(jù)時是O(1)，因?yàn)檫@兩個操作必然要遍歷隊列。
如何保證get()是O(1)復(fù)雜度呢？利用HashSet，可以用常數(shù)時間查詢是否有這個元素？而如何使得更新也是O(1)呢？
如果我們的鏈表是雙向鏈表，并且維護(hù)表頭，表尾，再利用一個HashMap定位到這個鏈表節(jié)點(diǎn)(key是這個節(jié)點(diǎn)的key，value是這個節(jié)點(diǎn)的引用)，就可以使得更新也是O(1)。
不過這里可以把HashSet和HashMap合起來用，只用HashMap即可。因?yàn)榭梢酝ㄟ^HashMap.get(key) == null?來判斷是否有這個節(jié)點(diǎn)。
java ac代碼：
class LRUCache {
//使用HashMap+雙向鏈表才能達(dá)到O(1)
HashMapmap;
int capacity;
int size;
Node head,tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap(capacity*2);
head = new Node(0,0);
tail = new Node(0,0);
head.next = tail;
tail.pre = head;
}
public int get(int key) {
Node node = map.get(key);
if(node != null)
{
if(node.next != tail)
{
node.pre.next = node.next;
node.next.pre = node.pre;
node.next = tail;
node.pre = tail.pre;
tail.pre.next = node;
tail.pre = node;
}
return node.value;
}
return -1;
}
public void put(int key, int value) {
if(get(key) != -1)
{
tail.pre.value = value;
return;
}
if(size < capacity)
size++;
else
{
Node node = head.next;
map.remove(node.key);
head.next = node.next;
node.next.pre = head;
}
Node node = new Node(key,value);
map.put(key,node);
node.next = tail;
node.pre = tail.pre;
tail.pre.next = node;
tail.pre = node;
}
class Node
{
int key,value;
Node pre,next;
public Node(int key,int value)
{
this.key = key;
this.value = value;
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/73434.html
摘要：圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖，寫出一個函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。因此使用一個數(shù)組代表每個節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。 題目地址：https://leetcode-cn.com/probl...題目描述： 對于一個具有樹特征的無向圖，我們可選擇任何一個節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小...
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個人主頁：應(yīng)無所住而生...
摘要：對于每個氣球，提供的輸入是水平方向上，氣球直徑的開始和結(jié)束坐標(biāo)。可以射出的弓箭的數(shù)量沒有限制。弓箭一旦被射出之后，可以無限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問題，不太好說清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對于每個氣球，提供的輸入是水平方...
摘要：有效二叉搜索樹定義如下節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 1869·2021-11-11 11:02
閱讀 1785·2021-09-22 15:55
閱讀 2599·2021-09-22 15:18
閱讀 3549·2019-08-29 11:26
閱讀 3819·2019-08-26 13:43
閱讀 2996·2019-08-26 13:32
閱讀 983·2019-08-26 10:55
閱讀 1026·2019-08-26 10:27
