思路
双向链表+哈希表实现，要明白STL里的<map>是红黑树实现的，亲测速度不够，要用真.哈希表:<unordered_map>
可能有人要问，为啥不用单向链表？我的理解是为了删除元素的时候不用从头搜索。
当然，针对这道题是可以用单向链表的，即“删除”最无用节点的时候，对链表不作处理，而只是从哈希表里把值删掉。反正在搜索的时候也是直接查的哈希表。副作用是这个链表会越来越长。
另外，不想自己实现双向链表的话，可以用<list>
代码
struct LinkedNode{
int key;
LinkedNode* next;
LinkedNode* prev;
LinkedNode(int _key = -1){
key = _key;
next = NULL;
prev = NULL;
}
};
class LRUCache{
private:
LinkedNode* pHeader;
LinkedNode* pEnd;
unordered_map<int, int> keyValueMap;
int cap;
public:
LRUCache(int capacity) {
cap = capacity;
pHeader = new LinkedNode(); //dummy node
pEnd = new LinkedNode();
pHeader->next = pEnd;
pEnd->prev = pHeader;
}
void refreshQueue(int key){
LinkedNode* pNode = pHeader;
while(pNode->next != NULL){
if(pNode->next->key == key)
break;
pNode = pNode->next;
}
//Move pNode->next to head
LinkedNode* pPrevNode = pNode;
LinkedNode* pHitNode = pNode->next;
LinkedNode* pNextNode = pHitNode->next;
pPrevNode->next = pNextNode;
pNextNode->prev = pPrevNode;
pHeader->next->prev = pHitNode;
pHitNode->prev = pHeader;
pHitNode->next = pHeader->next;
pHeader->next = pHitNode;
}
int removeLast(){
//Remove the last item and return its key
LinkedNode* pToRemove = pEnd->prev;
int key = pToRemove->key;
LinkedNode* pPrev = pToRemove->prev;
pPrev->next = pEnd;
pEnd->prev = pPrev;
delete pToRemove;
return key;
}
int get(int key) {
if(keyValueMap.count(key) > 0){
//Change priority queue
refreshQueue(key);
//Get value
return keyValueMap[key];
} else {
return -1;
}
}
void insert(int key){
LinkedNode* pNext = pHeader->next;
LinkedNode* pNewNode = new LinkedNode(key);
pNewNode->next = pNext;
pNewNode->prev = pHeader;
pHeader->next = pNewNode;
pNext->prev = pNewNode;
}
void set(int key, int value) {
if(keyValueMap.count(key)){
keyValueMap[key] = value; //set key
//Refresh queue
refreshQueue(key);
} else {
if(keyValueMap.size() == cap){
int oldKey = removeLast();
keyValueMap.erase(oldKey);
}
keyValueMap[key] = value;
insert(key);
}
}
};
