题目

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

题解

无官方题解,可参考评论区

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> 是 哈希表和链表实现的Map接口，具有可预测的迭代次序。 这种实现不同于HashMap，它维持于所有条目的运行双向链表。 此链接列表定义迭代排序，通常是将键插入到地图（插入顺序 ）中的顺序 。 请注意，如果将键重新插入到地图中，则插入顺序不受影响。 （A键k被重新插入到地图m如果当m.containsKey(k)将返回true之前立即调用m.put(k, v)被调用。）

提供了一种特殊的constructor来创建一个链接的哈希映射，其迭代顺序是最后访问的条目的顺序，从最近最近访问到最近的（ 访问顺序 ）。 这种Map非常适合建立LRU缓存。

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 构造一个空的 LinkedHashMap实例，具有指定的初始容量，负载因子和订购模式。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
如果此地图应该删除其最老的条目，则返回true 。 在将新条目插入到地图中之后，此方法由put和putAll调用。 它为实施者提供每次添加新的条目时删除最老条目的机会。 如果地图代表一个缓存，这是非常有用的：它允许地图通过删除陈旧的条目来减少内存消耗。

import java.util.*;
class LRUCache {
	private int size;
    private int oldestKey = 0;
    private LinkedHashMap<Integer, Integer> lhm;
    public LRUCache(int capacity) {
    	this.size = capacity;
    	lhm = new LinkedHashMap<Integer,Integer>(capacity, 1 , true){
    		@Override
                protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                    boolean isRemove = false;
                    if (this.size() > size) {
                        isRemove = true;
                        oldestKey = eldest.getKey();
                    }
                    return isRemove;
                }
    	};

    }
    
    public int get(int key) {
        if (lhm.get(key) != null) {
            return lhm.get(key);
        } else return -1;
    }
    
    public void put(int key, int value) {
        if (lhm.size() > size) {
            lhm.remove(oldestKey);
        }
        lhm.put(key, value);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

执行用时 : 161 ms, 在LRU Cache的Java提交中击败了38.39% 的用户

内存消耗 : 72.5 MB, 在LRU Cache的Java提交中击败了17.16% 的用户

感想

感觉基本就是按那个评论区的做的，重写方法什么的感觉还是要多研究一下java给的这些API，不然都不了解的话，就谈不上自己想到可以使用这些数据结构了！

当时就像到了要哈希，但是没想到还有一个专门做LRU的LinkedHashMap，长见识了。

就是感觉这样直接来的话，效率还是比较低。可能得自己实现Hashmap和LinkedList，再用他们实现一个LinkedHashMap效率会比较好，毕竟这样就可以省掉一些题目不需要的内容。比如这里只需要单向链表就够用了，而Java类库里面的实现是双向链表之而立的。详情可以参考JAVA击败99%的评论区回复.