🌕 146. LRU 缓存

难度: 🌕

问题描述

---

解法

class LRUCache {
    int size; // 当前节点数，排除虚拟头尾节点
    int capacity; // 容量
    Node head; // 虚拟头结点
    Node tail; // 新节点插入尾部，移除时优先从头部删除
    HashMap<Integer, Node> map; // 快速通过 key 定位到 Node

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        head.next = tail;
        tail.prev = head;
        this.map = new HashMap<>();
    }
    
    public int get(int key) {
        if(!map.containsKey(key)) {
            return -1; // 不存在当前 key
        }
        Node select = map.get(key); // 要查找的节点
        // 一经找到，就需要从原有位置中移除，插入到尾部
        delete(select);
        insertAtPrev(tail, select);
        return select.val;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)) {
            Node select = map.get(key);
            select.val = value; // 更新值
            get(key); // 通过 get() 将 select 节点移到最新
        } else {
            // 需要插入当前节点
            Node insert = new Node(key, value);
            // 判断当前是否达到最大容量，若达到，则需要删除最久未使用的节点
            if(size == capacity) {
                map.remove(head.next.key); // 从 map 中删除
                delete(head.next);
                size --;
            }
            // 插入新节点
            insertAtPrev(tail, insert);
            map.put(key, insert);
            size ++;
        }
    }

    // 工具类
    private void insertAtNext(Node cur, Node insert) {
        Node next = cur.next;
        cur.next = insert;
        insert.prev = cur;
        insert.next = next;
        next.prev = insert;
    }
    private void insertAtPrev(Node cur, Node insert) {
        Node prev = cur.prev;
        insertAtNext(prev, insert);
    }
    private void delete(Node cur) {
        Node prev = cur.prev;
        Node next = cur.next;
        prev.next = next;
        next.prev = prev;
    }
}

class Node { // 构造双向链表节点类
    int key;
    int val;
    Node prev;
    Node next;
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

---

输出