题目描述：
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
这题可以通过继承 LinkedHashMap 并使用内置方法实现，不过不推荐，该题考察的是双向链表
这里也提供代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
|
双向链表 + 哈希表
思路是双向链表每个节点存储key，value，以及前后指针，哈希表则存储key和对应节点
head和tail都是伪指针（辅助）
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
|
class LRUCache{
class Node{
int key;
int value;
Node prev;
Node next;
public Node(int key,int value){
this.key = key;
this.value = value;
}
}
Node head;
Node tail;
int size;
int capacity;
Map<Integer,Node> cache;
public LRUCache(int capacity){
head = new Node(-1,-1);
tail = new Node(-1,-1);
head.next = tail;
tail.prev = head;
size = 0;
this.capacity = capacity;
cache = new HashMap<Integer,Node>();
}
// 查询
public int get(int key){
Node node = cache.get(key);
if(node == null){
return -1;
}
moveToHead(node);
return node.value;
}
// 插入
public void put(int key,int value){
Node node = cache.get(key);
// key 不存在
if(node == null){
// 判断容量是否已满
// 未满添加到链表头部
node = new Node(key,value);
cache.put(key,node);
++size;
addToHead(node);
// 已满，删除尾部节点
if(size > capacity){
Node tail = removeTail();
cache.remove(tail.key);
--size;
}
}else{
// 存在，更新值然后移到头部（表示最近使用）
node.value = value;
moveToHead(node);
}
}
// 添加到头部
public void addToHead(Node node){
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
// 移除节点
public void removeNode(Node node){
node.next.prev = node.prev;
node.prev.next = node.next;
}
// 移动到头部
public void moveToHead(Node node){
removeNode(node);
addToHead(node);
}
// 删除尾部节点（删除最久未使用的节点）
public Node removeTail(){
Node t = tail.prev;
removeNode(t);
return t;
}
}
|