struct Node
{
int key;
int value;
Node * prev;
Node * next;
Node(int k, int v) : key(k), value(v), prev(NULL), next(NULL)
{
}
};
struct DoubleLinkedList
{
Node * head;
Node * last;
DoubleLinkedList(): head(NULL), last(NULL)
{
}
~DoubleLinkedList()
{
for(Node * tmp = head; tmp != NULL; tmp = tmp>next)
delete tmp;
}
Node * InsertNode(int key, int value)
{
// Insert the node at the head of the list
Node * newnode = new Node(key, value);
newnode>next = head;
if(head)
{
head>prev = newnode;
head = newnode;
}
else
{
head = newnode;
last = newnode;
}
return newnode;
}
void RemoveLastNode()
{
assert(last != NULL);
Node * prevLastNode = last>prev;
delete last;
last = prevLastNode;
if(last)
last>next = NULL;
else
head = NULL;
}
int GetNode(Node * node)
{
if(node == head)
{
return node>value;
}
else
{
if(node == last)
{
node>next = head;
head>prev = node;
node>prev>next = NULL;
last = node>prev;
node>prev = NULL;
head = node;
}
else
{
node>prev>next = node>next;
node>next>prev = node>prev;
node>next = head;
head>prev = node;
node>prev = NULL;
head = node;
}
return head>value;
}
}
};
class LRUCache
{
public:
LRUCache(int capacity): m_CurrentSize(0), m_Capacity(capacity)
{
}
int get(int key)
{
if(m_Container.find(key) == m_Container.end())
return 1;
else
{
Node * n = m_Container[key];
return priorityList.GetNode(n);
}
}
void set(int key, int value)
{
if(m_Container.find(key) == m_Container.end())
{
if(m_CurrentSize == m_Capacity)
{
// Remove the key from the map
m_Container.erase(priorityList.last>key);
priorityList.RemoveLastNode();
// Remove the corresponding key from the map
m_Container[key] = priorityList.InsertNode(key, value);
}
else
{
m_Container[key] = priorityList.InsertNode(key, value);
m_CurrentSize++;
}
}
}
int m_CurrentSize;
int m_Capacity;
DoubleLinkedList priorityList;
std::unordered_map<int, Node *> m_Container;
};
Give the good answer in local but wrong answers during submissions ?


Actually, I think I have the same issue as you:
Specifically, this is output from the leetcode:
Input: 1, [set(2,1),get(2)] Output: [1] Expected: [1]
My local answer to such a scenario:
LRUCache c(1); c.set(2, 1); cout << c.get(2);
is 1. However, the leetcode says that it is 1. I am confused what is going on with this. My solution is implemented in C++.
Thanks,