47.LRU Cache-LRU缓存

题目描述：


解析：方法一：重写LinkedHashMap 方法二：自己用链表实现

//方法一：
class LRUCache {
    //创建一个LinkedHashMap  
    private LinkedHashMap<Integer,Integer> map;
    public LRUCache(int capacity) {
        map=new LinkedHashMap<Integer,Integer>(capacity,0.75f,true){
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;  //当大小超过容量了，就移除该map中最老的键和值
            }
        };
    }
    public int get(int key) {
       return map.getOrDefault(key,-1);
    }
    public void put(int key, int value) {
        map.put(key,value);
    }
}

对于put操作：

//方法二：手动用链表实现
class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        int val = map.get(key).val;
        // 利用 put 方法把该数据提前
        put(key, val);
        return val;
    }
    public void put(int key, int val) {
        // 先把新节点 x 做出来
        Node x = new Node(key, val);
        if (map.containsKey(key)) {
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            // 更新 map 中对应的数据
            map.put(key, x);
        } else {
            if (cap == cache.size()) {
                // 删除链表最后一个数据
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            // 直接添加到头部
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}