LeetCode 146. LRU Cache

思路

双向链表+哈希表实现，要明白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);
        }
    }
};