力扣146. LRU 缓存

Problem: 146. LRU 缓存

题目描述

思路

主要说明大致思路，具体实现看代码。

1.为了实现题目中的O(1)时间复杂度的get与put方法，我们利用哈希表和双链表的结合，将key作为键，对应的链表的节点作为值（也就是在此处我们用一个节点类作为值）；
2.定义双链表的节点类，其中包含每次put的键与对应的值，还包括前驱、后驱指针；
3.编写双链表的实现类，并实现：

3.1.初始化一个双链表(创建虚拟头、尾节点；由于我们要实现将最就不使用的节点删除，我们在此使用尾插法即每次链表尾部位最近使用的，表头为最久不适用的)；
3.2.实现尾插一个节点；
3.3.实现删除一个给定的节点；
3.4.实现从表头删除一个节点（删除最久不使用的节点）
3.5.返回链表的长度

4.实现LRUCache类：

4.1. 创建哈希表map与双链表cache；
4.2. 为了不直接在get与put中对map与cache操作带来麻烦（主要操作是同步在mao中添加key同时在cache中增、删、改对应节点的值），我们封装实现一些API（具体操作实现看代码）
4.3. 实现get与put方法（直接看代码）

复杂度

时间复杂度:

$O(n)$;其中$n$为要操作的次数

空间复杂度:

$O(n)$

Code

/**
 * Node class
 */
class Node {
    public int key;
    public int val;
    public Node next;
    public Node prev;

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

class DoubleList {
    //The dummy node of head and tail to a double linked list
    private Node head;
    private Node tail;
    //The size of a linked list
    private int size;

    public DoubleList() {
        //Initialize the element of double linked list
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // Add node x at the end of the list, time O(1)
    // Tail insertion method of bidirectional linked list
    // with virtual head and tail nodes
    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    // Delete the x node in the linked list (x must exist)
    // Since it is a double-linked list and given to the target Node,
    // time O(1)
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    // Delete the first node in the linked list
    // and return the node, time O(1)
    public Node removeFirst() {
        if (head.next == null) {
            return null;
        }
        Node first = head.next;
        remove(first);
        return first;
    }

    // Return list length, time O(1)
    public int size() {
        return size;
    }
}

class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    //Max capacity
    private int cap;

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

    // Upgrade a key to the most recently used
    private void makeRecently(int key) {
        Node x = map.get(key);
        // Delete this node from the linked list first
        cache.remove(x);
        // Move back to the end of the line
        cache.addLast(x);
    }

    // Add the most recently used element
    private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        // The end of the list is the most recently used element
        cache.addLast(x);
        // Add the mapping of the key to the map
        map.put(key, x);
    }

    // Delete a key
    private void deleteKey(int key) {
        Node x = map.get(key);
        // Delete from the linked list
        cache.remove(x);
        // Delete from map
        map.remove(key);
    }

    // Delete the element that has been unused the longest
    private void removeLeastRecently() {
        // The first element at the head of the list is the one
        // that has been unused for the longest time
        Node deletedNode = cache.removeFirst();
        // Delete its key from the map
        int deleteKey = deletedNode.key;
        map.remove(deleteKey);
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // Upgrade the data to the most recently used
        makeRecently(key);
        return map.get(key).val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // Delete old data
            deleteKey(key);
            // The newly inserted data is the latest data
            addRecently(key, value);
            return;
        }
        if (cap == cache.size()) {
            // Delete the element that has been unused the longest
            removeLeastRecently();
        }
        // Add as recently used element
        addRecently(key, 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);
 */