【hot100-java】LRU 缓存

链表篇

灵神题解

 

 

1. class LRUCache {
2.     private static class Node{
3.         int key,value;
4.         Node prev,next;
6.         Node (int k,int v){
7.             key=k;
8.             value=v;
9.         }
10.     }
11.     private final int capacity;
12.     //哨兵节点
13.     private final Node dummy=new Node(0,0);
14.     private final Map<Integer,Node> keyToNode =new HashMap<>();
16.     public LRUCache(int capacity) {
17.         this.capacity=capacity;
18.         dummy.prev=dummy;
19.         dummy.next=dummy;
20.     }
21.    
22.     public int get(int key) {
23.            Node node=getNode(key);
24.            return node!=null?node.value:-1;
25.     }
26.    
27.     public void put(int key, int value) {
28.           Node node=getNode(key);
29.           //有书则更新
30.           if(node!=null){
31.             node.value=value;
32.             return;
33.           }
34.           node=new Node(key,value);
35.           keyToNode.put(key,node);
36.           //放在最上面
37.           pushFront(node);
38.           //书太多了
39.           if(keyToNode.size()>capacity){
40.               Node backNode=dummy.prev;
41.               keyToNode.remove(backNode.key);
42.               //去掉最后一本书
43.               remove(backNode);
44.           }
45.     }
47.     //取节点
48.     private Node getNode(int key){
49.         //没有这本书
50.         if(!keyToNode.containsKey(key)){
51.             return null;
52.         }
53.         //有这本书
54.         Node node=keyToNode.get(key);
55.         //抽出来
56.         remove(node);
57.         //放在最上面
58.         pushFront(node);
59.         return node;
60.     }
62.     //删除一个节点（抽出一本书）
63.     private void remove(Node x){
64.         x.prev.next=x.next;
65.         x.next.prev=x.prev;
66.     }
68.     //链表头添加节点
69.     private void pushFront(Node x){
70.         x.prev=dummy;
71.         x.next=dummy.next;
72.         x.prev.next=x;
73.         x.next.prev=x;
74.     }
75. }
77. /**
78. * Your LRUCache object will be instantiated and called as such:
79. * LRUCache obj = new LRUCache(capacity);
80. * int param_1 = obj.get(key);
81. * obj.put(key,value);
82. */

复制代码

 
背题

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。