146. LRU 缓存

一、题目

二、思路

• 题目要求 O(1) 的平均时间复杂度运行 -> 使用Map空间换时间 Map<Integer, Node>
  
• Map 通过 key 直接找到对应节点 getNode(key) -> Node
  
• 记得只要查过该节点之后就应该把该节点放到最前面 pushFront(Node)
  
• put 元素后，在map中添加，记得检查是否凌驾 capacity，凌驾则删除在map中的元素，以及在链表中的元素 delete(Node)
  
• 这里提到的 pushFront(Node) 和 delete(Node) 都是针对双向队列进行位置移动相关的操作，不涉及 Map。
  

三、代码

1. class LRUCache {
2.     class Node{
3.         int key,val;
4.         Node pre, next;
6.         Node(int key, int val) {
7.             this.key = key;
8.             this.val = val;
9.         }
10.     }
12.     Node dummy = new Node(0, 0);
13.     int capacity;
14.     Map<Integer, Node> map = new HashMap<>();
16.         // 初始化双向队列
17.     public LRUCache(int capacity) {
18.         dummy.pre = dummy;
19.         dummy.next = dummy;
20.         this.capacity = capacity;
21.     }
22.    
23.    
24.     public int get(int key) {
25.             // 从 map 中快速获得 node
26.         Node node = map.get(key);
27.         
28.                 // 不存在返回 -1
29.         if (node == null) {
30.             return -1;
31.         }
32.                 // 查询到需要遵循LRU的规则将最近查询的放到队首
33.         delete(node);
34.         pushFront(node);
35.         return node.val;
36.     }
38.     public void put(int key, int value) {
39.         Node node = map.get(key);
40.         // 已经存在就直接进行更新值，结束 put 方法
41.         if (node != null) {
42.             // 更新值
43.             node.val = value;
44.             delete(node);
45.             pushFront(node);
46.             return ;
47.         }
48.         // 不存在就新建一个 node，在双向队列和 map 中同时更新
49.         node = new Node(key,value);
50.         pushFront(node);
51.         map.put(key, node);
52.                 // 更新后检查是否超出容量
53.                 // 超出容量就删除双向队列中的最后一个节点，同时在 map 中删除
54.         if (map.size() > capacity) {
55.             Node lastNode = dummy.pre;
56.             delete(lastNode);
57.             map.remove(lastNode.key);
58.         }
59.     }
61.         // 将 node 放到双向队列队首
62.     private void pushFront(Node node) {
63.         node.next = dummy.next;
64.         node.pre = dummy;
65.         dummy.next.pre = node;
66.         dummy.next = node;
67.     }
68.     // 在双向队列中删除 node
69.     private void delete(Node node) {
70.         node.pre.next = node.next;
71.         node.next.pre = node.pre;
72.     }
73. }
75. /**
76. * Your LRUCache object will be instantiated and called as such:
77. * LRUCache obj = new LRUCache(capacity);
78. * int param_1 = obj.get(key);
79. * obj.put(key,value);
80. */

复制代码