LRU問題

原題連結

解題思路

總體思路：采用散清單（HashMap）和自寫的雙向連結清單Node

get：

如果不在散清單中，直接傳回-1；

在散清單中，則在雙向連結清單中删除鍵為key的節點，再将該節點加入雙向連結清單尾部，傳回節點value值。

put：

• 如果不在散清單中：

  将put的節點值加入散清單，同時加入雙向連結清單尾部。

  如果之前已達到最大容量，則需要先删去雙向連結清單的頭結點，同時删散清單中頭節點對應的值；

• 否則：

  在雙向連結清單中删除鍵為key的節點，更改其對應的value值，再将待put節點加入雙向連結清單尾部。

代碼

import java.util.HashMap;

class LRUCache {
    HashMap<Integer, Node> map;
    Node head;
    Node tail;
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
        map = new HashMap<>();
    }

    public int get(int key) {
        // System.out.printf("%s %d\n", "put", key);
        // print();
        Node node = map.get(key);
        if (node == null)
            return -1;
        delete(node);
        append(node);
        return node.value;
    }

    public void put(int key, int value) {
        // System.out.printf("%s %d %d\n", "put", key, value);
        // print();
        Node node = map.get(key);
        if (node == null) {
            if (capacity == map.size()) {
                map.remove(head.next.key);
                delete(head.next);
            }
            Node node1 = new Node(key, value);
            append(node1);
            map.put(key, node1);
        } else {
            delete(node);
            node.value = value;
            append(node);
        }
    }
    // 從連結清單中删除節點 node
    void delete(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    // 将節點 node 添加到雙向連結清單末尾
    void  append(Node node) {
        node.pre = tail.pre;
        tail.pre.next = node;
        node.next = tail;
        tail.pre = node;
    }

    void print() {
        Node node = this.head.next;
        while (node != tail) {
            System.out.printf("%d:%d  ", node.key, node.value);
            node = node.next;
        }
        System.out.println();
    }
}

class Node {
    int key;
    int value;
    Node pre;
    Node next;

    public Node() {
    }

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

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