題目

請你設(shè)計并實現(xiàn)一個滿足??LRU (最近最少使用) 緩存?約束的數(shù)據(jù)結(jié)構(gòu)。

實現(xiàn)?LRUCache?類：

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

函數(shù)?get?和?put?必須以?O(1)?的平均時間復(fù)雜度運行。

解題思路

1. 由題可知，需要Map來存儲數(shù)據(jù)，List可以通過通過控制添加到的索引位置來將數(shù)據(jù)提前；
2. 對Map進行操作時，通過更新List涉及的數(shù)據(jù)；
3. 溢出時從List獲取末尾節(jié)點即最近最少使用的數(shù)據(jù)進行刪除更新。

代碼展示

class LRUCache {Map< Integer, Integer> lru = null;List<Integer> sort = null;int cap;public LRUCache(int capacity) {lru = new HashMap<>();sort = new ArrayList<>(capacity);cap = capacity;}public int get(int key) {Integer val = lru.get(key);if(val != null){sort.remove((Integer) key);sort.add(0, key);return val;} else {return -1;}}public void put(int key, int value) {if(lru.containsKey(key)){lru.put(key,value);sort.remove((Integer) key);sort.add(0, key);} else {if (lru.size() == cap) {int last = sort.get(cap - 1);sort.remove(cap - 1);lru.remove(last);}lru.put(key, value);sort.add(0, key);}}
}