摘要:當緩存容量達到上限時,它應該在寫入新數據之前刪除最近最少使用的數據值,從而為新的數據值留出空間。但是無法保證是,也無法保證更新數據時是,因為這兩個操作必然要遍歷隊列。因為可以通過來判斷是否有這個節點。
題目地址:
https://leetcode-cn.com/probl...
題目描述:
運用你所掌握的數據結構,設計和實現一個 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
解答:
這一題就是實現一個最近最少使用的緩存。我們根據操作系統的定義可以想出一個比較樸素的方法:
利用隊列(基于鏈表的隊列),每放入一個數據就入隊列(尾部插入),而淘汰一個數據就出隊列(從頭部淘汰)。
而更新一個數據就把這個數據先刪除,然后再入隊列。這樣就能夠保證最近最少使用。
這種做法,如果永遠不更新數據,每次插入的數據都一定是不在隊列里的,那么能夠保證put()是O(1)。
但是無法保證get()是O(1),也無法保證更新數據時是O(1),因為這兩個操作必然要遍歷隊列。
如何保證get()是O(1)復雜度呢?利用HashSet,可以用常數時間查詢是否有這個元素?而如何使得更新也是O(1)呢?
如果我們的鏈表是雙向鏈表,并且維護表頭,表尾,再利用一個HashMap定位到這個鏈表節點(key是這個節點的key,value是這個節點的引用),就可以使得更新也是O(1)。
不過這里可以把HashSet和HashMap合起來用,只用HashMap即可。因為可以通過HashMap.get(key) == null?來判斷是否有這個節點。
java ac代碼:
class LRUCache { //使用HashMap+雙向鏈表才能達到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); */
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/73434.html
摘要:圖因此可以成為樹,在所有可能的樹中,具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖,寫出一個函數找到所有的最小高度樹并返回他們的根節點。因此使用一個數組代表每個節點的入度,若入度為就是葉子節點。 題目地址:https://leetcode-cn.com/probl...題目描述: 對于一個具有樹特征的無向圖,我們可選擇任何一個節點作為根。圖因此可以成為樹,在所有可能的樹中,具有最小...
摘要:關于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板,終止條件,遞歸調用,邏輯處理。 ?作者簡介:大家好,我是車神哥,府學路18號的車神? ?個人主頁:應無所住而生...
摘要:對于每個氣球,提供的輸入是水平方向上,氣球直徑的開始和結束坐標。可以射出的弓箭的數量沒有限制。弓箭一旦被射出之后,可以無限地前進。我們想找到使得所有氣球全部被引爆,所需的弓箭的最小數量。解答這是一道區間覆蓋問題,不太好說清楚,利用模板即可。 題目地址:https://leetcode-cn.com/probl...題目描述:在二維空間中有許多球形的氣球。對于每個氣球,提供的輸入是水平方...
摘要:有效二叉搜索樹定義如下節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節點的值均小于根節點的值,根節點的值均小于右子樹的值,因此中序遍歷以后得到的序列一定是升序序列。 ...
閱讀 1776·2021-11-11 11:02
閱讀 1679·2021-09-22 15:55
閱讀 2484·2021-09-22 15:18
閱讀 3488·2019-08-29 11:26
閱讀 3743·2019-08-26 13:43
閱讀 2646·2019-08-26 13:32
閱讀 897·2019-08-26 10:55
閱讀 965·2019-08-26 10:27