视频讲解

[大圣干嘛呢] LRUCache (LRU缓存) -- LeetCode 146_哔哩哔哩_bilibili

要点

1. 使用双向链表：比单向链表更方便，例如能通过 tail 找到尾节点的前一个结点
2. 使用 HashMap：通过 key 查 value

代码

class LinkNode {

    int key;
    int val;
    LinkNode front;
    LinkNode next;
    public LinkNode (int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class LRUCache {

    int capacity;
    Map<Integer, LinkNode> map = new HashMap<>();
    LinkNode head = new LinkNode(0, 0);
    LinkNode tail = new LinkNode(0, 0);

    

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.front = head;
    }

    /**
     * 使用 map 查询 key，如果发现存在，将 key 对应的 node 移到最前面 
     */
    public int get(int key) {
        if (map.containsKey(key)) {
            LinkNode node = map.get(key);
            moveNodeToTop(node);
            return node.val;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (!map.containsKey(key)) { // map 里不存在该 key
            if (map.size() == capacity) {
                deleteLastNode();
            }
            LinkNode temp = head.next;
            LinkNode newNode = new LinkNode(key, value);
            head.next = newNode;
            newNode.front = head;
            newNode.next = temp;
            temp.front = newNode;
            map.put(key, newNode); // 分析一下这里为什么 value 是 newNode
        } else { // map 里存在该 key
            LinkNode node = map.get(key);
            node.val = value;
            moveNodeToTop(node);
        }
    }

    /**
     * 删除最后一个节点
     */
    private void deleteLastNode() {
        LinkNode lastNode = tail.front;
        lastNode.front.next = tail;
        tail.front = lastNode.front;
        map.remove(lastNode.key);
    }

    /**
     * 把某一个节点移到链表最前面
     */
     private void moveNodeToTop(LinkNode node) {
         // 把 node 前后连上
         node.front.next = node.next;
         node.next.front = node.front;
         LinkNode temp = head.next;
         head.next = node;
         node.front = head;
         node.next = temp;
         temp.front = node;
     }

}