146. LRU Cache

题目描述和难度

  • 题目描述:

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

思路分析

求解关键:

参考解答

参考解答1

import java.util.HashMap;
import java.util.LinkedHashMap;

/**
 * https://leetcode-cn.com/problems/lru-cache/description/
 */
public class LRUCache {

    /**
     * 内部类,双向链表结点类
     */
    private class ListNode {

        // 这个 ListNode 的 key 属性猛的一看可能是多余的
        // 但是我们在移除 tail 结点对应的 Hash 表中的键值对的时候,就需要它
        private int key;

        private int val;
        private ListNode preV;
        private ListNode next;

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

    private HashMap<Integer, ListNode> map;
    private int capacity;
    private int size;
    private ListNode head;
    private ListNode tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 我们在更新的时候,使用先添加再删除的策略,所以多预留一个位置
        this.map = new LinkedHashMap<>(capacity + 1);
        this.head = null;
        this.tail = null;
    }

    //
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // map 中有,说明这个缓存中有数据,从 ListNode 中拿,并且将这个结点移动到队列的开头
        ListNode retNode = map.get(key);
        int retVal = retNode.val;
        // 移动到头
        moveToHead(retNode);
        return retVal;
    }

    /**
     * 把当前结点移动到双向链表的头部
     *
     * @param retNode
     */
    private void moveToHead(ListNode retNode) {
        // 如果头结点不是返回值所在的结点才操作
        if (head == retNode || retNode == null) {
            return;
        }

        // 处理尾指针,retNode 的前指针和后指针统一处理
        if (retNode == tail) {
            tail = tail.preV;
            if (tail != null) {
                tail.next = null;
            }
        }

        if (retNode.preV != null) {
            retNode.preV.next = retNode.next;
        }

        if (retNode.next != null) {
            retNode.next.preV = retNode.preV;
        }

        retNode.next = head;
        retNode.preV = null;
        if (head != null) {
            head.preV = retNode;
        }
        head = retNode;
    }


    /**
     * 末尾结点释放,tail 指针前移
     */
    private void removeLast() {

        // 根据我们的业务逻辑,head 和 tail 要么都非空,要么都为空,不可能出现一个为空,另一个不为空的情况

        // head == null || tail == null 包括了他们同时为 null 的情况
        if (head == null || tail == null) {
            // throw new IllegalArgumentException("当前双向链表为 null,不能执行这个操作");
            return;
        }

        // 如果当前只有一个结点,那么 head 和 tail 都置为 null ,即清空了这个双向链表
        if (head == tail) {
            head = null;
            tail = null;
            return;
        }
        // 此时双向链表非空,并且 head 和 tail 不重合
        // 只要把 tail 向前移动,即可
        ListNode removeNode = tail;
        tail = tail.preV;
        tail.next = null;
        removeNode.preV = null;
        removeNode.next = null;
    }

    /**
     * 把新结点放在双向链表的开头
     *
     * @param newNode
     */
    private void addFirst(ListNode newNode) {
        if (newNode == null) {
            return;
        }
        newNode.next = head;
        newNode.preV = null;
        if (head != null) {
            head.preV = newNode;
        }
        head = newNode;

        // 考虑一下尾结点(比较容易忽略掉这个情况)
        // 如果链表为空,即一开始的情况,tail == null 的时候,tail 也要赋值
        if (tail == null) {
            tail = newNode;
        }
    }

    public void put(int key, int value) {
        // 如果 map 中有
        // 直接拿出来,更新这个结点的 value,并且把这个结点移动到队列的开头
        if (map.containsKey(key)) {
            // 表示击中缓存
            ListNode curNode = map.get(key);
            curNode.val = value;
            moveToHead(curNode);
            return;
        }
        // 如果 map 中没有
        // 情况1:size = capacaity,map 中移除末尾结点,ListNode 把 tail 移除,并且新结点放在双向链表的开头
        ListNode newNode = new ListNode(key, value);
        map.put(key, newNode);
        if (size == capacity) {
            // 移除 Map 中的末尾结点对应的 key-value 对
            int removeKey = tail.key;
            map.remove(removeKey);
            removeLast();
        } else {
            // 情况2:size < capacaity,size++,map 中添加,把新结点加在双向链表的开头
            assert size < capacity;
            // 把一个新结点添加在链表的开头
            size++;
        }
        addFirst(newNode);
    }


    // 调试使用,非必需
    // 只适用去传入双向链表的 head 结点,打印出双向链表
    // 如果传入非 head 结点,对于调试没有意义

    public void printListNode() {
        System.out.println("map:" + map.keySet());
        System.out.println("head:" + head.key);
        System.out.println("tail:" + tail.key);
        StringBuilder stringBuilder = new StringBuilder();
        ListNode curNode = head;
        stringBuilder.append("NULL");
        stringBuilder.append(" <-> ");
        while (curNode != null) {
            stringBuilder.append("(");
            stringBuilder.append(curNode.key);
            stringBuilder.append(",");
            stringBuilder.append(curNode.val);
            stringBuilder.append(")");
            stringBuilder.append(" <-> ");
            curNode = curNode.next;
        }
        stringBuilder.append("NULL");
        System.out.println(stringBuilder.toString());
        System.out.println();
    }

    public static void main(String[] args) {
        // 缓存容量为 2
        int capacity = 2;
        LRUCache lruCache = new LRUCache(capacity);

        lruCache.put(1, 100);
        lruCache.printListNode();
        lruCache.put(2, 200);
        lruCache.printListNode();

        int value1 = lruCache.get(1);
        System.out.println(value1);
        lruCache.printListNode();


        lruCache.put(3, 300);
        lruCache.printListNode();


        int value2 = lruCache.get(2);
        System.out.println(value2);
        lruCache.printListNode();

        lruCache.put(4, 400);
        lruCache.printListNode();
    }

}

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

参考解答2

import java.util.HashMap;
import java.util.LinkedHashMap;

/**
 * https://leetcode-cn.com/problems/lru-cache/description/
 * 参考资料:https://leetcode.com/problems/lru-cache/discuss/145937/100-Java-solution-with-doubly-linked-list-and-HashTable
 */
public class LRUCache2 {

    /**
     * 内部类,双向链表结点类
     */
    private class ListNode {
        // 这个 ListNode 的 key 属性猛的一看可能是多余的
        // 但是我们在移除 tail 结点对应的 Hash 表中的键值对的时候,就需要它
        private int key;
        private int val;
        private ListNode prev;
        private ListNode next;

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

    private HashMap<Integer, ListNode> map;
    private int capacity;
    private ListNode head;
    private ListNode tail;

    public LRUCache2(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>(capacity);
        this.head = null;
        this.tail = null;
    }

    public int get(int key) {
        if (!this.map.containsKey(key)) {
            return -1;
        }

        ListNode curr = this.map.get(key);
        if (curr == head) {
            return curr.val;
        }
        // 如果不是头结点的话,就把这个结点移动到头结点
        moveToHead(curr);
        return curr.val;
    }

    private void moveToHead(ListNode retNode) {
        // 如果头结点不是返回值所在的结点才操作
        if (retNode == head || retNode == null) {
            return;
        }

        // 下面这两个 if 代码很工整,思路也非常正确
        // 只有对非空结点才能进行属性的操作
        if (retNode.prev != null) {
            retNode.prev.next = retNode.next;
        }
        if (retNode.next != null) {
            retNode.next.prev = retNode.prev;
        }
        // 上面分别改变了前后结点的 next 和 prev 指向
        // 对 retNode 没有改变

        // 尾指针向前移动一位
        if (retNode == tail) {
            tail = retNode.prev;
        }

        // 接下来把 retNode 移动到当前的 head 结点之前
        retNode.prev = null;
        if (head != null) {
            retNode.next = head;
            head.prev = retNode;
        }
        head = retNode;
    }

    /**
     * 移除尾结点
     */
    private void evict() {
        if (tail == null) {
            return;
        }

        ListNode evictedNode = tail;
        // 改变 tail 指针
        tail = evictedNode.prev;
        // 截断引用
        evictedNode.prev = null;

        // 对结点的操作都要判断一下结点是否为空
        if (tail != null) {
            tail.next = null;
        }
        // 只剩下一个结点的时候,head 置空
        if (evictedNode == head) {
            head = null;
        }
        this.map.remove(evictedNode.key);
    }

    /**
     * 注意代码中对结点属性的使用都会加上非空的判断
     *
     * @param node
     */
    private void addNodeToHead(ListNode node) {
        if (node == null) {
            return;
        }
        node.next = head;
        if (head != null) {
            head.prev = node;
        }
        node.prev = null;
        head = node;
        if (tail == null) {
            tail = node;
        }
    }

    public void put(int key, int value) {
        ListNode curr;
        if (this.map.containsKey(key)) {
            curr = this.map.get(key);
            curr.val = value;
            moveToHead(curr);
            return;
        }
        curr = new ListNode(key, value);
        if (this.map.size() == this.capacity) {
            // 如果满了,先把最后最后一个结点以及在 map 中对应的 k-v 对移除掉
            evict();
        }
        addNodeToHead(curr);
        this.map.put(key, curr);
    }


    // 调试使用,非必需
    // 只适用去传入双向链表的 head 结点,打印出双向链表
    // 如果传入非 head 结点,对于调试没有意义

    public void printListNode() {
        System.out.println("map:" + map.keySet());
        System.out.println("head:" + head.key);
        System.out.println("tail:" + tail.key);
        StringBuilder stringBuilder = new StringBuilder();
        ListNode curNode = head;
        stringBuilder.append("NULL");
        stringBuilder.append(" <-> ");
        while (curNode != null) {
            stringBuilder.append("(");
            stringBuilder.append(curNode.key);
            stringBuilder.append(",");
            stringBuilder.append(curNode.val);
            stringBuilder.append(")");
            stringBuilder.append(" <-> ");
            curNode = curNode.next;
        }
        stringBuilder.append("NULL");
        System.out.println(stringBuilder.toString());
        System.out.println();
    }

    public static void main(String[] args) {
        // 缓存容量为 2
        int capacity = 2;
        LRUCache2 lruCache = new LRUCache2(capacity);

        lruCache.put(1, 100);
        lruCache.printListNode();
        lruCache.put(2, 200);
        lruCache.printListNode();

        int value1 = lruCache.get(1);
        System.out.println(value1);
        lruCache.printListNode();


        lruCache.put(3, 300);
        lruCache.printListNode();


        int value2 = lruCache.get(2);
        System.out.println(value2);
        lruCache.printListNode();

        lruCache.put(4, 400);
        lruCache.printListNode();
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,val);
 */

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0146-lru-cache ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com