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

思路

• 题目要求get和set都是O(1),所以要快速地查找和插入/删除
• 利用java.util中的LinkedHashMap实现，该类型结合了哈希表和链表的优点

import java.util.*;
import java.util.ArrayList;
import java.util.LinkedHashMap;

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    LinkedHashMap<Integer, Integer> cache=new LinkedHashMap<>();
    public int[] LRU (int[][] operators, int k) {
        ArrayList<Integer> res=new ArrayList<>();
        for(int[] opt:operators){
            if(opt[0]==1) put(opt[1],opt[2],k);
            else res.add(get(opt[1]));
        }
        int[] r=new int[res.size()];
        int idx=0;
        for(Integer it:res){
            r[idx++]=it;
        }
        return r;
    }

    public Integer get(Integer key){
        //如果不存在则返回-1
        if(!cache.containsKey(key)) return -1;
        //将k-v对刷为最新
        int val=cache.get(key);
        cache.remove(key);
        cache.put(key, val);
        return cache.get(key);
    }

    public void put(Integer key, Integer value, Integer capacity){
        //如果已存在key
        if(cache.containsKey(key)){
            //删除现有的key
            cache.remove(key);
            //添加最新的k-v
            cache.put(key, value);
            return;
        }
        //如果不存在key，且缓存已满
        if(cache.size()==capacity){
            //删除最久未使用的元素(链表头部就是最久未使用的元素)
            cache.remove(cache.keySet().iterator().next());
        }
        //最后添加新的k-v对
        cache.put(key, value);
    }
}