@@ -0,0 +1,2156 @@
+// LRU cache with O(1) time for %60get()%60 and %60put()%60 methods.%0A// Idea is using doubly-linked list for values, which aare stored as %60DLinkedNode%60.%0Aclass LRUCache %7B%0A  static class DLinkedNode %7B%0A    int key;%0A    int value;%0A    DLinkedNode pre;%0A    DLinkedNode post;%0A  %7D%0A%0A  /** Always add the new node right after head */%0A  private void addNode(DLinkedNode node) %7B%0A    node.pre = head;%0A    node.post = head.post;%0A%0A    head.post.pre = node;%0A    head.post = node;%0A  %7D%0A%0A  /** Remove an existing node from the linked list */%0A  private void removeNode(DLinkedNode node) %7B%0A    DLinkedNode pre = node.pre;%0A    DLinkedNode post = node.post;%0A%0A    pre.post = post;%0A    post.pre = pre;%0A  %7D%0A%0A  /** Move certain node in between to the head */%0A  private void moveToHead(DLinkedNode node) %7B%0A    this.removeNode(node);%0A    this.addNode(node);%0A  %7D%0A%0A  /** Pop the current tail */%0A  private DLinkedNode popTail() %7B%0A    DLinkedNode res = tail.pre;%0A    this.removeNode(res);%0A    return res;%0A  %7D%0A%0A  private HashMap%3CInteger, DLinkedNode%3E cache = new HashMap%3CInteger, DLinkedNode%3E();%0A  private int count;%0A  private int capacity;%0A  private DLinkedNode head, tail;%0A%0A  public LRUCache(int capacity) %7B%0A    this.count = 0;%0A    this.capacity = capacity;%0A%0A    head = new DLinkedNode();%0A    head.pre = null;%0A%0A    tail = new DLinkedNode();%0A    tail.post = null;%0A%0A    head.post = tail;%0A    tail.pre = head;%0A  %7D%0A%0A  public int get(int key) %7B%0A    DLinkedNode node = cache.get(key);%0A    if (node == null) return -1; // should raise exception here%0A    // move the accessed node to the head;%0A    this.moveToHead(node);%0A    return node.value;%0A  %7D%0A%0A%0A  public void put(int key, int value) %7B%0A    DLinkedNode node = cache.get(key);%0A    if (node == null) %7B%0A      DLinkedNode newNode = new DLinkedNode();%0A      newNode.key = key;%0A      newNode.value = value;%0A%0A      this.cache.put(key, newNode);%0A      this.addNode(newNode);%0A%0A      ++count;%0A%0A      if (count %3E capacity) %7B%0A        // pop the tail%0A        DLinkedNode tail = this.popTail();%0A        this.cache.remove(tail.key);%0A        --count;%0A      %7D%0A    %7D else %7B%0A      // update the value.%0A      node.value = value;%0A      this.moveToHead(node);%0A    %7D%0A  %7D%0A%7D%0A

add solution