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

哈希表 + 双向链表

原理：类似力扣 146. LRU 缓存机制
推荐看这个讲解：https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

代码

import java.util.*;

public class Solution {
    private class Node {
        Node pre, next;
        int key, value;
        private Node(int k, int v) {
            this.key = k;
            this.value = v;
        } 
    }

    private class DoubleList {
        Node head = new Node(0, 0);
        Node tail = new Node(0, 0);
        int size;

        private DoubleList() {
            head.next = tail;
            tail.pre = head;
            size = 0;
        }

        private void addFirst(Node n) {
            Node headNext = head.next;
            head.next = n;
            n.pre = head;
            n.next = headNext;
            headNext.pre = n;
            size++;
        }

        private void remove(Node n) {
            n.pre.next = n.next;
            n.next.pre = n.pre;
            size--;
        }

        private Node romveLast() {
            Node last = tail.pre;
            remove(last);
            return last;
        }

        private int size() {
            return size;
        }
    }

    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        this.cap = k;
        map = new HashMap<>();
        cache = new DoubleList();

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < operators.length; i++) {
            if (operators[i][0] == 1) set(operators[i][1], operators[i][2]);
            else if (operators[i][0] == 2) {
                int res = get(operators[i][1]);
                list.add(res);
            }
        }

        int[] out = new int[list.size()];
        for (int i = 0; i < list.size(); i++) out[i] = list.get(i);
        return out;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        int val = map.get(key).value;
        set(key, val);
        return val;
    }

    public void set(int key, int val) {
        Node x = new Node(key, val);
        if (map.containsKey(key)) {
            cache.remove(map.get(key));
            cache.addFirst(x);
            map.put(key, x);
        } else {
            if (cap == cache.size()) {
                Node last = cache.romveLast();
                map.remove(last.key);
            }
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}