题解 | LRU Cache

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    static class LRU {
        static int cap;
        static Node dummy;

        static Map<Integer, Node> cache = new HashMap<>();


        LRU(int n) {
            cap = n;
            dummy = new Node(-1, -1);
            dummy.next = dummy;
            dummy.pre = dummy;
        }


        int get(int key) {
            Node node = getNode(key);
            if (node == null) return -1;
            return node.val;
        }


        void set(int key, int val) {
           
           
            if (cache.containsKey(key)) { // 多读题 如果存在 不算被使用
                Node node = cache.get(key);
                node.val = val;
                return;
            }
             //System.out.println("set:" + key + " size:" + cache.size());
            Node node = new Node(key, val);
            cache.put(key, node);
            moveToHead(node);
            //System.out.println("size:" + cache.size() + " cap:" + cap);
            if (cache.size() > cap) {
                Node last = dummy.pre;
                cache.remove(last.key);
                removeNode(last);
                
            }
        }


        static Node getNode(int key) {
            if (cache.containsKey(key)) {
                Node node = cache.get(key);
                removeNode(node);
                moveToHead(node);
                return node;
            }
            return null;
        }


        private static void removeNode(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        private static void moveToHead(Node node) {
            node.pre = dummy;
            node.next = dummy.next;
            node.pre.next = node;
            node.next.pre = node;
            
          
        }


    }


    static class Node {
        int key;
        int val;
        Node next;
        Node pre;

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



    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        //System.out.println("size:" + n);
        LRU lru = new LRU(n);
        in.nextLine();
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String line = in.nextLine();
            //System.out.println(line);
            String[] ops = line.split(" ", -1);
            if (ops[0].equals("p")) {
                int key = Integer.parseInt(ops[1]);
                int val = Integer.parseInt(ops[2]);
                lru.set(key, val);
            } else {
                int key = Integer.parseInt(ops[1]);
                int ans = lru.get(key);
                System.out.println(ans);
            }
        }
    }
}