146. LRU 缓存

难度: 中等

来源: 每日一题 2023.09.24

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

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 <= 10^5
最多调用 2 * 10^5 次 get 和 put

class LRUCache {

    public LRUCache(int capacity) {

    }
    
    public int get(int key) {

    }
    
    public void put(int key, int value) {
 
    }
}

分析与题解

双向链表 + HashMap

LRU这个题目是一个老生常谈的问题, 很多面试过程中都会遇到, 并且这个题对于新手来说还是有一定难度的.

像这个LRU算法, 我们主要关注点应该在于我们到底应该构建什么的结构来进行存储和保证我们的快速读取.

这个题目我也是做了最少10+遍了.. 所以就很明白使用双向链表和HashMap的数据结构来解决这个问题.

使用HashMap结构的原因主要是可以快速查找节点.

使用双向链表结构主要用于便于方便查找节点的前后节点.

首先, 我们先构建双向链表的节点类LRUNode.

class LRUNode {
    int key;
    int value;
    LRUNode pre;
    LRUNode next;
    LRUNode() {
    }
    LRUNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

然后, 我们通过双向链表头部节点header和尾部节点tail, 这两个节点只是作为一个标志位, 没有实际标识含义, 所有的节点都会在这两个节点中间.

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.count = 0;
    header = new LRUNode();
    tail = new LRUNode();
    header.next = tail;
    tail.pre = header;
}

我们知道LRU算法遵循着最近最少使用的数据原则, 所以当我们在get某一个数据的时候, 我们要把它放在双向链表的最前部. 这时候我们就需要两个操作.

把节点从原来的位置删除.

public void deleteNode(LRUNode node) {
    node.pre.next = node.next;
    node.next.pre = node.pre;
}

把节点插到头部.

public void nodeToHeader(LRUNode node) {
    node.next = header.next;
    header.next.pre = node;
    node.pre = header;
    header.next = node;
}

然后, get方法中除了 把节点从原来的位置删除 和 把节点插到头部 之外, 只需要正常的返回对应的数据即可.

public int get(int key) {
    LRUNode node = cache.get(key);
    if (node != null) {
        // 调整Node位置
        deleteNode(node);
        nodeToHeader(node);
        return node.value;
    } else {
        return -1;
    }
}

对于 put 方法, 主要有两种情况.

当前已经存在 key 的数据了, 那么我们只需要更新 value 的值, 并且把节点移动到双向链表的头部即可.

LRUNode node = cache.get(key);
if (node != null) {
    // 更新数据
    node.value = value;
    // 调整Node位置
    deleteNode(node);
    nodeToHeader(node);
}

如果当前不存在 key 的相关数据, 那我们需要创建新的节点, 同时判断当前的总节点数是否超出预设值, 如果超出, 就从尾部删除最后一个节点. 没超出则不进行删除操作, 当然了, 新增的节点不在需要移动节点的操作, 只需要把新增节点放在双向链表的头部即可.
```
LRUNode newNode = new LRUNode(key, value);
if (this.count < this.capacity) {
    count++;
    cache.put(key, newNode);
    nodeToHeader(newNode);
} else {
    LRUNode deleteNode = deleteLastNode();
    cache.remove(deleteNode.key);
    nodeToHeader(newNode);
    cache.put(key, newNode);
}
```

下面让我们一起看看整体的题解过程吧.

class LRUCache {

    class LRUNode {
        int key;
        int value;
        LRUNode pre;
        LRUNode next;
        LRUNode() {
        }
        LRUNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 构建缓存数组和链表结构
    HashMap<Integer, LRUNode> cache = new HashMap<>();
    LRUNode header, tail;
    int capacity, count;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        header = new LRUNode();
        tail = new LRUNode();
        header.next = tail;
        tail.pre = header;
    }

    public int get(int key) {
        LRUNode node = cache.get(key);
        if (node != null) {
            // 调整Node位置
            deleteNode(node);
            nodeToHeader(node);
            return node.value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        LRUNode node = cache.get(key);
        if (node != null) {
            // 更新数据
            node.value = value;
            // 调整Node位置
            deleteNode(node);
            nodeToHeader(node);
        } else {
            LRUNode newNode = new LRUNode(key, value);
            if (this.count < this.capacity) {
                count++;
                cache.put(key, newNode);
                nodeToHeader(newNode);
            } else {
                LRUNode deleteNode = deleteLastNode();
                cache.remove(deleteNode.key);
                nodeToHeader(newNode);
                cache.put(key, newNode);
            }
        }
    }

    public void deleteNode(LRUNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public void nodeToHeader(LRUNode node) {
        node.next = header.next;
        header.next.pre = node;
        node.pre = header;
        header.next = node;
    }

    public LRUNode deleteLastNode() {
        LRUNode node = tail.pre;
        deleteNode(node);
        return node;
    }
}

/**
* 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);
*/

复杂度分析:

时间复杂度: O(1), 通过HashMap和双向链表的配合,查找时间复杂度为O(1)
空间复杂度: O(n), HashMap和双向链表空间复杂度与所有节点的数量成线性关系.

结果如下所示.

得不到的永远是骚栋

146. LRU 缓存

146. LRU 缓存

难度: 中等

来源: 每日一题 2023.09.24

分析与题解

460. LFU 缓存(看官方题解,已解)

2591. 将钱分给最多的儿童

神经骚栋

Comments | 0 条评论

得不到的永远是骚栋