乐趣区

关于java:设计数据结构实现一个-LFUCache

题目形容

这是 LeetCode 上的 「460. LFU 缓存」,难度为 「艰难」

Tag :「链表」、「双向链表」、「设计」

请你为 「最不常常应用(LFU)」 缓存算法设计并实现数据结构。

实现 LFUCache 类:

  • LFUCache(int capacity) – 用数据结构的容量 capacity 初始化对象
  • int get(int key) – 如果键存在于缓存中,则获取键的值,否则返回 -1。
  • void put(int key, int value) – 如果键已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量时,则应该在插入新项之前,使最不常常应用的项有效。在此问题中,当存在平局(即两个或更多个键具备雷同应用频率)时,应该去除 「最近最久未应用」 的键。

留神「项的应用次数」就是自插入该项以来对其调用 getput 函数的次数之和。应用次数会在对应项被移除后置为 0。

为了确定最不常应用的键,能够为缓存中的每个键保护一个 应用计数器。应用计数最小的键是最久未应用的键。

当一个键首次插入到缓存中时,它的应用计数器被设置为 1 (因为 put 操作 )。对缓存中的键执行 getput 操作,应用计数器的值将会递增。

示例:

 输出:["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输入:[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释:// cnt(x) = 键 x 的应用计数
// cache=[] 将显示最初一次应用的程序(最右边的元素是最近的)LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1);   // cache=[1,_], cnt(1)=1
lFUCache.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lFUCache.get(1);      // 返回 1
                      // cache=[1,2], cnt(2)=1, cnt(1)=2
lFUCache.put(3, 3);   // 去除键 2,因为 cnt(2)=1,应用计数最小
                      // cache=[3,1], cnt(3)=1, cnt(1)=2
lFUCache.get(2);      // 返回 -1(未找到)lFUCache.get(3);      // 返回 3
                      // cache=[3,1], cnt(3)=2, cnt(1)=2
lFUCache.put(4, 4);   // 去除键 1,1 和 3 的 cnt 雷同,但 1 最久未应用
                      // cache=[4,3], cnt(4)=1, cnt(3)=2
lFUCache.get(1);      // 返回 -1(未找到)lFUCache.get(3);      // 返回 3
                      // cache=[3,4], cnt(4)=1, cnt(3)=3
lFUCache.get(4);      // 返回 4
                      // cache=[3,4], cnt(4)=2, cnt(3)=3

提醒:

  • 0 <= capacity, key, value <=
  • 最多调用 次 getput 办法

进阶:你能够为这两种操作设计工夫复杂度为 的实现吗?

根本剖析

前两天咱们刚讲过 146. LRU 缓存机制,简略了解 LRU 就是「移除最久不被应用的元素」。

因而对于 LRU 咱们只须要在应用「哈希表」的同时,保护一个「双向链表」即可:

  • 每次产生 getput 的时候就将元素寄存双向链表头部
  • 当须要移除元素时,则从双向链表尾部开始移除

LFU 简略了解则是指「移除应用次数起码的元素」,如果存在多个应用次数最小的元素,则移除「最近不被应用的那个」(LRU 规定)。同样的 getput 都算作一次应用。

因而,咱们须要记录下每个元素的应用次数,并且在 的复杂度内「批改某个元素的应用次数」和「找到应用次数最小的元素」。

桶排序 + 双向链表

「咱们能够应用「桶排序」的思路,搭配「双向链表」实现 操作。」

「在 LFUCache 中,咱们保护一个由 Bucket 作为节点的双向链表,每个 Bucket 都有一个 idx 编号,代表以后桶寄存的是「应用了多少次」的键值对」idx = 1 的桶寄存应用一次的键值对;idx = 2 的桶寄存的是应用两次的键值对 …)。

同时 LFUCache 持有一个「哈希表」,用来记录哪些 key 在哪个桶内。

「在 Bucket 外部则是保护了一条以 Item 作为节点的双向链表,Item 是用作寄存实在键值对的。」

同样的,Bucket 也持有一个「哈希表」,用来记录 keyItem 的映射关系。

因而 LFUCache 其实是一个「链表套链表」的数据结构:

对应到 LFUCache 的几种操作:

  • get:先通过 LFUCache 持有的哈希表进行查找,如果不存在返回,如果存在找到键值对所在的桶 cur
  • 调用对应的 curremove 操作,失去键值对对应的 item(移除代表以后键值对应用次数加一了,不会在存在于原来的桶中)。
  • item 放到 idx 为 的桶 target 中(代表代表以后键值对应用次数加一,应该放到新的指标桶中)。
  • 如果指标桶 target 不存在,则创立;如果原来桶 cur 移除键值对后为空,则销毁。
  • 更新 LFUCache 中哈希表的信息。
  • put:先通过 LFUCache 持有的哈希表进行查找:
  • 容量达到数量的话须要调用「编号最小的桶」的 clear 操作,在 clear 操作外部,会从 item 双向链表的尾部开始移除元素。实现后再执行插入操作。
  • 如果存在:找到键值对所在的桶 cur,调用 curput 操作,更新键值对,而后调用 LFUCacheget 操作实现应用次数加一。
  • 如果不存在:先查看容量是否达到数量:
  • 插入操作:将键值对增加到 的桶中(代表以后键值对应用次数为),如果桶不存在则创立。

代码:

class LFUCache {

    class Item {
        Item l, r;
        int k, v;
        public Item(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }

    class Bucket {
        Bucket l, r;
        int idx;
        Item head, tail;
        Map<Integer, Item> map = new HashMap<>();
        public Bucket(int _idx) {
            idx = _idx;
            head = new Item(-1, -1);
            tail = new Item(-1, -1);
            head.r = tail;
            tail.l = head;
        }
        void put(int key, int value) {
            Item item = null;
            if (map.containsKey(key)) {item = map.get(key);
                // 更新值
                item.v = value;
                // 在原来的双向链表地位中移除
                item.l.r = item.r;
                item.r.l = item.l;
            } else {item = new Item(key, value);
                // 增加到哈希表中
                map.put(key, item);
            }
            // 减少到双向链表头部
            item.r = head.r;
            item.l = head;
            head.r.l = item;
            head.r = item;
        }
        Item remove(int key) {if (map.containsKey(key)) {Item item = map.get(key);
                // 从双向链表中移除
                item.l.r = item.r;
                item.r.l = item.l;
                // 从哈希表中移除
                map.remove(key);
                return item;
            }
            return null; // never
        }
        Item clear() {
            // 从双向链表尾部找到待删除的节点
            Item item = tail.l;
            item.l.r = item.r;
            item.r.l = item.l;
            // 从哈希表中移除
            map.remove(item.k);
            return item;
        }
        boolean isEmpty() {return map.size() == 0;
        }
    }

    Map<Integer, Bucket> map = new HashMap<>();
    Bucket head, tail;
    int n;
    int cnt;
    public LFUCache(int capacity) {
        n = capacity;
        cnt = 0;
        head = new Bucket(-1);
        tail = new Bucket(-1);
        head.r = tail;
        tail.l = head;
    }
    
    public int get(int key) {if (map.containsKey(key)) {Bucket cur = map.get(key);
            
            Bucket target = null;
            if (cur.r.idx != cur.idx + 1) { 
                // 指标桶空缺
                target = new Bucket(cur.idx + 1);
                target.r = cur.r;
                target.l = cur;
                cur.r.l = target;
                cur.r = target;
            } else {target = cur.r;}

            // 将以后键值对从以后桶移除,并退出新的桶
            Item remove = cur.remove(key);
            target.put(remove.k, remove.v);
            // 更新以后键值对所在桶信息
            map.put(key, target);

            // 如果在移除掉以后键值对后,以后桶为空,则将以后桶删除(确保空间是 O(n) 的)// 也确保调用编号最小的桶的 clear 办法,可能无效移除掉一个元素
            deleteIfEmpty(cur);

            return remove.v;
        } 
        return -1;
    }
    
    public void put(int key, int value) {if (n == 0) return;
        if (map.containsKey(key)) {
            // 元素已存在,批改一下值
            Bucket cur = map.get(key);
            cur.put(key, value);
            // 调用一下 get 实现「应用次数」+ 1
            get(key); 
        } else {
            // 容器已满,须要先删除元素
            if (cnt == n) {
                // 从第一个桶(编号最小、应用次数最小)中进行革除
                Bucket cur = head.r;
                Item clear = cur.clear();
                map.remove(clear.k);
                cnt--;

                // 如果在移除掉键值对后,以后桶为空,则将以后桶删除(确保空间是 O(n) 的)// 也确保调用编号最小的桶的 clear 办法,可能无效移除掉一个元素
                deleteIfEmpty(cur);
            } 

            // 须要将以后键值对减少到 1 号桶
            Bucket first = null;

            // 如果 1 号桶不存在则创立
            if (head.r.idx != 1) {first = new Bucket(1);
                first.r = head.r;
                first.l = head;
                head.r.l = first;
                head.r = first;
            } else {first = head.r;}

            // 将键值对增加到 1 号桶
            first.put(key, value);
            // 更新键值对所在桶信息
            map.put(key, first);
            // 计数器加一
            cnt++;
        }
    }

    void deleteIfEmpty(Bucket cur) {if (cur.isEmpty()) {
            cur.l.r = cur.r;
            cur.r.l = cur.l;
            cur = null; // help GC
        }
    }
}
  • 工夫复杂度:各操作均为
  • 工夫复杂度:

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.460 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先将所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

退出移动版