一、題目

設(shè)計(jì)LRU(最近最少使用)緩存結(jié)構(gòu)，該結(jié)構(gòu)在構(gòu)造時(shí)確定大小，假設(shè)大小為 capacity ，操作次數(shù)是 n ，并有如下功能:

1. Solution(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
2. get(key)：如果關(guān)鍵字 key 存在于緩存中，則返回key對(duì)應(yīng)的value值，否則返回 -1 。
3. set(key, value)：將記錄(key, value)插入該結(jié)構(gòu)，如果關(guān)鍵字 key 已經(jīng)存在，則變更其數(shù)據(jù)值 value，如果不存在，則向緩存中插入該組 key-value ，如果key-value的數(shù)量超過capacity，彈出最久未使用的key-value
   提示:
   1.某個(gè)key的set或get操作一旦發(fā)生，則認(rèn)為這個(gè)key的記錄成了最常使用的，然后都會(huì)刷新緩存。
   2.當(dāng)緩存的大小超過capacity時(shí)，移除最不經(jīng)常使用的記錄。
   3.返回的value都以字符串形式表達(dá)，如果是set，則會(huì)輸出"null"來表示(不需要用戶返回，系統(tǒng)會(huì)自動(dòng)輸出)，方便觀察
   4.函數(shù)set和get必須以O(shè)(1)的方式運(yùn)行
   5.為了方便區(qū)分緩存里key與value，下面說明的緩存里key用""號(hào)包裹
   數(shù)據(jù)范圍:略
   示例：

[“set”,“set”,“get”,“set”,“get”,“set”,“get”,“get”,“get”],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2
[“null”,“null”,“1”,“null”,“-1”,“null”,“-1”,“3”,“4”]

二、思路

• 看上去很復(fù)雜，實(shí)際上只要考慮好結(jié)構(gòu)就行了?？梢钥吹絪et和get都需要O(1)的復(fù)雜度，所以需要一個(gè)哈希結(jié)果。
• 其次，有一個(gè)自動(dòng)移除最近不活躍節(jié)點(diǎn)的機(jī)制，那么就得考慮結(jié)果有序，鏈表或棧之類。
• 合在一起，就有一個(gè)很合適的數(shù)據(jù)結(jié)構(gòu)了。LinkedHashMap。

三、代碼

public class Solution {Map<Integer,Integer> map;private int capacity;public Solution(int capacity) {// write code heremap = new LinkedHashMap<>(capacity);this.capacity = capacity;}public int get(int key) {// write code hereInteger resultValue = map.get(key);if(resultValue == null){return -1;}else {//將該key存入最后map.remove(key);map.put(key,resultValue);return resultValue;}}public void set(int key, int value) {// write code here//是否存在keyif(map.containsKey(key)){map.remove(key);map.put(key,value);}else{map.put(key, value);}//然后判斷是否溢出if(capacity < map.size()){Integer firstKey = map.keySet().iterator().next();map.remove(firstKey);}}}