-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathSolution0146.java
More file actions
148 lines (125 loc) · 4.29 KB
/
Copy pathSolution0146.java
File metadata and controls
148 lines (125 loc) · 4.29 KB
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
// 146. LRU 缓存
/**
* 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);
*/
/*
1、LRU：最近最久未使用，缓存淘汰算法
2、LinkedHashMap 哈希链表 = 双向链表 + 哈希表
1）哈希表：查找快，但是无序
2）链表：有序，插入、删除快，但是查找慢
*/
// 使用Java的API LinkedHashMap
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> entry) {
return size() > capacity;
}
}
/*
LRUCache类，即手动实现哈希链表、缓存淘汰机制：
1、定义 双向链表节点内部类，包含 公有成员变量“键、值、前驱节点、后驱节点”、构造方法
2、定义 私有成员变量“HashMap缓存、链表大小、链表容量、链表头尾哨兵节点”
3、定义 公有构造方法，初始化成员变量
4、定义 私有方法，处理链表节点，添加节点到头部、删除节点、移动节点到头部、删除尾部节点
5、实现获取节点值
1）根据key从缓存中获取节点
2）如果节点不存在，返回-1
3）如果节点存在，当前被使用了，移动节点到头部
6、实现存入节点
1）根据key从缓存中获取节点
2）如果节点不存在
① 创建节点、添加节点到缓存、添加节点到头部、链表大小加1
② 判断链表大小是否超过链表容量，超过则 删除尾部节点、删除该节点缓存、链表大小减1
3）如果节点存在，更新节点值、移动节点到头部
*/
class LRUCache {
// 内部类，双向链表节点
class DoubleLinkedNode {
int key;
int value;
DoubleLinkedNode prev;
DoubleLinkedNode next;
public DoubleLinkedNode() {}
public DoubleLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, DoubleLinkedNode> cache = new HashMap<>(); // 缓存
private int size; // 大小
private int capacity; // 容量
private DoubleLinkedNode head, tail; // 头尾哨兵节点
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
this.head = new DoubleLinkedNode();
this.tail = new DoubleLinkedNode();
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 获取节点值
public int get(int key) {
DoubleLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
// 存入节点
public void put(int key, int value) {
DoubleLinkedNode node = cache.get(key);
if (node == null) {
DoubleLinkedNode newNode = new DoubleLinkedNode(key, value);
cache.put(key, newNode);
addToHead(newNode);
this.size++;
if (this.size > this.capacity) {
DoubleLinkedNode tailNode = removeTail();
cache.remove(tailNode.key);
this.size--;
}
} else {
node.value = value;
moveToHead(node);
}
}
// 添加节点到头部
private void addToHead(DoubleLinkedNode node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
// 删除节点
private void removeNode(DoubleLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 移动节点到头部：删除节点、添加节点到头部
private void moveToHead(DoubleLinkedNode node) {
removeNode(node);
addToHead(node);
}
// 删除尾部节点
private DoubleLinkedNode removeTail() {
DoubleLinkedNode node = this.tail.prev;
removeNode(node);
return node;
}
}