-
Notifications
You must be signed in to change notification settings - Fork 1
/
Question031.java
192 lines (169 loc) · 5.87 KB
/
Question031.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
package com.hncboy.swordreferstoofferspecial;
import java.util.HashMap;
/**
* @author hncboy
* @date 2021/11/20 16:39
* @description 剑指 Offer II 031.最近最少使用缓存
*
* 运用所掌握的数据结构,设计和实现一个 LRU (Least Recently Used,最近最少使用) 缓存机制 。
*
* 实现 LRUCache 类:
* LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
* int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
* void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。
* 当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
*
*
* 示例:
* 输入
* ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
* [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
* 输出
* [null, null, null, 1, null, -1, null, -1, 3, 4]
* 解释
* LRUCache lRUCache = new LRUCache(2);
* lRUCache.put(1, 1); // 缓存是 {1=1}
* lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
* lRUCache.get(1); // 返回 1
* lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
* lRUCache.get(2); // 返回 -1 (未找到)
* lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
* lRUCache.get(1); // 返回 -1 (未找到)
* lRUCache.get(3); // 返回 3
* lRUCache.get(4); // 返回 4
*
*
* 提示:
* 1 <= capacity <= 3000
* 0 <= key <= 10000
* 0 <= value <= 105
* 最多调用 2 * 105 次 get 和 put
*
* 进阶:是否可以在 O(1) 时间复杂度内完成这两种操作?
* 注意:本题与主站 146 题 {@link com.hncboy.LruCache} 相同:https://leetcode-cn.com/problems/lru-cache/
*
* 来源:力扣(LeetCode)
* 链接:https://leetcode-cn.com/problems/OrIXps
* 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
*/
public class Question031 {
private static class LRUCache {
/**
* 用于快速查找值
*/
private final HashMap<Integer, Node> map;
/**
* 双向链表
*/
private final DoubleList cache;
/**
* 最大容量
*/
private final int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
cache = new DoubleList();
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
// 获取 map 中的值
int value = map.get(key).value;
// 利用 put 方法把该数据提前
put(key, value);
return value;
}
public void put(int key, int val) {
// 构建新节点
Node node = new Node(key, val);
// 如果 map 包含该值
if (map.containsKey(key)) {
// 删除旧的节点,新的插到头部
cache.remove(map.get(key));
// 讲新节点插入到头部
cache.addFirst(node);
// 更新 map 中对应的数据
map.put(key, node);
return;
}
// map 中不包含该值
// 如果容量以及到达上限
if (capacity == cache.size()) {
// 删除链表尾节点
Node last = cache.removeLast();
map.remove(last.key);
}
// 将该节点添加到头部
cache.addFirst(node);
map.put(key, node);
}
private static class Node {
public int key;
public int value;
public Node next;
public Node prev;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private static class DoubleList {
private Node head;
private Node tail;
private int size;
/**
* 在链表头部添加节点,时间复杂度 O(1)
*/
public void addFirst(Node node) {
if (head == null) {
head = tail = node;
} else {
Node oldHead = head;
oldHead.prev = node;
node.next = oldHead;
head = node;
}
size++;
}
/**
* 删除链表中的 node 节点,时间复杂度 O(1)
*/
public void remove(Node node) {
if (head == node && tail == node) {
// 只有一个节点且则直接删除
head = null;
tail = null;
} else if (tail == node) {
// 删除尾节点
node.prev.next = null;
tail = node.prev;
} else if (head == node) {
// 删除头节点
node.next.prev = null;
head = node.next;
} else {
// 移除 node 节点
node.prev.next = node.next;
node.next.prev = node.prev;
}
size--;
}
/**
* 删除链表中最后一个节点,并返回该节点,时间 O(1)
*/
public Node removeLast() {
Node node = tail;
remove(tail);
return node;
}
/**
* 返回链表长度,时间 O(1)
*/
public int size() {
return size;
}
}
}
}