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

使用链表来模拟缓存结构，表头元素表示最近使用的key

set

检查链表中是否存在该key，若有则更新map中保存的value，并将该key从链表中删除同时在链表头插入。若没有该key，则在链表头插入该key（注意需要先判断链表大小是否越界，若越界则先删除链表尾元素再头插）

get

若链表中有该key，则返回对应的value，同时在链表中删除该key，再在头部插入。
若没有，返回-1

import java.util.*;


public class Solution {
    LinkedList<Integer> list = new LinkedList<>();
    int k = 0;
    List<Integer> ans = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();

    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        this.k = k;
        for(int i = 0; i < operators.length;i++){
            if(operators[i][0] == 1){
                set(operators[i][1], operators[i][2]);
            }else{
                get(operators[i][1]);
            }
        }

        int[] res = new int[ans.size()];
        for(int i = 0; i < ans.size();i++){
            res[i] = ans.get(i);
        }
        return res;
    }

    public void set(int key, int val){
        if(list.contains(key)){
            list.remove((Object)key);
            list.addFirst(key);
            map.put(key, val);
            return;
        }

        if(list.size() == k){
            map.remove(list.getLast());
            list.removeLast();
        }

        list.addFirst(key);
        map.put(key, val);

    }

    public void get(int key){
        if(list.contains(key)){
            list.remove((Object)key);
            list.addFirst(key);
            ans.add(map.get(key));
            return;
        }

        ans.add(-1);
    }
}