{"id":318,"date":"2022-12-06T20:03:28","date_gmt":"2022-12-06T12:03:28","guid":{"rendered":"https:\/\/dmoe.nicolite.cn\/?p=318"},"modified":"2022-12-06T20:03:56","modified_gmt":"2022-12-06T12:03:56","slug":"leetcode-146-lru%e7%bc%93%e5%ad%98","status":"publish","type":"post","link":"https:\/\/dmoe.nicolite.cn\/?p=318","title":{"rendered":"LeetCode 146. LRU\u7f13\u5b58"},"content":{"rendered":"\n<p>\u5730\u5740\uff1a<a href=\"https:\/\/leetcode.cn\/problems\/lru-cache\/\" data-type=\"URL\" data-id=\"https:\/\/leetcode.cn\/problems\/lru-cache\/\" target=\"_blank\" rel=\"noreferrer noopener\">146.LRU\u7f13\u5b58<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>\u8bed\u8a00Java<\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>class LRUCache {\n\n    \/\/\u63d2\u5165\u5220\u9664O(1)\uff0c\u4f7f\u7528\u53cc\u5411\u94fe\u8868\n    class DNode {\n        int key;\n        int value;\n        DNode next;\n        DNode pre;\n\n        public DNode(int key, int value, DNode next, DNode pre) {\n            this.key = key;\n            this.value = value;\n            this.next = next;\n            this.pre = pre;\n        }\n\n        public DNode(int key, int value) {\n            this.key = key;\n            this.value = value;\n        }\n    }\n\n    private int capacity = 0;\n\n    \/\/\u968f\u673a\u8bbf\u95eeO(1)\uff0c\u4f7f\u7528\u54c8\u5e0c\u8868\n    private HashMap&lt;Integer, DNode> keyMap;\n\n    private DNode dummy;\n    private DNode tail;\n\n    private int size = 0;\n\n\n    public LRUCache(int capacity) {\n        this.capacity = capacity;\n        keyMap = new HashMap&lt;>();\n        dummy = new DNode(-1, -1);\n        tail = new DNode(-2, -2);\n        dummy.next = tail;\n        tail.pre = dummy;\n    }\n    \n    public int get(int key) {\n        DNode node = keyMap.getOrDefault(key, null);\n        if(node == null) {\n            return -1;\n        } \n\n        \/\/\u79fb\u52a8\u5230\u94fe\u8868\u5934\n        move2Head(node);\n        return node.value;\n    }\n    \n    public void put(int key, int value) {\n        DNode node = keyMap.getOrDefault(key, null);\n\n        if(node != null) {\n            node.value = value;\n            \/\/\u79fb\u52a8\u5230\u94fe\u8868\u5934\n            move2Head(node);\n        } else {\n\n            if (size + 1 > capacity) {\n                \/\/\u79fb\u9664\u6700\u540e\u4e00\u4e2a\n                removeTail();\n            }  else {\n                size++;\n            }\n\n            \/\/\u63d2\u5165\u5230\u94fe\u8868\u5934\n            DNode newNode = new DNode(key, value);\n            insert2Head(newNode);\n            keyMap.put(key, newNode);\n        }\n    }\n\n    private void insert2Head(DNode node) {\n        DNode temp = dummy.next;\n        dummy.next = node;\n        node.pre = dummy;\n        node.next = temp;\n        temp.pre = node;\n    }\n\n    private void move2Head(DNode node) {\n        DNode pTemp = node.pre;\n        DNode nTemp = node.next;\n        pTemp.next = nTemp;\n        nTemp.pre = pTemp;\n\n        insert2Head(node);\n    }\n\n    private void removeTail() {\n        DNode temp = tail.pre;\n        if (temp != dummy) {\n            DNode pTemp = temp.pre;\n            tail.pre = pTemp;\n            pTemp.next = tail;\n            \n            keyMap.remove(temp.key, temp);\n            temp.key = -3;\n            temp.value = -3;\n            temp.pre = null;\n            temp.next = null;\n        }\n    }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u5730\u5740\uff1a146.LRU\u7f13\u5b58 \u8bed\u8a00Java<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16,15],"tags":[26,17,25,18],"class_list":["post-318","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-15","tag-cache","tag-leetcode","tag-lru","tag-18"],"blocksy_meta":{"styles_descriptor":{"styles":{"desktop":"","tablet":"","mobile":""},"google_fonts":[],"version":6}},"_links":{"self":[{"href":"https:\/\/dmoe.nicolite.cn\/index.php?rest_route=\/wp\/v2\/posts\/318","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dmoe.nicolite.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dmoe.nicolite.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dmoe.nicolite.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dmoe.nicolite.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=318"}],"version-history":[{"count":0,"href":"https:\/\/dmoe.nicolite.cn\/index.php?rest_route=\/wp\/v2\/posts\/318\/revisions"}],"wp:attachment":[{"href":"https:\/\/dmoe.nicolite.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=318"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dmoe.nicolite.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=318"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dmoe.nicolite.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=318"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}