力扣146. LRU 缓存

Problem: 146. LRU 缓存

题目描述

思路

主要说明大致思路，具体实现看代码。

1.为了实现题目中的O(1)时间复杂度的get与put方法，我们利用哈希表和双链表的结合，将key作为键，对应的链表的节点作为值（也就是在此处我们用一个节点类作为值）；
2.定义双链表的节点类，其中包含每次put的键与对应的值，还包括前驱、后驱指针；
3.编写双链表的实现类，并实现：

3.1.初始化一个双链表(创建虚拟头、尾节点；由于我们要实现将最就不使用的节点删除，我们在此使用尾插法即每次链表尾部位最近使用的，表头为最久不适用的)；
3.2.实现尾插一个节点；
3.3.实现删除一个给定的节点；
3.4.实现从表头删除一个节点（删除最久不使用的节点）
3.5.返回链表的长度

4.实现LRUCache类：

4.1. 创建哈希表map与双链表cache；
4.2. 为了不直接在get与put中对map与cache操作带来麻烦（主要操作是同步在mao中添加key同时在cache中增、删、改对应节点的值），我们封装实现一些API（具体操作实现看代码）
4.3. 实现get与put方法（直接看代码）

复杂度

时间复杂度:

$O(n)$;其中$n$为要操作的次数

空间复杂度:

$O(n)$

Code

/**
 * Node class
 */
class Node {
   
    public int key;
    public int val;
    public Node next;
    public Node prev;

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