{"id":233,"date":"2017-09-10T17:28:43","date_gmt":"2017-09-11T00:28:43","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=233"},"modified":"2018-07-10T18:53:25","modified_gmt":"2018-07-11T01:53:25","slug":"leetcode-146-lru-cache","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-146-lru-cache\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 146. LRU Cache O(1)"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"Design and Implement LRU Cache in O(1) -  LeetCode 146 - \u82b1\u82b1\u9171 \u5237\u9898\u627e\u5de5\u4f5c EP50\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/q1Njd3NWvlY?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<div class=\"question-description\">\n<p>Design and implement a data structure for\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Cache_replacement_policies#LRU\" target=\"_blank\" rel=\"noopener\">Least Recently Used (LRU) cache<\/a>. It should support the following operations:\u00a0<code>get<\/code>\u00a0and\u00a0<code>put<\/code>.<\/p>\n<p><code>get(key)<\/code>\u00a0&#8211; Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.<br \/>\n<code>put(key, value)<\/code>\u00a0&#8211; Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.<\/p>\n<p><b>Follow up:<\/b><br \/>\nCould you do both operations in\u00a0<b>O(1)<\/b>\u00a0time complexity?<\/p>\n<p><b>Example:<\/b><\/p>\n<pre>LRUCache cache = new LRUCache( 2 \/* capacity *\/ );\r\n\r\ncache.put(1, 1);\r\ncache.put(2, 2);\r\ncache.get(1);       \/\/ returns 1\r\ncache.put(3, 3);    \/\/ evicts key 2\r\ncache.get(2);       \/\/ returns -1 (not found)\r\ncache.put(4, 4);    \/\/ evicts key 1\r\ncache.get(1);       \/\/ returns -1 (not found)\r\ncache.get(3);       \/\/ returns 3\r\ncache.get(4);       \/\/ returns 4\r\n<\/pre>\n<\/div>\n<div id=\"interviewed-div\"><strong>Idea:<\/strong><\/div>\n<div><\/div>\n<div>Use Hashtable for fast mapping and double linked list for fast manipulation.<\/div>\n<div><\/div>\n<div><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/146-ep50.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-240\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/146-ep50.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/146-ep50.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/146-ep50-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/146-ep50-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/146-ep50-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/div>\n<div><\/div>\n<div><strong>Time Complexity:<\/strong><\/div>\n<div>Put O(1)<\/div>\n<div>Get O(1)<\/div>\n<div><\/div>\n<div><strong>Solution:<\/strong><\/div>\n<div>\n<pre class=\"lang:default decode:true  \">\/\/ \bAuthor: Huahua\r\nclass LRUCache {\r\npublic:\r\n    LRUCache(int capacity) {\r\n        capacity_ = capacity;\r\n    }\r\n    \r\n    int get(int key) {\r\n        const auto it = m_.find(key);\r\n        \/\/ If key does not exist\r\n        if (it == m_.cend()) return -1;\r\n\r\n        \/\/ Move this key to the front of the cache\r\n        cache_.splice(cache_.begin(), cache_, it-&gt;second);\r\n        return it-&gt;second-&gt;second;\r\n    }\r\n    \r\n    void put(int key, int value) {        \r\n        const auto it = m_.find(key);\r\n        \r\n        \/\/ Key already exists\r\n        if (it != m_.cend()) {\r\n            \/\/ Update the value\r\n            it-&gt;second-&gt;second = value;\r\n            \/\/ Move this entry to the front of the cache\r\n            cache_.splice(cache_.begin(), cache_, it-&gt;second);\r\n            return;\r\n        }\r\n        \r\n        \/\/ Reached the capacity, remove the oldest entry\r\n        if (cache_.size() == capacity_) {\r\n            const auto&amp; node = cache_.back();\r\n            m_.erase(node.first);\r\n            cache_.pop_back();\r\n        }\r\n        \r\n        \/\/ Insert the entry to the front of the cache and update mapping.\r\n        cache_.emplace_front(key, value);\r\n        m_[key] = cache_.begin();\r\n    }\r\nprivate:\r\n    int capacity_;\r\n    list&lt;pair&lt;int,int&gt;&gt; cache_;\r\n    unordered_map&lt;int, list&lt;pair&lt;int,int&gt;&gt;::iterator&gt; m_;\r\n};\r\n\r\n\/**\r\n * Your LRUCache object will be instantiated and called as such:\r\n * LRUCache obj = new LRUCache(capacity);\r\n * int param_1 = obj.get(key);\r\n * obj.put(key,value);\r\n *\/<\/pre>\n<p>&nbsp;<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Design and implement a data structure for\u00a0Least Recently Used (LRU) cache. It should support the following operations:\u00a0get\u00a0and\u00a0put. get(key)\u00a0&#8211; Get the value (will always be&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[],"class_list":["post-233","post","type-post","status-publish","format-standard","hentry","category-hashtable","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/233","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=233"}],"version-history":[{"count":9,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/233\/revisions"}],"predecessor-version":[{"id":3076,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/233\/revisions\/3076"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=233"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=233"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=233"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}