Leetcode 146 LRU毫无新意题解

最近和我一起刷题的小伙伴不和我一起刷题了，蛮伤感的。跟着她学到了很多东西，算得上刷题路上遇到的文昌贵人。不知道你会不会看得到这篇帖子，希望你能有个好的前程。感谢最近这段时间的陪伴和指引。

感伤完毕，对新手老大难问题 （LRU）。这篇文章我写在这里当做是自己的学习笔记，如果能够帮助到一些朋友，那也算是有点贡献。

参考内容
1. 王争 在某时间app上的 数据结构于算法之美 其中链表篇  归纳总结了很多底层的细节，能够帮助理解
2. 花花酱对于Leetcode 146的讲解  传送门 -> https://www.youtube.com/watch?v=q1Njd3NWvlY 能够快速帮你理解这道题的题目要求和注意的细节
3. 中国区力扣上的题解 传送门 -> https://leetcode-cn.com/problems ... xian-by-labuladong/ 系统的详细讲解了这道题的写法

正文内容

题目要求： 实现一个 最近最少使用 的设计题目
问题 ：什么是最近最少使用?  
解答：想象一下你家里的书柜，上面放着的都是最近要看，看过，和在看的书。但是书柜大小有限，最好拿的位置肯定是最近最常看的书。因此，当某些书你确定最近不会看的时候，你会把它收纳到盒子里放在一个不碍事的角落里。那么这个过程就是实现了一个最近最少使用的设计。

题目逻辑：1. 当 get 的时候
                           a. 若已经存在，将之前存在的删除。在从头部插入
                           b. 若不存在 返回-1
                 2.  当 put的时候
                           a. 若不存在
                                 I. 查看容器是否已满，满了的话把最后一位删除。不满就直接插入到头节点
                           b. 若存在
                                 i. 将之前的删除，从头部插入
题目一些引申的requirement：
         1. 需要支持random访问 时间需要是 o(1)
         2. remove last entry 时间需要o(1)
         3. add/ move an entry 时间需要 o(1)

题目数据结构策略：使用HashMap + double linked list来实现
问：为什么要用HashMap?
答：单纯使用list 无法支持在O(1)的时间做到随机访问 Array可以做到O（1）的时间随机访问，但是Array在remove 和 add 的时候可能会造成 o（n）的时间

问：为什么要使用double linked list？ 单链表不就可以完成2 和 3 了吗
答：使用双链表的原因是在于，可以很快的找到它的前节点。虽然这样存储会消耗额外的空间（extra space for pre-pointer ）但是以空间换时间的方式在这道题是可取的。因为我们可能要频繁涉及到随机删除某一个entry。单链表的话，我们还需要先循环一遍记录pre 节点，在来找当前节点。（插入也会有同样的问题，但是这道题不太涉及插入，但可以延伸了解双向链表这一特性）

解题思路

手撸一个 双向链表的class （你也可以去调用LinkedHashMap 或者 double linked list anyway 别问！问就是我要装逼）
class Node{
        Node prev;
        Node next;
        int key;
        int val;
        public Node(int k,int v){
            key = k;
            val = v;
        }
    }


初始化 capacity 和double linked list的对应关系
public LRUCache(int capacity) {
        cap = capacity;
        map = new HashMap<>();
        size = 0;
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;
        tail.prev = head;
    }

构建remove function 方便调用（可读性 和 可扩展性 还有复用性）
public void remove(Node node){
//这里给新手同学讲一个linked list的一个技巧，处理对应关系时，为了保证正确性和逻辑性，不造成溢出。（举个不太好的例子） 先找好小三和小三确立好关系，在把现任甩了 （这个例子应该会被骂吧 方便记忆 骂就骂吧）
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
建议新手同学 画画图掌握一下对应关系

构建一个addHead function 因为我们要频繁向头结点插入
public void addHead(Node node){
        node.prev = head;
        node.next = head.next;
        head.next = node;
        node.next.prev = node;
    }

接下来就是 get function
public int get(int key) {
        Node node = map.get(key);
        if(node==null) return -1;
        remove(node);
        addHead(node);
        return node.val;
    }

最终大boss put
public void put(int key, int value) {
        Node node = map.get(key);
      //这里就是我之前说的 先查看有没有
        if(node==null){
            node = new Node(key,value);
            map.put(key,node);
            addHead(node);
         //在查看size的情况
            if(size==cap){
                map.remove(tail.prev.key);
                remove(tail.prev);
            }
            else{
                size++;
            }
        }
//如果有的话 就按get哪样去处理
        else{
            node.val = value;
            map.put(key,node);
            remove(node);
            addHead(node);
        }
    }


代码详情如下
class LRUCache {
    class Node{
        Node prev;
        Node next;
        int key;
        int val;
        public Node(int k,int v){
            key = k;
            val = v;
        }
    }
    Map<Integer,Node> map;
    Node head;
    Node tail;
    int cap;
    int size;
    public LRUCache(int capacity) {
        cap = capacity;
        map = new HashMap<>();
        size = 0;
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;
        tail.prev = head;
    }


    public void remove(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void addHead(Node node){
        node.prev = head;
        node.next = head.next;
        head.next = node;
        node.next.prev = node;
    }

    public int get(int key) {
        Node node = map.get(key);
        if(node==null) return -1;
        remove(node);
        addHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if(node==null){
            node = new Node(key,value);
            map.put(key,node);
            addHead(node);
            if(size==cap){
                map.remove(tail.prev.key);
                remove(tail.prev);

            }
            else{
                size++;
            }
        }
        else{
            node.val = value;
            map.put(key,node);
            remove(node);
            addHead(node);
        }
    }
}

一直很头疼这LRU问题，当接触了大量的相关知识之后，花了两个小时仔细研读了一番，其实看通了之后就怎么回事。逻辑很重要。
文后，在碎碎念一下。真的蛮感谢哪位一起刷题的同学，她在思想上教育了我，如何去刷题。刷题是为了巩固你的逻辑，将逻辑应用到类似的题目之中。考算法，不是考谁背的多，背的快，而是你的思维逻辑和分析方法。这就是为什么有的同学可以在没有最优解，没有 做完题目的情况下依旧能拿到offer的原因，你让人看到了你的思考问题的方法和过程，路径正确，就是走得快慢的事了。