题解 | #数组中的逆序对#

import java.util.*;

class Lru{
    class Node {
    int key,val;
    Node pre,next;
    Node(){}
    Node(int key,int val){
        this.key = key;
        this.val = val;
    }
    }
    int maxsize;
    HashMap<Integer,Node> cache = new HashMap <> ( );
    Node head,tail;
    Lru(int k){
        maxsize = k;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    void put(int key,int val){
        //判断当前key是否存在
        Node node = cache.getOrDefault(key,null);
        if(node != null){ //当结点存在的时候
            cache.get(key).val = val;
            //从原来的位置移除
            node.pre.next = node.next;
            node.next.pre = node.pre;
            //移动到链表的头部
            move(node);
        }
        else {
            if(maxsize <= cache.size()){
                remove();
            }
           node = new Node(key,val);
           cache.put(key,node);
           move(node);
        }
    }
    void remove(){
       if(cache.size() == 0 || tail.pre.pre == null)return;
       int key  = tail.pre.key;
       cache.remove(key);
       tail.pre.pre.next = tail;
       tail.pre = tail.pre.pre;
        //等待垃圾回收期自动回收。
       
    }
    void move(Node node){
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre= head;
    }
    int get(int key){
          Node node = cache.getOrDefault(key,null);
          if(node == null)return -1;
          node.pre.next = node.next;
          node.next.pre = node.pre;
        //移动到链表的头部
          move(node);
          return node.val;
    }
}

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        if(operators == null || operators.length ==0 ||k <=0)return null;
        // write code here
        Lru myLru = new Lru(k);
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0;i<operators.length;i++){
            int [] op = operators[i];
            if(op[0] == 1){
                myLru.put(op[1],op[2]);
            }
            else if(op[0] == 2){
                res.add(myLru.get((op[1])));
            }
        }
        int[] ans = new int[res.size()];
        for(int i = 0;i<res.size();i++){
            ans[i] = res.get(i);
        }
        return ans;
         
    }
}