Skip to content

Commit ce0d083

Browse files
Ken-YangKen-Yang
committed
implement LRUCache
1 parent 53b6039 commit ce0d083

4 files changed

Lines changed: 131 additions & 0 deletions

File tree

‎Java/.classpath‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
5+
<classpathentry kind="output" path="bin"/>
6+
</classpath>

.gitignore renamed to Java/.gitignore

File renamed without changes.

‎Java/.project‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectDescription>
3+
<name>LeetCode</name>
4+
<comment></comment>
5+
<projects>
6+
</projects>
7+
<buildSpec>
8+
<buildCommand>
9+
<name>org.eclipse.jdt.core.javabuilder</name>
10+
<arguments>
11+
</arguments>
12+
</buildCommand>
13+
</buildSpec>
14+
<natures>
15+
<nature>org.eclipse.jdt.core.javanature</nature>
16+
</natures>
17+
</projectDescription>

‎Java/src/net/kenyang/algorithm/LRUCache.java‎

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
package net.kenyang.algorithm;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
public class LRUCache {
7+
int iCapacity;
8+
int iCurrentSize = 0;
9+
Map<Integer, Node> map = new HashMap<Integer, Node>();
10+
int iLastKey = -1;
11+
int iFirstKey = -1;
12+
13+
private class Node {
14+
public int value;
15+
public int nextKey = -1;
16+
public int preKey = -1;
17+
}
18+
19+
public LRUCache(int capacity) {
20+
this.iCapacity = capacity;
21+
}
22+
23+
/**
24+
* move to the tail
25+
*
26+
* @param current
27+
* @param key
28+
*/
29+
private void updateToNewestNode(Node current, int key) {
30+
map.get(iLastKey).nextKey = key;
31+
current.preKey = iLastKey;
32+
current.nextKey = -1;
33+
iLastKey = key;
34+
}
35+
36+
/**
37+
* We need to move middleNode to the end, so we need to reconnect the
38+
* prevNode and nextNode.
39+
*
40+
* @param middleNode
41+
*/
42+
private void reconnectNode(Node middleNode) {
43+
Node prev = map.get(middleNode.preKey);
44+
Node next = map.get(middleNode.nextKey);
45+
if (prev != null) {
46+
prev.nextKey = middleNode.nextKey;
47+
}
48+
if (next != null) {
49+
next.preKey = middleNode.preKey;
50+
}
51+
}
52+
53+
public void set(int key, int value) {
54+
55+
Node current = map.get(key);
56+
if (current != null) {
57+
current.value = value;
58+
if (iFirstKey == key) {
59+
iFirstKey = current.nextKey;
60+
updateToNewestNode(current, key);
61+
} else if (key != iLastKey) {
62+
reconnectNode(current);
63+
updateToNewestNode(current, key);
64+
}
65+
} else {
66+
current = new Node();
67+
current.value = value;
68+
current.preKey = iLastKey;
69+
70+
if (iCurrentSize >= iCapacity) {
71+
int newFirstKey = map.get(iFirstKey).nextKey;
72+
map.remove(iFirstKey);
73+
iFirstKey = newFirstKey;
74+
} else {
75+
iCurrentSize++;
76+
}
77+
78+
if (iLastKey != -1 && iCurrentSize != 1) {
79+
map.get(iLastKey).nextKey = key;
80+
}
81+
82+
iLastKey = key;
83+
}
84+
map.put(key, current);
85+
86+
if (iFirstKey == -1) {
87+
iFirstKey = key;
88+
}
89+
90+
}
91+
92+
public int get(int key) {
93+
Node current = map.get(key);
94+
if (current == null) {
95+
return -1;
96+
}
97+
98+
if (iFirstKey == key && iCurrentSize != 1) {
99+
iFirstKey = current.nextKey;
100+
updateToNewestNode(current, key);
101+
} else if (key != iLastKey) {
102+
reconnectNode(current);
103+
updateToNewestNode(current, key);
104+
}
105+
106+
return current.value;
107+
}
108+
}

0 commit comments

Comments
 (0)