牛客题霸NC93-设计LRU缓存结构-题解

经典的LRU缓存数据结构设计题，用HashMap和自定义双端队列结构实现，时间复杂度o(1)，空间复杂度o(n)。

import java.util.*;

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    class DNode{
        DNode next;
        DNode prev;
        int val;
        int key;
        public DNode(int val){
            this.val = val;
        }

        public DNode(int key, int val){
            this.key = key;
            this.val = val;
        }
    }

    public Solution(){
        head = new DNode(0);
        tail = new DNode(0);
        head.next = tail;
        tail.next = head;
        size = 0;
        map = new HashMap<>();
    }

    DNode head;
    DNode tail;
    int size;
    Map<Integer, DNode> map;
    int capacity;

    private void set(int key, int val){
        if (map.containsKey(key)){
            DNode node = map.get(key);
            node.val = val;
            delete(node);
            moveToFirst(node);
        }else{
            if(size == capacity){
                DNode last = tail.prev;
                delete(last);
                map.remove(last.key);
                size--;
            }
            DNode node = new DNode(key, val);
            map.put(key, node);
            size++;
            moveToFirst(node);
        }
    }

    private int get(int key){
        if (map.containsKey(key)){
            DNode node = map.get(key);
            delete(node);
            moveToFirst(node);
            return node.val;
        }else{
            return -1;
        }
    }

    private void delete(DNode node){
        DNode prev = node.prev;
        DNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }

    private void moveToFirst(DNode node){
        DNode next = head.next;
        head.next = node;
        node.next = next;
        next.prev = node;
        node.prev = head;
    }

    public int[] LRU (int[][] operators, int k) {
        // write code here
        capacity = k;
        List<Integer> ans = new ArrayList<>();
        for (int[] operator : operators){
            if (operator[0] == 1){
                set(operator[1], operator[2]);
            }else{
                int temp = get(operator[1]);
                ans.add(temp);
            }
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}