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

用两个LinkedList存储数据key和value。

插入一组数据时，检查key是否存在，如果存在就删除对应数据。并重新插入一遍，以保证它们会处于最新的位置上。 如果不存在，也需要将数据插入到LinkedList中。 接着判断LinkedList长度是否达到K，如达到就删除最后一个元素。

查找数据时，先判断key是否存在，如果存在就把数据提前。并将查询到的数据存入ans。如果没找到就将-1存入ans。

最后把ans集合改为数组返回。

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> key = new LinkedList<Integer>();
        LinkedList<Integer> value = new LinkedList<Integer>();
        ArrayList<Integer> ans = new ArrayList<Integer>();
        for(int[] op:operators){
            if(op[0]==1){
                int index = key.indexOf(op[1]);
                if(index>=0){
                    key.remove(index);//移除元素
                    value.remove(index);//
                }
                key.addFirst(op[1]);
                value.addFirst(op[2]);
                if(key.size()>k){
                    value.removeLast();
                    key.removeLast();
                }
            }else{
                int index = key.indexOf(op[1]);
                if(index>=0){
                    ans.add(value.get(index));
                    key.remove(index);
                    key.addFirst(op[1]);
                    int temp = value.remove(index);
                    value.addFirst(temp);
                }else{
                    ans.add(-1);
                }
                
            }
        }
        int[] ret= new int[ans.size()];
        for(int i=0 ; i< ans.size(); i++){
            ret[i]=ans.get(i);
        }
        return ret;
    }
}