[LeetCodeNote][java][HashMap|手写双向链表]146-LRU缓存机制

146. LRU 缓存机制 - 力扣（LeetCode） (leetcode-cn.com)

•  题目描述：

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
 

进阶：你是否可以在 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

先扔题解！

class LRUCache {

    class DoubleLink{
        int key;
        int value;

        DoubleLink prev;
        DoubleLink next;

        DoubleLink(){};
        DoubleLink(int key,int value){
            this.key=key;
            this.value=value;
        }
    }
    
    int size;
    int capacity;
    Map lru = new HashMap();
    DoubleLink head,tail;
    public LRUCache(int capacity) {
        this.size=0;
        this.capacity=capacity;
        head = new DoubleLink();
        tail = new DoubleLink();
        head.next=tail;
        tail.prev=head;
        
    }
    
    public int get(int key) {
        DoubleLink x = lru.get(key);
        if(x==null) return -1;
        else{
            moveTohead(x);
            return x.value;
        }
    }
    
    public void put(int key, int value) {
        DoubleLink x = lru.get(key);
        if(x!=null){
            x.value=value;
            moveTohead(x);
        }
        else{
            DoubleLink newnode = new DoubleLink(key,value);
            lru.put(key,newnode);
            addTohead(newnode);
            size++;
            if(size>capacity){
                delettail();
                size--;
            }
        }
    }

    public void addTohead(DoubleLink node){
        node.prev=head;
        node.next=head.next;
        head.next.prev=node;
        head.next=node;
        
    }
    public void moveTohead(DoubleLink node){
        node.next.prev=node.prev;
        node.prev.next=node.next;
        addTohead(node);
    }

　　//delettail函数和官方题解有差别
　　//官方题解返回了DoubleLink类型的node,并在put函数的else分支下使用HashMap的remove方法进行删除
　　//我暂时不明白有什么区别，姑且把删除放在了方法里。
　　
    public void delettail(){
        DoubleLink node=tail.prev;
        node.next.prev=node.prev;
        node.prev.next=node.next;
        lru.remove(node.key);
        
    }
}

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

 先碎碎念一下思路！

最开始拿到题发现了key和value肯定是想到了Map，但是对于LRU机制中所实现的排序思考了好一会儿，想了半天是不是能用Map的key一举解决。

//这里记录一下：keyvalue的模式识别意识是有了的！很好！

//因为map可以O（1）时间内由key找到value

然而没想出来看了题解视频，

视频中有一句我觉得很有道理：他说“对于有插入顺序的问题，首先想到队列、栈、链表”

再分析题目：题目的get要求能随机访问！（通过key找value 

　　　　　　　　　put要求能插入到头部

用map做随机访问，用双向链表快速移动节点

因为头尾节点都常被用到（头部插入尾部删除）

所以这里使用虚节点head和tail解决这个问题！

心得：

我的数据结构学的真的太烂了。

Map的api都是现查的……

作为第一次用java写数据结构的题其实还有超级多细节值得思考，

比如public还是private？

比如new的使用

比如节点做指针的理解

balabala……

虚节点很妙

手写双向链表其实不难

一道题对着题解还搞了好久……

但是为什么脑子总是很快的反应过来觉得会了呢？

其实理解起来超级容易哇，本身LRU在计组课上也学过。

希望过几天重新拿起来还能写得出来吧。