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

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    int capacity, size;
    DLinkedList head, tail;
    HashMap<Integer, DLinkedList> map;
    public int[] LRU (int[][] operators, int k) {
        head = new DLinkedList();
        tail = new DLinkedList();
        head.next = tail;
        tail.prev = head;
        size = 0;
        this.capacity = k;
        map = new HashMap<>();

        int len = (int) Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        for(int i = 0, j = 0; i <operators.length; i++){
            if(operators[i][0] == 1){
                set(operators[i][1], operators[i][2]);
            }else{
                res[j++] = get(operators[i][1]);
            }
        }
        return res;
    }
    
    public int get(int key) {
        DLinkedList node = map.get(key);
        if(node == null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }
    
    public void set(int key, int value) {
        DLinkedList node = map.get(key);
        if(node == null){
            node = new DLinkedList(key, value);
            map.put(key, node);
            addToHead(node);
            size++;
            if(size > capacity){
                DLinkedList cur_tail = removeTail();
                map.remove(cur_tail.key);
                size--;
            }
        }else{
            removeNode(node);
            node = new DLinkedList(key, value);
            map.put(key, node);
            addToHead(node);
        }

    }
    public void moveToHead(DLinkedList node){
        removeNode(node);
        addToHead(node);
    }
    public void removeNode(DLinkedList node){
        node.next.prev = node.prev;
        node.prev.next = node.next;

    }
    public void addToHead(DLinkedList node){
        head.next.prev = node;
        node.next = head.next;
        node.prev = head;
        head.next = node;
    }
    public DLinkedList removeTail(){
        DLinkedList tail_cur = tail.prev;
        removeNode(tail_cur);
        return tail_cur;
    }
    

    class DLinkedList{
        int key, value;
        DLinkedList next, prev;
        public DLinkedList(){

        }
        public DLinkedList(int key_, int value_){
            key = key_;
            value = value_;
        }
    }
}