中级提升班下1

题目一 LRU

设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能。set(key, value):将记录(key, value)插入该结构。
get(key):返回key对应的value值。
【要求】
1.set和get方法的时间复杂度为0(1)
⒉.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的3.当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的
【举例】

假设缓存结构的实例是cache，大小为3，并依次发生如下行为1.cache. set ("A"，1)。最常使用的记录为("A",1)
2.cache.set("B",2)。最常使用的记录为("B",2)，("A",1)变为最不常使用的
3.cache.set("C",3)。最常使用的记录为("C",2)，("A",1)还是最不常使用的
4.cache. get("A")。最常使用的记录为("A",1)，("B",2)变为最不常使用的
5.cache.set("D",4)。大小超过了3，所以移除此时最不常使用的记录("B",2)，加入记录("D",4)，并且为最常使用的记录，然后("C",2)变为最不常使用的记录。

解

使用hash表+双向链表的方式来实现LRU，hash可以快速定位元素，双向链表可以快速的新增，删除，修改节点的位置

public static class Node<K, V> {
    public K key;
    public V value;
    public Node<K, V> last;
    public Node<K, V> next;

    public Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

// 双向链表
public static class NodeDoubleLinkedList<K, V> {
    private Node<K, V> head;
    private Node<K, V> tail;

    public NodeDoubleLinkedList() {
        this.head = null;
        this.tail = null;
    }

    // 添加一个新节点，到尾部
    public void addNode(Node<K, V> newNode) {
        if (newNode == null) {
            return;
        }
        if (head == null) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.last = this.tail;
            this.tail = newNode;
        }
    }

    // node放尾巴
    public void moveNodeToTail(Node<K,V> node){
        if (this.tail == node){
            return;
        }
        if (this.head == node){
            this.head = node.next;
            this.head.last = null;
        }else {
            node.last.next = node.next;
            node.next.last = node.last;
        }
        node.last = this.tail;
        node.next = null;
        this.tail.next = node;
        this.tail = node;
    }

    // 淘汰头节点
    public Node<K,V> removeHead(){
        if (this.head == null){
            return null;
        }
        Node<K,V> res = head;
        if (this.head == this.tail){
            this.tail =null;
            this.head = null;
        }else {
            this.head = res.next;
            res.next = null;
            this.head.last = null;
        }
        return res;
    }
}

public static class MyCache<K,V>{
    private Map<K, Node<K,V>> keyNodeMap;
    private NodeDoubleLinkedList<K,V> nodeList;
    private int capacity;

    public MyCache(int capacity){
        if (capacity < 1){
            throw new RuntimeException("should be more than 0.");
        }
        this.keyNodeMap = new HashMap<>();
        this.nodeList = new NodeDoubleLinkedList<>();
        this.capacity = capacity;
    }

    public V get(K key){
        if (this.keyNodeMap.containsKey(key)){
            Node<K,V> res = this.keyNodeMap.get(key);
            this.nodeList.moveNodeToTail(res);
            return res.value;
        }
        return null;
    }

    public void set(K key, V val){
        if (this.keyNodeMap.containsKey(key)){
            Node<K,V> node = this.keyNodeMap.get(key);
            node.value = val;
            this.nodeList.moveNodeToTail(node);
        }else {
            Node<K,V> newNode = new Node<>(key, val);
            this.keyNodeMap.put(key, newNode);
            this.nodeList.addNode(newNode);
            if (this.keyNodeMap.size() == this.capacity +1){
                this.removeMostUnusedCache();
            }
        }
    }

    private void removeMostUnusedCache() {
        Node<K, V> removeNode = this.nodeList.removeHead();
        this.keyNodeMap.remove(removeNode.key);
    }
}