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

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
        int length = operators.length;//一维数组的长度
        int count = 0;//计数器，统计缓存的容量
        int index = 0;//临时数组下表
        int[] val = new int[length];//创建一个临时数组
        LinkedList<Integer> linkedList = new LinkedList<>();//创建一个对象LinkedList
        HashMap<Integer,Integer> hashMap = new HashMap<>();//创建一个对象HashMap
        //LRU缓存工作过程：
        //1. set(key, value)：将记录(key, value)插入该结构
        //2. get(key)：返回key对应的value值
        for(int i=0;i<length;i++){//set(key, value)
            if(operators[i][0] == 1){
                if(count>=k){//如果缓存容量已满，则删除最长时间没有访问的数据
                    linkedList.removeLast();
                }
                linkedList.addFirst(operators[i][1]);//新插入的数据将被视为最新操作的数据
                hashMap.put(operators[i][1],operators[i][2]);//添加到HashMap中
                count++;
            }else{//get(key)
                Object[] A = linkedList.toArray();//将链表转化为数组，遍历判断链表是否存在key（operators[i][1]）
                int len = A.length;
                boolean flag = false;
                int c = 0;
                for(c=0;c<len;c++){
                    int x = (int)A[c];
                    if( x== operators[i][1]){
                        flag = true;
                        break;
                    }
                }
                if(flag){//存在该key
                    val[index] = hashMap.get(operators[i][1]);//存在，返回该key的value值
                    index ++;
                    linkedList.remove(c);//从链表中删除该key，
                    linkedList.addFirst(operators[i][1]);//并将该key添加到最新位置
                }else{//不存在该key
                    val[index] = -1;//不存在，返回-1
                    index ++;
                }
                
            }
        }
        //创建一个长度适合的数组（c），并从长度较长的数组（val）赋值给该数组（c）
        int[] c = new int[index];
        for(int i=0;i<index;i++){
            c[i] = val[i];
        }
        
        return c;
    }
}