NC93：设计LRU缓存结构

LRU (Least recently used) 最近最少使用

像浏览器的缓存策略、memcached的缓存策略都是使用LRU这个算法，LRU算***将近期最不会访问的数据淘汰掉。LRU如此流行的原因是实现比较简单，而且对于实际问题也很实用，良好的运行时性能，命中率较高。下面谈谈如何实现LRU缓存：

• 新数据插入到链表头部
• 每当缓存命中（即缓存数据被访问），则将数据移到链表头部
• 当链表满的时候，将链表尾部的数据丢弃

LRU Cache具备的操作：

• set(key,value)：如果key在hashmap中存在，则先重置对应的value值，然后获取对应的节点cur，将cur节点从链表删除，并移动到链表的头部；若果key在hashmap不存在，则新建一个节点，并将节点放到链表的头部。当Cache存满的时候，将链表最后一个节点删除即可。
• get(key)：如果key在hashmap中存在，则把对应的节点放到链表头部，并返回对应的value值；如果不存在，则返回-1。

解法1：使用队列和map实现

opt == 1 ： 添加(x, y)
opt == 1 ： 确定map中是否存在(x, y)，如果存在queue先移除(x, y)再添加(x, y)，达到移除最不经常使用的记录
size > k ： 移除队列首元素即可

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
        ArrayList<Integer> list=new ArrayList<Integer>();

        Queue<int[]> queue=new LinkedList<int[]>();
        HashMap<Integer,int[]> map=new HashMap<Integer,int[]>();
        for(int i=0;i<operators.length;i++){

            if(queue.size()>k){
                int[] poll=queue.poll();
                map.remove(poll[1]);
            }

            if(operators[i][0]==1){
//                 int[] res=map.get(operators[i][1]);
//                 if(res!=null){
//                     map.remove(operators[i][1]);
//                     queue.remove(res);
//                 }
                map.put(operators[i][1],operators[i]);
                queue.offer(operators[i]);
            }

            if(operators[i][0]==2){
                int[] res=map.get(operators[i][1]);
                if(res!=null){
                    queue.remove(res);
                    queue.offer(res);
                    list.add(res[2]);
                }
                else{
                    list.add(-1);
                }
            }
        }
        int[] result=new int[list.size()];
        for(int i=0;i<list.size();i++){
            result[i]=list.get(i);
        }
        return result;
    }
}