【算法】【线性表】【链表】LRU 缓存2

1  题目

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

2  解答

上次我写了一个，今儿再写一个比较清晰的，主要思路就是：get 的时候，如果存在的话，要把它移动到头部，put的时候如果 key 存在，更新value后要把它移动到头部，不存在的话，要看删不删旧的，并把新的添加到头部：

public class LRUCache {
    // 容量大小
    private int capacity;
    // 链表头节点 方便处理
    private LRUNode head;
    // 某个元素存在或者不存在 所以需要 map 进行判断
    private Map<Integer, LRUNode> map;
    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("容量不能小于0");
        this.capacity = capacity;
        this.head = new LRUNode(0, 0);
        this.map = new HashMap<>(capacity);
        this.head.preNode = this.head;
        this.head.nextNode = this.head;
    }
    // 链表节点
    class LRUNode {
        private int key;
        private int value;
        private LRUNode preNode;
        private LRUNode nextNode;

        public LRUNode(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public LRUNode(int key, int value, LRUNode preNode) {
            this.key = key;
            this.value = value;
            this.preNode = preNode;
        }

        public LRUNode(int key, int value, LRUNode preNode, LRUNode nextNode) {
            this.key = key;
            this.value = value;
            this.preNode = preNode;
            this.nextNode = nextNode;
        }
    }

    public int get(int key) {
        // 不存在直接返回 -1
        LRUNode node = map.get(key);
        if (Objects.isNull(node)) {
            return -1;
        }
        // 就一个元素的话或者它本身就在第一个 不需要移动
        int res = node.value;
        if (map.size() <= 1) return res;
        if (node.preNode == this.head) return res;
        // 说明大于1个元素并且它还不在第一的位置，就需要把它移动到头部去
        // 为什么需要移动？因为put满的情况下要删除最不常用的 所以要移动保证删除的时候是O(1)
        LRUNode preNode = node.preNode;
        // 因为有头节点的存在 所以这个前置节点一定不为空
        LRUNode nextNode = node.nextNode;
        // 将当前要移动的节点 先释放出来
        nextNode.preNode = preNode;
        preNode.nextNode = nextNode;
        // 该节点的前后都重新指向
        node.preNode = this.head;
        node.nextNode = head.nextNode;
        // 插进来
        head.nextNode.preNode = node;
        head.nextNode = node;
        // 返回结果
        return res;
    }

    public void put(int key, int value) {
        LRUNode node = map.get(key);
        // 存在的话，直接更新
        if (Objects.nonNull(node)) {
            node.value = value;
            // 这里很重要 因为存在更新完value 要把这个节点释放出来，下边要对这个节点移动到头部
            LRUNode preNode = node.preNode;
            LRUNode nextNode = node.nextNode;
            nextNode.preNode = preNode;
            preNode.nextNode = nextNode;
        } else {
            // 没有的话 说明不存在需要把它插进来
            // 先判断满没满
            if (map.size() < this.capacity) {
                // 没满直接头插法把它带进来
                node = new LRUNode(key, value);
                this.map.put(key, node);
            } else {
                // 满了的话 需要移出尾部
                node = this.head.preNode;
                map.remove(node.key);
                node.key = key;
                node.value = value;
                map.put(key, node);
                LRUNode lastPreNode = node.preNode;
                lastPreNode.nextNode = this.head;
                this.head.preNode = lastPreNode;
            }
        }

        // node即为需要插入到头部的节点
        // 重新赋值 node 信息
        node.nextNode = this.head.nextNode;
        node.preNode = this.head;
        // 放到头部
        LRUNode headNextNode = this.head.nextNode;
        headNextNode.preNode = node;
        this.head.nextNode = node;
    }

    // 打印链表信息
    @Override
    public String toString() {
        LRUNode node = this.head.nextNode;
        StringBuilder builder = new StringBuilder();
        while (node != this.head) {
            builder.append(node.key).append("(").append(node.value).append(")");
            node = node.nextNode;
        }
        return builder.toString();
    }
}

打败的人数有点少哇，哈哈哈，上次写的那个一会儿moveLast 一会儿 moveFirst 的不够精简，这次写的简单点，有理解不对的地方欢迎指正哈。