“`”<\/p>\n
\u8003\u5bdf\u70b9\uff1aLFU Cache<\/p>\n
<pre><code>public class LFUCache {private class Node{ int value; ArrayList<Integer> set; Node prev; Node next; public Node (int value ){ this.value = value; this.set = new ArrayList<Integer> (); this.prev = null; this.next = null; }}private class item{ int key; int value; Node parent ; public item(int key ,int value, Node parent){ this.key = key ; this.value = value; this.parent = parent; }} private HashMap<Integer, item> map;private Node head,tail;private int capacity;\/\/ @param capacity, an integerpublic LFUCache(int capacity) { \/\/ Write your code here this.capacity = capacity; this.map = new HashMap <Integer,item> (); this.head = new Node (0); this.tail = new Node(Integer.MAX_VALUE); head.next = tail; tail.prev = head; }\/\/ @param key, an integer\/\/ @param value, an integer\/\/ @return nothingpublic void set(int key, int value) { \/\/ Write your code here if (get(key) != -1 ) { map.get(key).value = value; return ; } if (map.size() == capacity ){ getLFUitem(); } Node newpar = head.next; if ( newpar.value != 1){ newpar = getNewNode(1,head,newpar); } item curitem = new item(key,value,newpar); map.put(key,curitem); newpar.set.add(key); return; }public int get(int key) { \/\/ Write your code here if (!map.containsKey(key)){ return -1; } item cur = map.get(key); Node curpar = cur.parent; if (curpar.next.value == curpar.value + 1){ cur.parent= curpar.next; cur.parent.set.add(key); }else{ Node newpar =getNewNode(curpar.value + 1,curpar,curpar.next); cur.parent = newpar; newpar.set.add(key); } curpar.set.remove(new Integer(key)); if(curpar.set.isEmpty()){ deleteNode(curpar); } return cur.value;}private Node getNewNode (int value ,Node prev , Node next){ Node temp = new Node(value); temp.prev = prev; temp.next = next; prev.next = temp; next.prev = temp; return temp;}private void deleteNode(Node temp){ temp.prev.next = temp.next; temp.next.prev = temp.prev; return ;}private void getLFUitem(){ Node temp = head.next; int LFUkey = temp.set.get(0); temp.set.remove(0); map.remove(LFUkey); if (temp.set.isEmpty()){ deleteNode(temp); } return;}<\/code><\/pre><\/p>\n
<\/p>\n
<pre><code> "“`
\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
“`” \u8003\u5bdf\u70b9\uff1aLFU Cache <pre><code>pu […]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[],"class_list":["post-45356","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45356","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/comments?post=45356"}],"version-history":[{"count":1,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45356\/revisions"}],"predecessor-version":[{"id":45357,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45356\/revisions\/45357"}],"wp:attachment":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/media?parent=45356"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/categories?post=45356"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/tags?post=45356"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}