|
1 | 1 | classLRUCache { |
| 2 | + |
| 3 | +privatefinalMap<Integer,Node>map; |
| 4 | +privatefinalintcapacity; |
| 5 | +privatefinalNodehead; |
| 6 | +privatefinalNodetail; |
| 7 | + |
| 8 | +publicLRUCache(intcapacity) { |
| 9 | +this.capacity =capacity; |
| 10 | +this.map =newHashMap<>(); |
| 11 | +this.head =newNode(-1, -1); |
| 12 | +this.tail =newNode(-1, -1); |
| 13 | +this.head.next =this.tail; |
| 14 | +this.tail.prev =this.head; |
| 15 | + } |
| 16 | + |
| 17 | +publicintget(intkey) { |
| 18 | +if (!map.containsKey(key)) { |
| 19 | +return -1; |
| 20 | + } |
| 21 | +Nodenode =map.get(key); |
| 22 | +removeNode(node); |
| 23 | +addToFront(node); |
| 24 | +returnnode.value; |
| 25 | + } |
2 | 26 |
|
3 | | -privatefinalMap<Integer,Node>map; |
4 | | -privatefinalNodehead; |
5 | | -privatefinalNodetail; |
6 | | -privateintcapacity; |
| 27 | +publicvoidput(intkey,intvalue) { |
| 28 | +if (map.containsKey(key)) { |
| 29 | +updateExistingKey(key,value); |
| 30 | +return; |
| 31 | + } |
| 32 | +if (map.size() ==this.capacity) { |
| 33 | +NodeleastUsed =tail.prev; |
| 34 | +removeNode(leastUsed); |
| 35 | +map.remove(leastUsed.key); |
| 36 | + } |
| 37 | +NodenewNode =newNode(key,value); |
| 38 | +addToFront(newNode); |
| 39 | +map.put(key,newNode); |
| 40 | + } |
7 | 41 |
|
8 | | -publicLRUCache(intcapacity) { |
9 | | -this.map =newHashMap<>(); |
10 | | -this.head =newNode(-1, -1); |
11 | | -this.tail =newNode(-1, -1); |
12 | | -head.next =tail; |
13 | | -tail.prev =head; |
14 | | -this.capacity =capacity; |
15 | | - } |
| 42 | +privatevoidupdateExistingKey(intkey,intvalue) { |
| 43 | +Nodenode =map.get(key); |
| 44 | +NodeupdatedNode =newNode(key,value); |
| 45 | +removeNode(node); |
| 46 | +addToFront(updatedNode); |
| 47 | +map.put(key,updatedNode); |
| 48 | + } |
16 | 49 |
|
17 | | -publicintget(intkey) { |
18 | | -if (!this.map.containsKey(key)) { |
19 | | -return -1; |
| 50 | +privatevoidremoveNode(Nodenode) { |
| 51 | +NodeprevToNode =node.prev; |
| 52 | +NodenextToNode =node.next; |
| 53 | +prevToNode.next =nextToNode; |
| 54 | +nextToNode.prev =prevToNode; |
20 | 55 | } |
21 | | -Nodenode =this.map.get(key); |
22 | | -removeNode(node); |
23 | | -addNode(node); |
24 | | -returnthis.map.get(key).val; |
25 | | - } |
26 | 56 |
|
27 | | -publicvoidput(intkey,intvalue) { |
28 | | -if (!map.containsKey(key)) { |
29 | | -if (capacity ==0) { |
30 | | -removeNode(tail.prev); |
31 | | - } |
32 | | - }else { |
33 | | -removeNode(this.map.get(key)); |
| 57 | +privatevoidaddToFront(Nodenode) { |
| 58 | +NodenextToHead =head.next; |
| 59 | +node.next =nextToHead; |
| 60 | +nextToHead.prev =node; |
| 61 | +node.prev =head; |
| 62 | +head.next =node; |
34 | 63 | } |
35 | | -addNode(newNode(key,value)); |
36 | | - } |
37 | | - |
38 | | -privatevoidaddNode(Nodenode) { |
39 | | -NodenextToHead =head.next; |
40 | | -head.next =node; |
41 | | -node.next =nextToHead; |
42 | | -nextToHead.prev =node; |
43 | | -node.prev =head; |
44 | | -this.map.put(node.key,node); |
45 | | -this.capacity--; |
46 | | - } |
47 | | - |
48 | | -privatevoidremoveNode(Nodenode) { |
49 | | -NodenextNode =node.next; |
50 | | -node.prev.next =nextNode; |
51 | | -nextNode.prev =node.prev; |
52 | | -this.map.remove(node.key); |
53 | | -this.capacity++; |
54 | | - } |
55 | 64 |
|
56 | | -privatestaticclassNode { |
57 | | -Nodenext; |
58 | | -Nodeprev; |
59 | | -intkey; |
60 | | -intval; |
| 65 | +privatestaticclassNode { |
61 | 66 |
|
62 | | -publicNode(intkey,intval) { |
63 | | -this.key =key; |
64 | | -this.val =val; |
65 | | -this.next =null; |
66 | | -this.prev =null; |
| 67 | +privatefinalintkey; |
| 68 | +privatefinalintvalue; |
| 69 | +privateNodenext; |
| 70 | +privateNodeprev; |
| 71 | + |
| 72 | +publicNode(intkey,intvalue) { |
| 73 | +this.key =key; |
| 74 | +this.value =value; |
| 75 | + } |
67 | 76 | } |
68 | | - } |
69 | 77 | } |
| 78 | + |
| 79 | +/** |
| 80 | + * Your LRUCache object will be instantiated and called as such: |
| 81 | + * LRUCache obj = new LRUCache(capacity); |
| 82 | + * int param_1 = obj.get(key); |
| 83 | + * obj.put(key,value); |
| 84 | + */ |