题解 | #设计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();
                    count--;
                }
                linkedList.addFirst(operators[i][1]);//新插入的数据将被视为最新操作的数据
                hashMap.put(operators[i][1],operators[i][2]);//添加到HashMap中
                count++;
            }else{//get(key)
                /*  注意：遍历linkedList的几种方式：
                *  1，将linkedList（链表）转换为数组，然后对数组遍历：Object[] A = linkedList.toArray();
                *  2，使用for循环结合get(index)方法遍历，int w = linkedList.get(j);
                *  3，使用for each循环（建议使用，效率高）：for(Integer list:linkedList)
                *  4，使用迭代器Iterator遍历（建议使用，效率高）：for(Iterator it = linkedList.iterator();it.hasNext();)
                *  5，使用pollFirst()遍历，但会删除原链表数据
                *  6，使用pollLast()遍历，但会删除原链表数据
                *  7，使用removeFirst()遍历，但会删除原链表数据
                *  8，使用removeLast()()遍历，但会删除原链表数据
                *  遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；
                *  若单纯只读取，而不删除，LinkedList遍历时建议使用For-each或者迭代器的方式。
                *  千万不要通过随机访问去遍历LinkedList，更不要先将linkedList（链表）转换为数组，然后对数组遍历。
                */
                boolean flag = false;
                int j=0;
//                 for(j=0;j<count;j++){//使用for循环
//                     int w = linkedList.get(j);
//                     if(w == operators[i][1]){
//                         flag = true;
//                         break;
//                     }
//                 }
                
//                 for(Integer list:linkedList){//使用for each循环
//                     if(list == operators[i][1]){
//                         flag = true;
//                         break;
//                     }
//                     j++;
//                 }
                
                for(Iterator it = linkedList.iterator();it.hasNext();){//使用迭代器Iterator遍历
                    int w = (int)it.next();
                    if(w == operators[i][1]){
                        flag = true;
                        break;
                    }
                    j++;
                }
                
                if(flag){//存在该key
                    val[index] = hashMap.get(operators[i][1]);//存在，返回该key的value值
                    index ++;
                    linkedList.remove(j);//从链表中删除该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;
    }
}