題目

解題

采用哈希表+雙向鏈表的數(shù)據(jù)結(jié)構(gòu)，雙向鏈表創(chuàng)建虛擬頭結(jié)點、虛擬尾結(jié)點，用來查詢最近最少使用的元素，剛剛使用或添加的元素，放到虛擬頭結(jié)點后面，淘汰掉虛擬尾結(jié)點的前一個元素

class LRUCache {
    Map<Integer,Node> map;
    int capacity;
  // 虛擬頭結(jié)點
    Node first;
 // 虛擬尾結(jié)點
    Node last;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        // 容量
        this.capacity = capacity;

        first = new Node();
        last = new Node();
        
        first.next = last;
        last.prev = first;
    }
    
    public void addFirstNode(Node node) {
        node.next = first.next;
        first.next.prev = node;

        node.prev = first;
        first.next = node;
    }

    public void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;

        removeNode(node);
        addFirstNode(node);

        return node.value;
    }
    
    public void put(int key, int value) {
         Node node = map.get(key);
         if (node != null) {
             node.value = value;
             removeNode(node);
             addFirstNode(node);
         } else {
             if (map.size() == capacity) {
                 map.remove(last.prev.key);
                 removeNode(last.prev);
             }
             map.put(key, node = new Node(key,value));
             addFirstNode(node);
         }
    }

    public static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node (int key, int value) {
            this.key = key;
            this.value = value;
        }
        public Node() {}
    }
}