hot100 146.LRU缓存

思路：如下图所示。

1.疑问一：需要几个哨兵节点？

答：一个就够了。一开始哨兵节点sentinel的prev和next都指向sentinel。随着节点的插入，sentinel的next指向链表的第一个节点（最上面的书），sentinel的prev指向链表的最后一个节点（最下面的书）。

2.疑问二：为什么节点要把key也存下来？

答：在删除链表末尾节点的时候，也要删除哈希表中的记录，这需要知道末尾节点的key。

3.疑问三：为什么要用哈希表？

答：目的是为了降低时间复杂度。如果不使用哈希表，仅使用双向链表，那么get操作需要遍历链表查找节点，时间复杂度为O(n)，put操作也需要遍历链表判断是否存在，时间复杂度也为O(n)。在使用哈希表+双向链表之后，get操作和put操作的定位、查找、插入的时间复杂度都降为O(1)。

4.复杂度分析：

（1）时间复杂度：所有操作均为O(1)。

（2）空间复杂度：O(min(p,capacity))，其中p为put的调用次数。

附代码：

写法一：标准库（面试一般不让调用标准库，需手写链表）。

class LRUCache { private final int capacity; private final Map<Integer,Integer> cache = new LinkedHashMap<>(); //内置LRU public LRUCache(int capacity) { this.capacity = capacity; } public int get(int key) { //先删除key，并取出value做判断 Integer value = cache.remove(key); if(value != null){ //如果在cache中就重新插入到末尾 cache.put(key,value); return value; } //key不在 cache 中 return -1; } public void put(int key, int value) { if(cache.remove(key) != null){ //先删除key，如果key已经存在 cache.put(key,value); //再重新插入到末尾 return; } //key不在cache中，那么就把key插入cache，插入前判断cache是否满了 if(cache.size() == capacity){ //cache满了 Integer eldestKey = cache.keySet().iterator().next(); //链表头部是从未被访问或最久未被访问的key，尾部是最后put的元素，也就是最近被访问的key cache.remove(eldestKey); //移除最久未使用的key } cache.put(key,value); //把当前元素put进来 } }

写法二：手写双向链表。

class LRUCache { // 定义一个双向链表节点的静态内部类 // 静态内部类是在外部类的内部定义的一个普通类 // 静态内部类可以被外部类的所有实例共同使用，创建自己的对象 private static class Node{ // 初始化新节点的key和value，不初始化prev和next指针，默认为null int key,value; Node prev,next; // 将参数k,v分别赋值给当前对象的key,value成员变量 Node(int key,int value){ this.key = key; this.value = value; this.prev = null; this.next = null; } } private final int capacity; private final Node sentinel = new Node(0,0); //哨兵节点，节点的key和value初始化为0 private final Map<Integer,Node> keyToNode = new HashMap<>(); public LRUCache(int capacity) { this.capacity = capacity; sentinel.prev = sentinel; sentinel.next = sentinel; } public int get(int key) { Node node = getNode(key); // 如果存在该节点，getNode会把对应的节点移到链表的头部 return node != null ? node.value : -1; } public void put(int key, int value) { Node node = getNode(key); // 如果存在该节点，getNode会把对应节点移到链表的头部 if(node != null){ //有这本书 node.value = value; //更新value return; } //不存在就创建新节点 node = new Node(key,value); //新书 keyToNode.put(key,node); pushFront(node); //放到最上面 if(keyToNode.size() > capacity){ //书太多了 Node backNode = sentinel.prev; keyToNode.remove(backNode.key); // 根据key把HashMap中的对应键值对删除 remove(backNode); //去掉最后一本书 } } //获取key对应的节点，同时把该节点移到链表头部 private Node getNode(int key){ if(!keyToNode.containsKey(key)){ //没有这本书 return null; } Node node = keyToNode.get(key); //有这本书 remove(node); //把这本书抽出来 pushFront(node); //放到最上面 return node; } //删除一个节点(抽出一本书) private void remove(Node x){ x.prev.next = x.next; x.next.prev = x.prev; } //在链表头添加一个节点（把一本书放到最上面） private void pushFront(Node x){ x.prev = sentinel; x.next = sentinel.next; x.prev.next = x; x.next.prev = x; } }

ACM模式：

import java.util.*; class LRUCache { // 双向链表节点 private static class Node { int key, value; Node prev, next; Node(int key, int value) { this.key = key; this.value = value; this.prev = null; this.next = null; } } private final int capacity; private final Node sentinel = new Node(0, 0); private final Map<Integer, Node> keyToNode = new HashMap<>(); // 是构造函数 // 1.必须与类名完全相同 // 2.没有返回类型（连void都不用写） // 3.使用new关键字调用 // 4.构造函数的作用是初始化新创建的对象 public LRUCache(int capacity) { this.capacity = capacity; sentinel.prev = sentinel; sentinel.next = sentinel; } public int get(int key) { Node node = getNode(key); return node != null ? node.value : -1; } public void put(int key, int value) { Node node = getNode(key); if (node != null) { node.value = value; return; } node = new Node(key, value); keyToNode.put(key, node); pushFront(node); if (keyToNode.size() > capacity) { Node backNode = sentinel.prev; keyToNode.remove(backNode.key); remove(backNode); } } private Node getNode(int key) { if (!keyToNode.containsKey(key)) { return null; } Node node = keyToNode.get(key); remove(node); pushFront(node); return node; } private void remove(Node x) { x.prev.next = x.next; x.next.prev = x.prev; } private void pushFront(Node x) { x.prev = sentinel; x.next = sentinel.next; x.prev.next = x; x.next.prev = x; } } public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取第一行：操作次数 int n = scanner.nextInt(); // 声明一个LRUCache类型的变量 LRUCache lru = null; // 存储输出结果 List<String> output = new ArrayList<>(); // 处理 n 次操作 for (int i = 0; i < n; i++) { String op = scanner.next(); if (op.equals("LRUCache")) { int capacity = scanner.nextInt(); // 创建一个LRUCache类型的对象 // 现在lru指向了一个真正的LRUCache类型的对象 lru = new LRUCache(capacity); output.add("null"); } else if (op.equals("put")) { int key = scanner.nextInt(); int value = scanner.nextInt(); lru.put(key, value); output.add("null"); } else if (op.equals("get")) { int key = scanner.nextInt(); int result = lru.get(key); // 将int类型的res转换成String后添加到列表 output.add(String.valueOf(result)); } } // 输出结果（空格分隔） for (int i = 0; i < output.size(); i++) { System.out.print(output.get(i)); if (i < output.size() - 1) { System.out.print(" "); } } scanner.close(); } }