题解 | #设计LRU缓存结构#

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    /*
    1.遍历二维数组中的每一行
    2.若这一行长度为3进行set操作
    3.若这一行长度为2进行进行get操作
    4.LRU缓存中的长度为k
    5.get,set操作要刷新(栈,先进的(在最下边最不常用),在栈顶的是新的(常用))
    6.刷新相当于把元素删除重新入栈
    6.LRU缓存满了,要把栈底元素删除
    
    无解:get 和 set 方法中 key,value 的 类型由Integer 换为int 测试报错(数组越界)
    */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> returnList = new ArrayList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
        LinkedList<Integer> keyList = new LinkedList<>(); //大量插入删除用LinkedList
        
        for(int i = 0; i < operators.length; i++){
            if(operators[i].length == 3){
                set(map,keyList,operators[i][1],operators[i][2],k);
            }else if(operators[i].length == 2){
                returnList.add(get(map,keyList,operators[i][1]));
            }
        }
            
        int[] returnArray = new int[returnList.size()];
        for(int j = 0; j < returnList.size(); j++){
            returnArray[j] = returnList.get(j);
        }
        return returnArray;
        
    }
    
    public void set( HashMap<Integer,Integer> map,LinkedList<Integer> keyList,Integer key,Integer value,int k){
        
        if(keyList.contains(key)){ //key已存在刷新
            // 刷新
            keyList.remove(key);
            keyList.add(key);
        }else{ // 不存在key
            if(keyList.size() < k){ // LRU不满直接插入
                keyList.add(key);
            }else{//LRU已满,删除最不常用的key,value
                map.remove(keyList.removeFirst());
                keyList.add(key); // 插入key
            }
            
        }
        
        map.put(key,value); // 在map中存入新key,value
  }
    
    public int get(HashMap<Integer,Integer> map,LinkedList<Integer> keyList,Integer key){
        if(keyList.contains(key)){
            // 刷新
            keyList.remove(key);
            keyList.add(key);
            return map.get(key);
        }else{
            return -1;
        }
    }
}