「力扣」第 146 题:LRU 缓存机制(中等)


「力扣」第 146 题:LRU 缓存机制(中等)

运用你所掌握的数据结构,设计和实现一个 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

题目意思:缓存是有限的,在缓存满的时候,删除哪些元素,就有不同的缓存删除策略。

LRU (Least Recently Used)缓存机制

  • 在缓存满的时候,删除缓存里最久未使用的数据,然后再放入新元素;
  • 数据的访问时间很重要,访问时间距离现在最近,就最不容易被删除。

核心思想:在删除元素的时候,只看在缓存里的存在时间。

另一种缓存删除机制是 LFU (Least Frequently Used,最不经常使用)缓存机制,这道题是「力扣」第 460 题:LFU 缓存。算法的设计思想其实是一样的。

思路

  • 由于题目的时间复杂度要求 $O(1)$,空间肯定不能省,存取数据时间性能最好的就是哈希表,因此底层的数据结构一定是一个哈希表;
  • 根据题目意思,访问某个数据,时间优先级得提前,还有删除末尾结点的需求,这样的数据结构得在头尾访问数据最快,这种数据结构是「双向链表」
  • 「链表」结点需要记录:1、value,2、key(在哈希表里删除的时候用得上),3、前驱结点引用,4、后继结点引用。

这样一套设计下来,题目中要求的操作就是 $O(1)% 了。

下面是内存结构示意图:

image.png

编码说明:

  • 应该先弄清楚思路,再编码;
  • 可以设计成「双向链表」的尾部存储较新访问的结点,头部是当前频次最旧的结点。双向链表在结构上是对称的,编码的时候注意保持语义一致;
  • 「双向链表」的常见操作是使用两个虚拟结点,一个访问头部最快,另一个访问尾部最快,这个技巧其实在「单链表」中我们已经见过,叫「哨兵结点」;
  • 链表中的相关操作建议画图去思考实现,否则凭空想象一些指针变量的指向操作容易出错;
  • 在一些操作中相同的操作,应该考虑抽取成公用的方法;
  • 在编码完成以后,需要注意调试,这一步是很花时间的,也没有过多的技巧,添加打印输出语句。

注意:

  1. 以下代码由于本人水平有限,封装还不够好,仅供参考;
  2. 下面的代码细节特别多,读者浏览即可,不建议模仿,应该尝试自己编写完成,相信是一个不错的编程练习;
  3. Java 里的 LinkedList 就是双向链表,这里只是为了练习,定制化一些操作,因此手写。

参考代码

import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    private Map map;

    /**
     * 双链表结点类
     */
    private class ListNode {

        private Integer key;
        private Integer value;
        /**
         * 前驱结点 precursor
         */
        private ListNode pre;
        /**
         * 后继结点 successor(写成 next 是照顾单链表的表示习惯)
         */
        private ListNode next;

        public ListNode() {
        }

        public ListNode(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;

    /**
     * 虚拟头结点没有前驱
     */
    private ListNode dummyHead;
    /**
     * 虚拟尾结点没有后继
     */
    private ListNode dummyTail;

    public LRUCache(int capacity) {
        map = new HashMap<>(capacity);
        this.capacity = capacity;
        dummyHead = new ListNode(-1, -1);
        dummyTail = new ListNode(-1, -1);
        // 初始化链表为 head <-> tail

        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;
    }

    /**
     * 如果存在,把当前结点移动到双向链表的头部
     *
     * @param key
     * @return
     */
    public int get(int key) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            int val = node.value;

            // 把当前 node 移动到双向链表的头部
            moveNode2Head(key);
            return val;
        } else {
            return -1;
        }
    }

    /**
     * 如果哈希表的容量满了,就要删除一个链表末尾元素,然后在链表头部插入新元素
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // 1、更新 value
            map.get(key).value = value;
            // 2、把当前 node 移动到双向链表的头部
            moveNode2Head(key);
            return;
        }

        // 放元素的操作是一样的

        if (map.size() == capacity) {
            // 如果满了
            ListNode oldTail = removeTail();

            // 设计 key 就是为了在这里删除
            map.remove(oldTail.key);
        }

        // 然后添加元素
        ListNode newNode = new ListNode(key, value);
        map.put(key, newNode);
        addNode2Head(newNode);
    }

    // 为了突出主干逻辑,下面是 3 个公用的方法

    /**
     * 删除双链表尾部结点
     */
    private ListNode removeTail() {
        ListNode oldTail = dummyTail.pre;
        ListNode newTail = oldTail.pre;

        // 两侧结点建立连接
        newTail.next = dummyTail;
        dummyTail.pre = newTail;

        // 释放引用
        oldTail.pre = null;
        oldTail.next = null;

        return oldTail;
    }

    /**
     * 把当前 key 指向的结点移到双向链表的头部
     *
     * @param key
     */
    private void moveNode2Head(int key) {
        // 1、先把 node 拿出来
        ListNode node = map.get(key);

        // 2、原来 node 的前驱和后继接上
        node.pre.next = node.next;
        node.next.pre = node.pre;

        // 3、再把 node 放在末尾
        addNode2Head(node);
    }

    /**
     * 在双链表的头部新增一个结点
     *
     * @param newNode
     */
    private void addNode2Head(ListNode newNode) {
        // 1、当前头结点
        ListNode oldHead = dummyHead.next;

        // 2、末尾结点的后继指向新结点
        oldHead.pre = newNode;

        // 3、设置新结点的前驱和后继
        newNode.pre = dummyHead;
        newNode.next = oldHead;

        // 4、更改虚拟头结点的后继结点
        dummyHead.next = newNode;
    }


    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.map.keySet());

        int res1 = cache.get(1);
        System.out.println(res1);

        cache.put(3, 3);

        int res2 = cache.get(2);
        System.out.println(res2);

        int res3 = cache.get(3);
        System.out.println(res3);

        cache.put(4, 4);
        System.out.println(cache.map.keySet());

        int res4 = cache.get(1);
        System.out.println(res4);

        int res5 = cache.get(3);
        System.out.println(res5);

        int res6 = cache.get(4);
        System.out.println(res6);
    }
}

文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「力扣」第 147 题:对链表进行插入排序(中等) 「力扣」第 147 题:对链表进行插入排序(中等)
「力扣」第 147 题:对链表进行插入排序(中等) 英文网址:147. Insertion Sort List ; 中文网址:147. 对链表进行插入排序 。 我写的题解地址:https://leetcode-cn.com/probl
下一篇 
「力扣」第 143 题:重排链表(中等) 「力扣」第 143 题:重排链表(中等)
「力扣」第 143 题:重排链表(中等)链接:https://leetcode-cn.com/problems/reorder-list 给定一个单链表 L:L0→L1→…→L**n-1→Ln ,将其重新排列后变为: L0→Ln→L1→L
  目录