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

//先吐槽一下题目，就我所以为出现的问题.
//对于那种get的key不存在或者get的key被移除了缓存队列，我们应不应该在这一次get里将其加入到缓存中。
//按理说是应该的，即使你不存在我也应该在缓存里面存一下，你说key不存在返回-1我能理解，
//但是要是因为它只是被移除了缓存队列但是key是存在的，应该是要把它放到缓存队列里面的。

//我的解法很low，仅仅是为了构造答案而做题，并没有用到LRU的队列，实际上的取值和插入值都是在hashmap上完成的。队列仅仅提供了辅助的作用。
import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        LinkedList<Integer> list=new LinkedList<>();
        HashMap<Integer,Integer> map=new HashMap<>();
        int res[] =new int[102400];
        int st=0;
        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==1){
                for(int j=0;j<list.size();j++){
                    if(list.get(j)==operators[i][1]){
                        list.remove(j);
                        map.remove(operators[i][1]);
                        break;
                    }
                }
                
                map.put(operators[i][1],operators[i][2]);
                
                if(list.size()==k){
                    
                    map.remove( list.removeLast());
                }
                   
                list.addFirst(operators[i][1]);
            }else{
                if(map.get(operators[i][1])!=null){
                     res[st++]=map.get(operators[i][1]);
                      for(int j=0;j<list.size();j++){
                    if(list.get(j)==operators[i][1]){
                        list.remove(j);
                        break;
                    }
                }
                    if(list.size()==k){
                      map.remove( list.removeLast());
                    }
                    list.addFirst(operators[i][1]);
                }else{
                    res[st++]=-1;
                }
               
            }
        }
          int ans[]=new int[st];
        for(int i=0;i<st;i++){
            ans[i]=res[i];
        } 
     
        return ans;
    }
}