146. LRU 缓存

一、题目

二、思路

• 题目要求 O(1) 的平均时间复杂度运行 -> 使用Map空间换时间 Map<Integer, Node>
• Map 通过 key 直接找到对应节点 getNode(key) -> Node
• 记得只要查过该节点之后就应该把该节点放到最前面 pushFront(Node)
• put 元素后，在map中添加，记得检查是否超过 capacity，超过则删除在map中的元素，以及在链表中的元素 delete(Node)
• 这里提到的 pushFront(Node) 和 delete(Node) 都是针对双向队列进行位置移动相关的操作，不涉及 Map。

三、代码

class LRUCache {
    class Node{
        int key,val;
        Node pre, next;

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

    Node dummy = new Node(0, 0);
    int capacity;
    Map<Integer, Node> map = new HashMap<>();

	// 初始化双向队列
    public LRUCache(int capacity) {
        dummy.pre = dummy;
        dummy.next = dummy;
        this.capacity = capacity;
    }
    
    
    public int get(int key) {
    	// 从 map 中快速获得 node
        Node node = map.get(key);
        
		// 不存在返回 -1
        if (node == null) {
            return -1;
        }
		// 查询到需要遵循LRU的规则将最近查询的放到队首
        delete(node);
        pushFront(node);
        return node.val;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        // 已经存在就直接进行更新值，结束 put 方法
        if (node != null) {
            // 更新值
            node.val = value;
            delete(node);
            pushFront(node);
            return ;
        }
        // 不存在就新建一个 node，在双向队列和 map 中同时更新
        node = new Node(key,value);
        pushFront(node);
        map.put(key, node);
		// 更新后检查是否超出容量
		// 超出容量就删除双向队列中的最后一个节点，同时在 map 中删除
        if (map.size() > capacity) {
            Node lastNode = dummy.pre;
            delete(lastNode);
            map.remove(lastNode.key);
        }
    }

	// 将 node 放到双向队列队首
    private void pushFront(Node node) {
        node.next = dummy.next;
        node.pre = dummy;
        dummy.next.pre = node;
        dummy.next = node;
    }
    // 在双向队列中删除 node
    private void delete(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}

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