（重要）LRU cache

［抄题］：

［思维问题］：

需要从任何位置访问某数字有没有（重要 ），返回其位置（不重要），所以用hashmap。

需要从任何位置删除，用linkedlist。最终二者结合，用linked hashmap。

［一句话思路］：

链表存物理位置，key存数，value存值（要更新）

［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

1. prev next都是node类型。node第一次初始化的时候没有参数key value public时有.Node head = new Node(-1,-1)前后都是node，类型保持一致.初始节点的prev next都是null
2. LRU中的初始化是把head,tail的中间部分连接起来
3. 私有化数据类型的时候要有hashmap,因为有点，可以直接把key对应的点取出来.长度用.size()表示
4. 是否存在用containsKey
5. move_to_tail(Node current) 里面有参数. 有get就不用移动，没get就要移动
6. set中如果已经存在，判断条件是if (get(key) != -1)，而不是containskey就行了，因为还要放到最后一位
7. 满了的时候，remove的是head.next！！！因为head是空的。先把head.next.key值删remove了再说。head.next = head.next.next;指定指针 head.next.prev = head;在前一步的基础上指定指针
8. insert是新建的节点, 要写new
9. hashmap的操作是put, get。queue的操作语言是poll, add。stack是push／pop。（pgh,qpa,spp）
10. move_2_end中，从左到右，节点的操作顺序是1432

［二刷］：

1. private私有类是小写，而且要加上class
2. get函数记得写返回语句
3. hs满了之后，要写remove head.next的key，让它不被找到
4. Node insert = new Node(key,value)直接指定了,加入hs中的动作是put（key,insert）（因为是这么定义的）
5. hs.get(key) 得到的是一个点,get(key)得到的是一个数

［三刷］：

［总结］：

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构，为什么不用别的数据结构］：

链表存物理位置，key存数，value存值（要更新）

［其他解法］：

［Follow Up］：

［题目变变变］：

public class LRUCache {

    /*

    * @param capacity: An integer

    */

    private class Node {

        Node prev;

        Node next;

        int key;

        int value;

        public Node(int key,int value){

            this.key = key;

            this.value = value;

            this.prev = null;

            this.next = null;

        }

    }

    private HashMap<Integer,Node> hs = new HashMap<Integer,Node>();

    private int capacity;

    private Node head = new Node(-1,-1);

    private Node tail = new Node(-1,-1);

    public LRUCache(int capacity) {

        this.capacity = capacity;

        head.next = tail;

        tail.prev = head;

    }

    /*

     * @param key: An integer

     * @return: An integer

     */

    public int get(int key) {

        if (!hs.containsKey(key)) {

            return -1;

        }

        //remove

        Node curt = hs.get(key);

        curt.prev.next = curt.next;

        curt.next.prev = curt.prev;

        //move_to_tail

        move_to_tail(curt);

        return hs.get(key).value;

    }

    /*

     * @param key: An integer

     * @param value: An integer

     * @return: nothing

     */

    public void set(int key, int value) {

        if (get(key) != -1) {

            hs.get(key).value = value;

            return ;

        }

        //if full,remove head.next

        if (hs.size() == capacity) {

            hs.remove(head.next.key);

            head.next = head.next.next;

            head.next.prev = head;

        }

        //insert,move_to_tail

        Node insert = new Node(key,value);

        hs.put(key,insert);

        move_to_tail(insert);

    }

    private void move_to_tail(Node curt){

        curt.prev = tail.prev;

        tail.prev = curt;

        curt.prev.next = curt;

        curt.next = tail;

    }

}