链表篇
灵神题解
class LRUCache {private static class Node{int key,value;Node prev,next;Node (int k,int v){key=k;value=v;}}private final int capacity;//哨兵节点private final Node dummy=new Node(0,0);private final Map<Integer,Node> keyToNode =new HashMap<>();public LRUCache(int capacity) {this.capacity=capacity;dummy.prev=dummy;dummy.next=dummy;}public int get(int key) {Node node=getNode(key);return node!=null?node.value:-1;}public void put(int key, int value) {Node node=getNode(key);//有书则更新if(node!=null){node.value=value;return;}node=new Node(key,value);keyToNode.put(key,node);//放在最上面pushFront(node);//书太多了if(keyToNode.size()>capacity){Node backNode=dummy.prev;keyToNode.remove(backNode.key);//去掉最后一本书remove(backNode);}}//取节点private Node getNode(int key){//没有这本书if(!keyToNode.containsKey(key)){return null;}//有这本书Node node=keyToNode.get(key);//抽出来remove(node);//放在最上面pushFront(node);return node;}//删除一个节点（抽出一本书）private void remove(Node x){x.prev.next=x.next;x.next.prev=x.prev;}//链表头添加节点private void pushFront(Node x){x.prev=dummy;x.next=dummy.next;x.prev.next=x;x.next.prev=x;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/
背题
