Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd354ffb

Browse files
edit 146
1 parent8287062 commitd354ffb

File tree

4 files changed

+161
-166
lines changed

4 files changed

+161
-166
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -446,7 +446,7 @@ Your ideas/fixes/algorithms are more than welcome!
446446
|149|[Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_149.java)| O(?)|O(?)| Hard|
447447
|148|[Sort List](https://leetcode.com/problems/sort-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_148.java) O(nlogn)|O(h) | Medium| Linked List, Sort
448448
|147|[Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_147.java) O(n^2)|O(1) | Medium| Linked List
449-
|146|[LRU Cache](https://leetcode.com/problems/lru-cache/)|[Doubly Linked List](../master/src/main/java/com/fishercoder/solutions/_146_use_DoublyLinkedList_plus_HashMap.java) |[Linked Hash Map](../master/leetcode-algorithms/src/main/java/com/fishercoder/solutions/_146_use_LinkedHashMap.java)|O(?)|O(?) | Hard| Linked List
449+
|146|[LRU Cache](https://leetcode.com/problems/lru-cache/)|[Solution](../master/leetcode-algorithms/src/main/java/com/fishercoder/solutions/_146.java)|amortized O(1)| O(n) | Hard| Linked List
450450
|145|[Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_145.java)| O(n)|O(h) | Hard| Binary Tree
451451
|144|[Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_144.java)| O(n)|O(h) | Medium| Binary Tree
452452
|143|[Reorder List](https://leetcode.com/problems/reorder-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_143.java)| O(n)|O(1)| Medium|
Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
packagecom.fishercoder.solutions;
2+
3+
importjava.util.HashMap;
4+
importjava.util.LinkedHashMap;
5+
importjava.util.Map;
6+
7+
/**
8+
* 146. LRU Cache
9+
*
10+
* Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
11+
12+
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
13+
put(key, value) - Set or insert the value if the key is not already present.
14+
When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
15+
16+
Follow up:
17+
Could you do both operations in O(1) time complexity?
18+
19+
Example:
20+
21+
LRUCache cache = new LRUCache(2);//capacity
22+
23+
cache.put(1, 1);
24+
cache.put(2, 2);
25+
cache.get(1); // returns 1
26+
cache.put(3, 3); // evicts key 2
27+
cache.get(2); // returns -1 (not found)
28+
cache.put(4, 4); // evicts key 1
29+
cache.get(1); // returns -1 (not found)
30+
cache.get(3); // returns 3
31+
cache.get(4); // returns 4
32+
*/
33+
34+
publicclass_146 {
35+
36+
publicclassLinkedHashMapSolution {
37+
/**
38+
* The shortest implementation is to use LinkedHashMap:
39+
* specify a size of the linkedHashMap;
40+
* override the removeEldestEntry method when its size exceeds max size:
41+
* https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#removeEldestEntry-java.util.Map.Entry-
42+
* in the constructor, set the last boolean variable to be true: it means the ordering mode,
43+
* if we set it to be true, it means in access order, false, means it's in insertion order:
44+
* https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html#LinkedHashMap-int-float-boolean-
45+
*/
46+
47+
privateMap<Integer,Integer>cache;
48+
privatefinalintmax;
49+
50+
publicLinkedHashMapSolution(intcapacity) {
51+
max =capacity;
52+
cache =newLinkedHashMap<Integer,Integer>(capacity,1.0f,true) {
53+
publicbooleanremoveEldestEntry(Map.Entryeldest) {
54+
returncache.size() >max;
55+
}
56+
};
57+
}
58+
59+
publicintget(intkey) {
60+
returncache.getOrDefault(key, -1);
61+
}
62+
63+
publicvoidset(intkey,intvalue) {
64+
cache.put(key,value);
65+
}
66+
}
67+
68+
publicclassDoublyLinkedListPlusHashMapSolution {
69+
privateclassNode {
70+
intkey,value;
71+
DoublyLinkedListPlusHashMapSolution.Nodeprev,next;
72+
73+
Node(intk,intv) {
74+
this.key =k;
75+
this.value =v;
76+
}
77+
78+
Node() {
79+
this.key =0;
80+
this.value =0;
81+
}
82+
}
83+
84+
privateintcapacity;
85+
privateintcount;
86+
privateDoublyLinkedListPlusHashMapSolution.Nodehead,tail;
87+
privateMap<Integer,DoublyLinkedListPlusHashMapSolution.Node>map;// ATTN: the value should be Node type! This is the whole point
88+
// of having a class called Node!
89+
90+
publicDoublyLinkedListPlusHashMapSolution(intcapacity) {
91+
this.capacity =capacity;
92+
this.count =0;// we need a count to keep track of the number of elements in the cache so
93+
// that we know when to evict the LRU one from the cache
94+
this.map =newHashMap();
95+
head =newDoublyLinkedListPlusHashMapSolution.Node();
96+
tail =newDoublyLinkedListPlusHashMapSolution.Node();
97+
head.next =tail;
98+
tail.prev =head;
99+
}
100+
101+
publicintget(intkey) {
102+
DoublyLinkedListPlusHashMapSolution.Nodenode =map.get(key);// HashMap allows value to be null, this is superior than
103+
// HashTable!
104+
if (node ==null) {
105+
return -1;
106+
}else {
107+
update(node);
108+
returnnode.value;
109+
}
110+
}
111+
112+
publicvoidset(intkey,intvalue) {
113+
DoublyLinkedListPlusHashMapSolution.Nodenode =map.get(key);
114+
if (node ==null) {
115+
node =newDoublyLinkedListPlusHashMapSolution.Node(key,value);
116+
map.put(key,node);
117+
add(node);
118+
count++;
119+
120+
if (count >capacity) {
121+
// ATTN: It's tail.prev, not tail, because tail is always an invalid node, it
122+
// doesn't contain anything, it's always the tail.prev that is the last node in the
123+
// cache
124+
DoublyLinkedListPlusHashMapSolution.NodetoDelete =tail.prev;
125+
map.remove(toDelete.key);
126+
remove(toDelete);
127+
count--;
128+
}
129+
}else {
130+
remove(node);
131+
node.value =value;
132+
add(node);
133+
}
134+
}
135+
136+
privatevoidupdate(DoublyLinkedListPlusHashMapSolution.Nodenode) {
137+
// this simplifies the process, just do two operations, remove the old node first, and then
138+
// just add the node again
139+
// this will guarantee that this node will be at the latest position: the most recently used
140+
// position.
141+
remove(node);
142+
add(node);
143+
}
144+
145+
privatevoidremove(DoublyLinkedListPlusHashMapSolution.Nodenode) {
146+
DoublyLinkedListPlusHashMapSolution.Nodenext =node.next,prev =node.prev;
147+
prev.next =next;
148+
next.prev =prev;
149+
}
150+
151+
privatevoidadd(DoublyLinkedListPlusHashMapSolution.Nodenode) {// ATTN: we'll always add the node into the first position:
152+
// head.next!!!!
153+
DoublyLinkedListPlusHashMapSolution.Nodenext =head.next;
154+
head.next =node;
155+
node.next =next;
156+
node.prev =head;
157+
next.prev =node;
158+
}
159+
}
160+
}

‎src/main/java/com/fishercoder/solutions/_146_use_DoublyLinkedList_plus_HashMap.java

Lines changed: 0 additions & 108 deletions
This file was deleted.

‎src/main/java/com/fishercoder/solutions/_146_use_LinkedHashMap.java

Lines changed: 0 additions & 57 deletions
This file was deleted.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp