I like to read this solution as a small machine: keep the useful information, throw away the noise. For 146. LRU Cache, the solution in this repository is mainly a data structure design solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: data structure design.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are updateKeyTimes, get, put, addNode, removeNode.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 260 ms, faster than 7.78% of C++ online submissions for LRU Cache.
02//Memory Usage: 36.6 MB, less than 100.00% of C++ online submissions for LRU Cache.
03class LRUCache {
04public:
05 map<int, int> cache;
06 int capacity;
07 vector<int> keyTimes;
08
09 LRUCache(int capacity) {
10 this->capacity = capacity;
11 }
12
13 void updateKeyTimes(int key){
14 if(find(keyTimes.begin(), keyTimes.end(), key) != keyTimes.end()){
15 keyTimes.erase(find(keyTimes.begin(), keyTimes.end(), key));
16 }
17 keyTimes.push_back(key);
18 }
19
20 int get(int key) {
21 if(cache.find(key) != cache.end()){
22 updateKeyTimes(key);
23 return cache[key];
24 }
25 return -1;
26 }
27
28 void put(int key, int value) {
29 if(cache.find(key) == cache.end() && cache.size() == capacity){
30 //it's a new key, we need to pop oldest pair
31 int oldest = keyTimes[0];
32 //remove first element
33 keyTimes.erase(keyTimes.begin());
34 cache.erase(cache.find(oldest));
35 }
36 cache[key] = value;
37 updateKeyTimes(key);
38 }
39};
40
41/**
42 * Your LRUCache object will be instantiated and called as such:
43 * LRUCache* obj = new LRUCache(capacity);
44 * int param_1 = obj->get(key);
45 * obj->put(key,value);
46 */
47
48//map + double linked list
49//https://leetcode.com/problems/lru-cache/discuss/45911/Java-Hashtable-%2B-Double-linked-list-(with-a-touch-of-pseudo-nodes)
50//Runtime: 116 ms, faster than 55.33% of C++ online submissions for LRU Cache.
51//Memory Usage: 37.3 MB, less than 96.34% of C++ online submissions for LRU Cache.
52class DLinkedNode{
53public:
54 int key;
55 int value;
56 DLinkedNode *prev, *post;
57 DLinkedNode() : key(0), value(0), prev(NULL), post(NULL) {};
58 DLinkedNode(int k, int v){
59 this->key = k;
60 this->value = v;
61 this->prev = NULL;
62 this->post = NULL;
63 };
64};
65
66class LRUCache {
67public:
68 map<int, DLinkedNode*> cache; //from key to node
69 int count, capacity;
70 DLinkedNode *head, *tail;
71
72 void addNode(DLinkedNode* node){
73 //add to head
74 node->prev = head;
75 node->post = head->post;
76
77 head->post->prev = node;
78 head->post = node;
79 };
80
81 void removeNode(DLinkedNode* node){
82 DLinkedNode *prev = node->prev, *post = node->post;
83
84 // node->prev = NULL; //this will set prev to NULL?
85 // node->post = NULL;
86
87 prev->post = post;
88 post->prev = prev;
89
90 };
91
92 void moveToHead(DLinkedNode* node){
93 removeNode(node);
94 addNode(node);
95 };
96
97 DLinkedNode* popTail(){
98 DLinkedNode* node = tail->prev;
99 removeNode(node);
100 return node;
101 };
102
103 LRUCache(int capacity) {
104 this->count = 0;
105 this->capacity = capacity;
106 head = new DLinkedNode();
107 tail = new DLinkedNode();
108 head->post = tail;
109 tail->prev = head;
110 }
111
112 int get(int key) {
113 DLinkedNode* node = cache[key];
114 if(node == NULL){
115 return -1;
116 }
117 moveToHead(node);
118 return node->value;
119 }
120
121 void put(int key, int value) {
122 DLinkedNode* node = cache[key];
123 if(node == NULL){
124 node = new DLinkedNode(key, value);
125 cache[key] = node;
126 addNode(node);
127 ++count;
128 if(count > capacity){
129 DLinkedNode* last = popTail();
130 cache.erase(cache.find(last->key));
131 --count;
132 }
133 }else{
134 node->value = value;
135 moveToHead(node);
136 }
137 }
138};
139
140/**
141 * Your LRUCache object will be instantiated and called as such:
142 * LRUCache* obj = new LRUCache(capacity);
143 * int param_1 = obj->get(key);
144 * obj->put(key,value);
145 */Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.