1+ package com .fishercoder .solutions ;
2+
3+ import java .util .HashMap ;
4+ import java .util .LinkedHashMap ;
5+ import java .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+ public class _146 {
35+
36+ public class LinkedHashMapSolution {
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+ private Map <Integer , Integer > cache ;
48+ private final int max ;
49+
50+ public LinkedHashMapSolution (int capacity ) {
51+ max = capacity ;
52+ cache = new LinkedHashMap <Integer , Integer >(capacity , 1.0f , true ) {
53+ public boolean removeEldestEntry (Map .Entry eldest ) {
54+ return cache .size () > max ;
55+ }
56+ };
57+ }
58+
59+ public int get (int key ) {
60+ return cache .getOrDefault (key , -1 );
61+ }
62+
63+ public void set (int key , int value ) {
64+ cache .put (key , value );
65+ }
66+ }
67+
68+ public class DoublyLinkedListPlusHashMapSolution {
69+ private class Node {
70+ int key , value ;
71+ DoublyLinkedListPlusHashMapSolution .Node prev , next ;
72+
73+ Node (int k , int v ) {
74+ this .key = k ;
75+ this .value = v ;
76+ }
77+
78+ Node () {
79+ this .key = 0 ;
80+ this .value = 0 ;
81+ }
82+ }
83+
84+ private int capacity ;
85+ private int count ;
86+ private DoublyLinkedListPlusHashMapSolution .Node head , tail ;
87+ private Map <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+ public DoublyLinkedListPlusHashMapSolution (int capacity ) {
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 = new HashMap ();
95+ head = new DoublyLinkedListPlusHashMapSolution .Node ();
96+ tail = new DoublyLinkedListPlusHashMapSolution .Node ();
97+ head .next = tail ;
98+ tail .prev = head ;
99+ }
100+
101+ public int get (int key ) {
102+ DoublyLinkedListPlusHashMapSolution .Node node = 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+ return node .value ;
109+ }
110+ }
111+
112+ public void set (int key , int value ) {
113+ DoublyLinkedListPlusHashMapSolution .Node node = map .get (key );
114+ if (node == null ) {
115+ node = new DoublyLinkedListPlusHashMapSolution .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 .Node toDelete = 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+ private void update (DoublyLinkedListPlusHashMapSolution .Node node ) {
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+ private void remove (DoublyLinkedListPlusHashMapSolution .Node node ) {
146+ DoublyLinkedListPlusHashMapSolution .Node next = node .next , prev = node .prev ;
147+ prev .next = next ;
148+ next .prev = prev ;
149+ }
150+
151+ private void add (DoublyLinkedListPlusHashMapSolution .Node node ) {// ATTN: we'll always add the node into the first position:
152+ // head.next!!!!
153+ DoublyLinkedListPlusHashMapSolution .Node next = head .next ;
154+ head .next = node ;
155+ node .next = next ;
156+ node .prev = head ;
157+ next .prev = node ;
158+ }
159+ }
160+ }
0 commit comments