题解 | #设计LRU缓存结构#

import java.util.*;


public class Solution {

     HashMap<Integer,MyNode> map;
     int size;
     MyNode begin = new MyNode(-1);
     MyNode end = new MyNode(-1);
    public Solution(int capacity) {
        // write code here
        map = new HashMap<Integer,MyNode>();
        size = capacity;
        begin.next = end;
        end.last = begin;
    }

    public int get(int key) {
        // write code here
        if(map.containsKey(key)){
             MyNode temp = map.get(key);
             temp.next.last = temp.last;
             temp.last.next = temp.next;
             temp.last = end.last;
             end.last.next = temp;
             end.last = temp;
             temp.next = end;
             return temp.val;
        }
        return -1;
    }

    public void set(int key, int value) {
        // write code here
        if(map.containsKey(key)){
             MyNode one = map.get(key);
             one.val = value;
             one.last.next = one.next;
             one.next.last = one.last;
             one.last = end.last;
             end.last.next = one;
             end.last = one;
             one.next = end;
        }else{
             if(map.size() < size){
             MyNode one = new MyNode(value,key,end,end.last);
             map.put(key,one);
             one.last = end.last;
             end.last.next = one;
             end.last = one;
             one.next = end;
          }else{
             MyNode one = new MyNode(value,key,end,end.last);
             map.put(key,one);
             one.last = end.last;
             end.last.next = one;
             end.last = one;
             one.next = end;
             MyNode two = map.remove(begin.next.key);
             begin.next = two.next;
             two.next.last = begin;
          }
        }
    }
    class MyNode{
         MyNode next;
         MyNode last;
         int key;
         int val;
         public MyNode(int val){
              this.val = val;
         }
         public MyNode(int val,int key){
              this.val = val;
              this.key = key;
         }
         public MyNode(int val,int key , MyNode next,MyNode last){
              this.val = val;
              this.key = key;
              this.next = next;
              this.last = last;
         }
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */