forked from algorithm008-class01/algorithm008-class01
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPLruCache.java
More file actions
132 lines (116 loc) · 3.92 KB
/
Copy pathPLruCache.java
File metadata and controls
132 lines (116 loc) · 3.92 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
//运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
//
// 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
//写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在
//写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
//
//
//
// 进阶:
//
// 你是否可以在 O(1) 时间复杂度内完成这两种操作？
//
//
//
// 示例:
//
// LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
//
//cache.put(1, 1);
//cache.put(2, 2);
//cache.get(1); // 返回 1
//cache.put(3, 3); // 该操作会使得关键字 2 作废
//cache.get(2); // 返回 -1 (未找到)
//cache.put(4, 4); // 该操作会使得关键字 1 作废
//cache.get(1); // 返回 -1 (未找到)
//cache.get(3); // 返回 3
//cache.get(4); // 返回 4
//
// Related Topics 设计
package leetcode.editor.cn;
import java.util.HashMap;
import java.util.Map;
//Java：LRU缓存机制
public class PLruCache {
public static void main(String[] args) {
// TO TEST
PLruCache lruCache = new PLruCache();
LRUCache cache = lruCache.new LRUCache( 2 );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4);
}
//leetcode submit region begin(Prohibit modification and deletion)
class LRUCache {
private Node head;
private Node tail;
private Map<Integer,Node> nodeMap = new HashMap<>();
private int size;
private int maxSize;
public LRUCache(int capacity) {
maxSize = capacity;
head = new Node();
tail = new Node();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
Node node = nodeMap.get(key);
if( node == null) return -1;
if( node.pre != head) {
node.pre.next = node.next;
node.next.pre = node.pre;
node.pre = head;
head.next.pre = node;
node.next = head.next;
head.next = node;
}
return node.value;
}
public void put(int key, int value) {
Node node = nodeMap.get(key);
if (node != null){
node.value = value;
get(key);
} else {
node = new Node();
node.value = value;
node.key = key;
nodeMap.put(key, node);
head.next.pre = node;
node.next = head.next;
node.pre = head;
head.next = node;
if (size == maxSize) {
Node tmp = tail.pre;
tail.pre = tmp.pre;
tmp.pre.next = tail;
tmp.pre = null;
tmp.next = null;
nodeMap.remove(tmp.key);
} else {
size++;
}
}
}
class Node {
int value;
int key;
Node next;
Node pre;
}
}
/**
* 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);
*/
//leetcode submit region end(Prohibit modification and deletion)
}