{"id":2116,"date":"2016-08-25T22:36:21","date_gmt":"2016-08-25T14:36:21","guid":{"rendered":"http:\/\/boweihe.me\/?p=2116"},"modified":"2016-08-25T22:36:21","modified_gmt":"2016-08-25T14:36:21","slug":"leetcode-146-lru-cache","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2116","title":{"rendered":"LeetCode 146. LRU Cache"},"content":{"rendered":"

\u601d\u8def<\/h3>\n

\u53cc\u5411\u94fe\u8868+\u54c8\u5e0c\u8868\u5b9e\u73b0\uff0c\u8981\u660e\u767dSTL\u91cc\u7684<map>\u662f\u7ea2\u9ed1\u6811\u5b9e\u73b0\u7684\uff0c\u4eb2\u6d4b\u901f\u5ea6\u4e0d\u591f\uff0c\u8981\u7528\u771f.\u54c8\u5e0c\u8868:<unordered_map>
\n\u53ef\u80fd\u6709\u4eba\u8981\u95ee\uff0c\u4e3a\u5565\u4e0d\u7528\u5355\u5411\u94fe\u8868\uff1f\u6211\u7684\u7406\u89e3\u662f\u4e3a\u4e86\u5220\u9664\u5143\u7d20\u7684\u65f6\u5019\u4e0d\u7528\u4ece\u5934\u641c\u7d22\u3002
\n\u5f53\u7136\uff0c\u9488\u5bf9\u8fd9\u9053\u9898\u662f\u53ef\u4ee5\u7528\u5355\u5411\u94fe\u8868\u7684\uff0c\u5373\u201c\u5220\u9664\u201d\u6700\u65e0\u7528\u8282\u70b9\u7684\u65f6\u5019\uff0c\u5bf9\u94fe\u8868\u4e0d\u4f5c\u5904\u7406\uff0c\u800c\u53ea\u662f\u4ece\u54c8\u5e0c\u8868\u91cc\u628a\u503c\u5220\u6389\u3002\u53cd\u6b63\u5728\u641c\u7d22\u7684\u65f6\u5019\u4e5f\u662f\u76f4\u63a5\u67e5\u7684\u54c8\u5e0c\u8868\u3002\u526f\u4f5c\u7528\u662f\u8fd9\u4e2a\u94fe\u8868\u4f1a\u8d8a\u6765\u8d8a\u957f\u3002
\n\u53e6\u5916\uff0c\u4e0d\u60f3\u81ea\u5df1\u5b9e\u73b0\u53cc\u5411\u94fe\u8868\u7684\u8bdd\uff0c\u53ef\u4ee5\u7528<list><\/p>\n

\u4ee3\u7801<\/h3>\n
struct LinkedNode{\n    int key;\n    LinkedNode* next;\n    LinkedNode* prev;\n    LinkedNode(int _key = -1){\n        key = _key;\n        next = NULL;\n        prev = NULL;\n    }\n};\nclass LRUCache{\nprivate:\n    LinkedNode* pHeader;\n    LinkedNode* pEnd;\n    unordered_map<int, int> keyValueMap;\n    int cap;\npublic:\n    LRUCache(int capacity) {\n        cap = capacity;\n        pHeader = new LinkedNode(); \/\/dummy node\n        pEnd = new LinkedNode();\n        pHeader->next = pEnd;\n        pEnd->prev = pHeader;\n    }\n    void refreshQueue(int key){\n        LinkedNode* pNode = pHeader;\n        while(pNode->next != NULL){\n            if(pNode->next->key == key)\n                break;\n            pNode = pNode->next;\n        }\n        \/\/Move pNode->next to head\n        LinkedNode* pPrevNode = pNode;\n        LinkedNode* pHitNode = pNode->next;\n        LinkedNode* pNextNode = pHitNode->next;\n        pPrevNode->next = pNextNode;\n        pNextNode->prev = pPrevNode;\n        pHeader->next->prev = pHitNode;\n        pHitNode->prev = pHeader;\n        pHitNode->next = pHeader->next;\n        pHeader->next = pHitNode;\n    }\n    int removeLast(){\n        \/\/Remove the last item and return its key\n        LinkedNode* pToRemove = pEnd->prev;\n        int key = pToRemove->key;\n        LinkedNode* pPrev = pToRemove->prev;\n        pPrev->next = pEnd;\n        pEnd->prev = pPrev;\n        delete pToRemove;\n        return key;\n    }\n    int get(int key) {\n        if(keyValueMap.count(key) > 0){\n            \/\/Change priority queue\n            refreshQueue(key);\n            \/\/Get value\n            return keyValueMap[key];\n        } else {\n            return -1;\n        }\n    }\n    void insert(int key){\n        LinkedNode* pNext = pHeader->next;\n        LinkedNode* pNewNode = new LinkedNode(key);\n        pNewNode->next = pNext;\n        pNewNode->prev = pHeader;\n        pHeader->next = pNewNode;\n        pNext->prev = pNewNode;\n    }\n    void set(int key, int value) {\n        if(keyValueMap.count(key)){\n            keyValueMap[key] = value; \/\/set key\n            \/\/Refresh queue\n            refreshQueue(key);\n        } else {\n            if(keyValueMap.size() == cap){\n                int oldKey = removeLast();\n                keyValueMap.erase(oldKey);\n            }\n            keyValueMap[key] = value;\n            insert(key);\n        }\n    }\n};<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u601d\u8def \u53cc\u5411\u94fe\u8868+\u54c8\u5e0c\u8868\u5b9e\u73b0\uff0c\u8981\u660e\u767dSTL\u91cc\u7684<map>\u662f\u7ea2\u9ed1\u6811\u5b9e\u73b0\u7684\uff0c\u4eb2\u6d4b\u901f\u5ea6\u4e0d\u591f\uff0c\u8981\u7528\u771f.\u54c8\u5e0c\u8868:<unordered_map> \u53ef\u80fd\u6709\u4eba\u8981\u95ee\uff0c\u4e3a\u5565\u4e0d\u7528\u5355\u5411\u94fe\u8868\uff1f\u6211\u7684\u7406\u89e3\u662f\u4e3a\u4e86\u5220\u9664\u5143\u7d20\u7684\u65f6\u5019\u4e0d\u7528\u4ece\u5934\u641c\u7d22\u3002 \u5f53\u7136\uff0c\u9488\u5bf9\u8fd9\u9053\u9898\u662f\u53ef\u4ee5\u7528\u5355\u5411\u94fe\u8868\u7684\uff0c\u5373\u201c\u5220\u9664\u201d\u6700\u65e0\u7528\u8282\u70b9\u7684\u65f6\u5019\uff0c\u5bf9\u94fe\u8868\u4e0d\u4f5c\u5904\u7406\uff0c\u800c\u53ea\u662f\u4ece\u54c8\u5e0c\u8868\u91cc\u628a\u503c\u5220\u6389\u3002\u53cd\u6b63\u5728\u641c\u7d22\u7684\u65f6\u5019\u4e5f\u662f\u76f4\u63a5\u67e5\u7684\u54c8\u5e0c\u8868\u3002\u526f\u4f5c\u7528\u662f\u8fd9\u4e2a\u94fe\u8868\u4f1a\u8d8a\u6765\u8d8a\u957f\u3002 \u53e6\u5916\uff0c\u4e0d\u60f3\u81ea\u5df1\u5b9e\u73b0\u53cc\u5411\u94fe\u8868\u7684\u8bdd\uff0c\u53ef\u4ee5\u7528<list> \u4ee3\u7801 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66,207],"class_list":["post-2116","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj","tag-207"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2116","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2116"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2116\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2116"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2116"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}