8.12 第一次做，无法 AC，今天先大致看了，明天继续研究这题，不做新题
8.13 无法 AC ，漏洞百出
8.14 还是差一点就可以一次 AC 了！
8.15 还是差一点，明天再做一次！
8.16 又是差一点
8.17 终于 AC 了

第一次复习
9.7 无法 AC
9.8 可以 AC
9.14 可以 AC 就是太粗心了

题目描述

原题链接：https://leetcode-cn.com/problems/lru-cache/

解题思路：双向哈希链表

labuladong 题解：https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
官方题解：https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/

Tip：在双向链表的实现中，使用一个伪头部节点（头节点）和伪尾部节点（尾节点）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在，也就没有了空指针异常。

8.12 感悟：
双向链表用来存储实际的值，其可以实现删除和插入的 O(1) 时间复杂度；
哈希表用键映射双向链表的每个节点，用来实现查找的 O(1) 时间复杂度。

8.14 踩坑：
哈希表的键是节点的 key 值，哈希表的值是整个节点！

9.7 感悟：

缓存嘛，想想 Redis 缓存，是不是要既有键又有值？所以实际存储中，一个节点的数据域要既有键又有值才行。
哈希表的目的是快速找到链表的节点，那存的值肯定就是一整个节点。 ```java // 2021.9.7 版本 class Node { public int key, value; public Node next, pre;

// 这个构造函数是为了下面 put 方法传来键值对以便构造新节点的 public Node(int k, int v) {
```
  key = k;
  value = v;
```
} }

class DoubleList { private Node head, tail;

public DoubleList() {
    head = new Node(0, 0);
    tail = new Node(0, 0);
    head.next = tail;
    tail.pre = head;
}
// 往链表头部插入数据(头节点之后插)
public void addFirst(Node n) {
    head.next.pre = n;
    n.pre = head;
    n.next = head.next;
    head.next = n;
}
// 删除链表任一节点
public void delete(Node n) {
    n.next.pre = n.pre;
    n.pre.next = n.next;
}
// 删除链表最后一个节点并返回
// 返回值的作用是可以让哈希表据其 key 值 remove 掉它
public Node removeLast() {
    Node tmp = tail.pre;
    delete(tmp);
    return tmp;
}

}

class LRUCache {

DoubleList cache;
Map<Integer, Node> map;
int cap;
public LRUCache(int capacity) {
    cache = new DoubleList();
    map = new HashMap<>();
    cap = capacity;
}

public int get(int key) {
    if(map.get(key) == null) return -1;
    else {
        put(key, map.get(key).value);
        return map.get(key).value;
    }
}

public void put(int key, int value) {
    Node n = new Node(key, value);
    if(map.get(key) != null) {
        cache.delete(map.get(key));
        cache.addFirst(n);
        map.put(key, n);
    } else {
        if(map.size() != cap) {
            cache.addFirst(n);
            map.put(key, n);
        } else {
            Node tmp = cache.removeLast();
            map.remove(tmp.key);
            cache.addFirst(n);
            map.put(key, n);
        }

    }
}

}

```java
// 2021.8.13 版本
class Node {
    public int key, val;   // 节点类全都要是 public
    public Node pre, next; // 节点类全都要是 public

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

class DoubleList {
    private Node head;
    private Node tail;

    public DoubleList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
    }

    // 往链表头部插入数据 (在头节点之后插)
    public void addFirst(Node x) {
        head.next.pre = x;
        x.pre = head;
        x.next = head.next;
        head.next = x;
    }

    // 删除任意节点数据
    public void remove(Node x) {
        x.next.pre = x.pre;
        x.pre.next = x.next;
    }

    // 删除最后一个节点并返回
    // 返回值的作用是可以让哈希表据其 key 值 remove 掉它
    public Node removeLast() {
        Node tmp = tail.pre;
        remove(tail.pre);
        return tmp;
    }
}

class LRUCache {

    private int cap;
    private DoubleList cache;
    private Map<Integer, Node> map;

    public LRUCache(int capacity) {
        this.cap = capacity;
        this.cache = new DoubleList();
        this.map = new HashMap<>();
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1;

        int val = map.get(key).val;
        this.put(key, val); // 反正 put 除了可以更新原有值，还能把节点移到前面去利用 put 把值移头去
        return val;
    }

    public void put(int key, int value) {
        Node x = new Node(key, value);
        // 先不管容量够不够，先判断值在不在:
        // 如果值已存在，是不用管容量的
        if(map.containsKey(key)) {
            cache.remove(map.get(key)); // 要删除 HashMap 中本来存在的 Node，不能删除新来的 x 
            cache.addFirst(x);
            map.put(key, x); // key 存在的话，HashMap 是会覆盖的
        }else {
            // 如果值不存在：容量够与容量满
            // 容量够与容量满的区别是：容量满得先把最后一个节点去掉
            // 其它都是相同的操作：头插 + 更新哈希表
            // 所以可以把容量满当初特殊情况
            if(map.size() == cap) {
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            // 容量肯定够的情况
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}

数据结构与算法

4. LRU 缓存机制

题目描述

解题思路：双向哈希链表