LeetCode - 460 LFU缓存（Java & JS & Python）

系统管理员 2024-02-05 16:10 58阅读 0赞

#### 题目来源 ####

[460. LFU 缓存 - 力扣（LeetCode）][460. LFU _ - _LeetCode]

#### 题目描述 ####

请你为 [最不经常使用（LFU）][LFU]缓存算法设计并实现数据结构。

实现 LFUCache 类：

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

为了确定最不常使用的键，可以为缓存中的每个键维护一个 **使用计数器** 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

#### 示例 ####

输入

>     ["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 lfu = new LFUCache(2);
>     lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
>     lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
>     lfu.get(1);      // 返回 1
>                      // cache=[1,2], cnt(2)=1, cnt(1)=2
>     lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
>                      // cache=[3,1], cnt(3)=1, cnt(1)=2
>     lfu.get(2);      // 返回 -1（未找到）
>     lfu.get(3);      // 返回 3
>                      // cache=[3,1], cnt(3)=2, cnt(1)=2
>     lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
>                      // cache=[4,3], cnt(4)=1, cnt(3)=2
>     lfu.get(1);      // 返回 -1（未找到）
>     lfu.get(3);      // 返回 3
>                      // cache=[3,4], cnt(4)=1, cnt(3)=3
>     lfu.get(4);      // 返回 4
>                      // cache=[3,4], cnt(4)=2, cnt(3)=3

#### 提示 ####

*  1 <= capacity <= 104
 *  0 <= key <= 105
 *  0 <= value <= 109
 *  最多调用 2 \* 10^5 次 get 和 put 方法

#### 题目解析 ####

LFU缓存可以通过：两个哈希表(Map结构) + 双向链表来实现。

我们可以定义两个哈希表keyMap和freqMap，其中：

*  keyMap的键是"本题key"，值为"双向链表节点node"
 *  freqMap的键是"本题key的使用次数freq"，值为”对应使用次数freq的key对应的node组成的双向链表“

而双向链表节点node用于记录key的如下信息：

*  key：本题的key
 *  val：本题的value
 *  freq：对应key使用次数

可能上面说法比较晦涩，下面通过图示来说：

![cf74cd265a2b40f7b4d5253422a4f6b1.png][]

--------------------

![ccd04352d84d4259a8c0df3b839e801a.png][]

--------------------

![677655fc324f4b3486c7bffc775bc3d8.png][]

--------------------

![fbede097377b478c80a0aed72205714a.png][]

--------------------

![4ad0202822c74092b5889b1b8adbc79c.png][]

--------------------

![403a8a769ef54fbb809a9ad7aead880c.png][]

--------------------

![fac7ffc4c52f481e9fc717e30b53c01d.png][]‘

--------------------

![2526f47bd8b7419294c49b53e637aa81.png][]

--------------------

![8be6b78ca8ef4ca5beb59a153bf3746e.png][]

--------------------

![753111e628ec47bda62eebad2ecc6307.png][]

以上就是两个哈希Map，以及双向链表完成LFU缓存的逻辑。

上面逻辑中，有一个问题，那么就是每次LFU容量不足时，我们需要删除掉最少、最远使用的key，那么首先如何找到最少使用次数的key呢？

上面图示中，我们是通过人眼识别出freqMap键列中最小的键，即为最少使用次数。

那么代码该如何实现呢？

我们可以定义一个全局变量（或者类静态变量）minFreq来记录最少使用次数，而minFreq的更新有如下时机：

*  1、put新增操作一定会带来一个使用次数freq=1的键，且此新键的使用次数1一定是最少的，此时我们可以更新minFreq=1
 *  2、get和put更新操作会新增对应key的使用次数，因此在新增使用次数后，该key需要从对应使用次数的DLink中去除，如果对应DLink只有该key对应节点，且对应DLink是最少使用次数对应的容器链表，那么删除key后，该DLInk就为空，那么最少使用次数的key就没了。此时我们可以直接将minFreq++，因为如果当前key在新增使用次数前是唯一的最少使用次数key，那么当前key新增使用次数后，依旧是最少使用次数的key。而minFreq就是当前key新增使用次数前的使用次数。

#### Java算法源码 ####

import java.util.HashMap;
    
    class LFUCache {
      /** 双向链表节点 */
      static class Node {
        /** 记录本题的键 */
        int key;
    
        /** 记录本题的值 */
        int val;
    
        /** 记录该键被访问的次数 */
        int freq;
    
        /** 当前节点的上一个节点 */
        Node prev;
    
        /** 当前节点的下一个节点 */
        Node next;
    
        public Node(int key, int val, int freq) {
          this.key = key;
          this.val = val;
          this.freq = freq;
          this.prev = null;
          this.next = null;
        }
      }
    
      /** 双向链表 */
      static class Link {
        /** 链表中节点个数 */
        int size;
    
        /** 链表头节点 */
        Node head;
    
        /** 链表尾节点 */
        Node tail;
    
        public Link() {
          this.size = 0;
          this.head = null;
          this.tail = null;
        }
    
        /**
         * 尾插
         *
         * @param node 要被插入的节点
         */
        public void addLast(Node node) {
          if (this.size == 0) {
            // 空链表，则node节点插入后，即为头、尾节点
            this.head = node;
            this.tail = node;
          } else {
            // 非空链表，则node节点插入到tail节点后面
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
          }
          this.size++;
        }
    
        /**
         * 删除指定节点
         *
         * @param node 要删除的节点
         */
        public void remove(Node node) {
          // 空链表没有节点，所以无法删除
          if (this.size == 0) return;
    
          if (this.size == 1) {
            // 链表只有一个节点，则删除完后，变为空链表
            this.head = null;
            this.tail = null;
          } else if (this.head == node) {
            // 如果要删除的节点是头节点
            this.head = this.head.next;
            this.head.prev = null;
          } else if (this.tail == node) {
            // 如果要删除的节点是尾节点
            this.tail = this.tail.prev;
            this.tail.next = null;
          } else {
            // 如果要删除的节点是中间节点
            node.prev.next = node.next;
            node.next.prev = node.prev;
          }
    
          this.size--;
        }
      }
    
      /** keyMap用于记录key对应的node */
      HashMap<Integer, Node> keyMap;
    
      /** freqMap的key是访问次数，value是具有相同访问次数的key对应的node组成的链表，链表头是最远访问的，链表尾是最近访问的 */
      HashMap<Integer, Link> freqMap;
    
      /** LFU缓存中能记录的最多key的数量 */
      int capacity;
    
      /** LFU缓存中所有的key中最少的访问次数 */
      int minFreq;
    
      public LFUCache(int capacity) {
        this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.capacity = capacity;
        this.minFreq = 0;
      }
    
      public int get(int key) {
        if (this.keyMap.containsKey(key)) {
          // 存在对应key，则返回对应val
          Node node = this.keyMap.get(key);
          incNodeFreq(node); // get操作会新增对应key的访问次数
          return node.val;
        } else {
          // 不存在对应key，则返回-1
          return -1;
        }
      }
    
      public void put(int key, int value) {
        // 对应key已存在，则为更新场景
        if (this.keyMap.containsKey(key)) {
          Node node = this.keyMap.get(key);
          incNodeFreq(node); // 更新操作会增加对应key的访问次数
          node.val = value;
        }
        // 对应key不存在，则为新增场景
        else {
          // 先判断容量是否超过，keyMap的key数量就是LFU缓存中记录的key数量
          if (this.keyMap.size() >= this.capacity) {
            Link link = this.freqMap.get(this.minFreq);
            int removeKey = link.head.key;
            link.remove(link.head); // 最少访问次数所在链表的头节点，即为：最少、最远访问的key，容量不足时，需要优先删除它
            this.keyMap.remove(removeKey); // 注意，不要遗漏将keyMap中该key删除
          }
    
          // 新增key，则对应key的访问次数为1，且为最少访问次数
          this.minFreq = 1;
          Node node = new Node(key, value, this.minFreq);
    
          // 将新增key对应的node加入到freqMap，和keyMap中
          this.freqMap.putIfAbsent(this.minFreq, new Link());
          this.freqMap.get(this.minFreq).addLast(node);
          this.keyMap.put(key, node);
        }
      }
    
      /**
       * 增加key的访问次数
       *
       * @param node key对应的node
       */
      public void incNodeFreq(Node node) {
        // 由于key的访问次数增加，因此要从原访问次数的链表中删除
        this.freqMap.get(node.freq).remove(node);
    
        // 如果原链表删除当前key对应的节点后为空，且原链表对应的访问次数就是最少访问次数
        if (this.freqMap.get(node.freq).size == 0 && node.freq == this.minFreq) {
          // 则最少访问次数对应的key没有了，因此最少访问次数++（即当前key访问次数++后，当前key的访问次数还是最少访问次数）
          this.minFreq++;
        }
    
        // 当前key访问次数++
        node.freq++;
    
        // 将当前key对应的node转移到对应增加后的访问次数对应的链表尾部（最近访问）
        this.freqMap.putIfAbsent(node.freq, new Link());
        this.freqMap.get(node.freq).addLast(node);
      }
    }

#### JS算法源码 ####

/** 双向链表节点 */
    class Node {
      constructor(key, val, freq) {
        /** 记录本题的键 */
        this.key = key;
        /** 记录本题的值 */
        this.val = val;
        /** 记录该键被访问的次数 */
        this.freq = freq;
        /** 当前节点的上一个节点 */
        this.prev = null;
        /** 当前节点的下一个节点 */
        this.next = null;
      }
    }
    
    /** 双向链表 */
    class Link {
      constructor() {
        /** 链表中节点个数 */
        this.size = 0;
        /** 链表头节点 */
        this.head = null;
        /** 链表尾节点 */
        this.tail = null;
      }
    
      /**
       * 尾插
       * @param {*} node 要被插入的节点
       */
      addLast(node) {
        if (this.size == 0) {
          // 空链表，则node节点插入后，即为头、尾节点
          this.head = node;
          this.tail = node;
        } else {
          // 非空链表，则node节点插入到tail节点后面
          this.tail.next = node;
          node.prev = this.tail;
          this.tail = node;
        }
        this.size++;
      }
    
      /**
       * 删除指定节点
       * @param {*} node 要删除的节点
       */
      remove(node) {
        // 空链表没有节点，所以无法删除
        if (this.size == 0) return;
    
        if (this.size == 1) {
          // 链表只有一个节点，则删除完后，变为空链表
          this.head = null;
          this.tail = null;
        } else if (this.head == node) {
          // 如果要删除的节点是头节点
          this.head = this.head.next;
          this.head.prev = null;
        } else if (this.tail == node) {
          // 如果要删除的节点是尾节点
          this.tail = this.tail.prev;
          this.tail.next = null;
        } else {
          // 如果要删除的节点是中间节点
          node.prev.next = node.next;
          node.next.prev = node.prev;
        }
    
        this.size--;
      }
    }
    
    /**
     * @param {number} capacity
     */
    var LFUCache = function (capacity) {
      /** keyMap用于记录key对应的node */
      this.keyMap = new Map();
      /** freqMap的key是访问次数，value是具有相同访问次数的key对应的node组成的链表，链表头是最远访问的，链表尾是最近访问的 */
      this.freqMap = new Map();
      /** LFU缓存中能记录的最多key的数量 */
      this.capacity = capacity;
      /** LFU缓存中所有的key中最少的访问次数 */
      this.minFreq = 0;
    };
    
    /**
     * @param {number} key
     * @return {number}
     */
    LFUCache.prototype.get = function (key) {
      if (this.keyMap.has(key)) {
        // 存在对应key，则返回对应val
        const node = this.keyMap.get(key);
        this.incNodeFreq(node); // get操作会新增对应key的访问次数
        return node.val;
      } else {
        // 不存在对应key，则返回-1
        return -1;
      }
    };
    
    /**
     * @param {number} key
     * @param {number} value
     * @return {void}
     */
    LFUCache.prototype.put = function (key, value) {
      // 对应key已存在，则为更新场景
      if (this.keyMap.has(key)) {
        const node = this.keyMap.get(key);
        this.incNodeFreq(node); // 更新操作会增加对应key的访问次数
        node.val = value;
      }
      // 对应key不存在，则为新增场景
      else {
        // 先判断容量是否超过，keyMap的key数量就是LFU缓存中记录的key数量
        if (this.keyMap.size >= this.capacity) {
          const link = this.freqMap[this.minFreq];
          const removeKey = link.head.key;
          link.remove(link.head); // 最少访问次数所在链表的头节点，即为最少、最远访问的key，容量不足时，需要优先删除它
          this.keyMap.delete(removeKey); // 注意，不要遗漏将keyMap中该key删除
        }
    
        // 新增key，则对应key的访问次数为1，且为最少访问次数
        this.minFreq = 1;
    
        // 将新增key对应的node加入到freqMap，和keyMap中
        const node = new Node(key, value, this.minFreq);
    
        if (this.freqMap[this.minFreq] == undefined) {
          this.freqMap[this.minFreq] = new Link();
        }
    
        this.freqMap[this.minFreq].addLast(node);
        this.keyMap.set(key, node);
      }
    };
    
    /**
     * 增加key的访问次数
     * @param {*} node key对应的node
     */
    LFUCache.prototype.incNodeFreq = function (node) {
      // 由于key的访问次数增加，因此要从原访问次数的链表中删除
      this.freqMap[node.freq].remove(node);
    
      // 如果原链表删除当前key对应的节点后为空，且原链表对应的访问次数就是最少访问次数
      if (this.freqMap[node.freq].size == 0 && node.freq == this.minFreq) {
        // 则最少访问次数对应的key没有了，因此最少访问次数++（即当前key访问次数++后，当前key的访问次数还是最少访问次数）
        this.minFreq++;
      }
    
      // 当前key访问次数++
      node.freq++;
    
      // 将当前key对应的node转移到对应增加后的访问次数对应的链表尾部（最近访问）
      if (this.freqMap[node.freq] == undefined) {
        this.freqMap[node.freq] = new Link();
      }
    
      this.freqMap[node.freq].addLast(node);
    };

#### Python算法源码 ####

# 双向链表节点
    class Node:
        def __init__(self, key, val, freq):
            """
            :param key: 记录本题的键
            :param val: 记录本题的值
            :param freq: 记录该键被访问的次数
            """
            self.key = key
            self.val = val
            self.freq = freq
            self.prev = None
            self.next = None
    
    
    # 双向链表
    class Link:
        def __init__(self):
            self.size = 0
            self.head = None
            self.tail = None
    
        def addLast(self, node):
            """
            尾插
            :param node: 要被插入的节点
            """
            if self.size == 0:
                # 空链表，则node节点插入后，即为头、尾节点
                self.head = node
                self.tail = node
            else:
                # 非空链表，则node节点插入到tail节点后面
                self.tail.next = node
                node.prev = self.tail
                self.tail = node
    
            self.size += 1
    
        def remove(self, node):
            """
            删除指定节点
            :param node: 要删除的节点
            """
            if self.size == 0:
                # 空链表没有节点，所以无法删除
                return
    
            if self.size == 1:
                # 链表只有一个节点，则删除完后，变为空链表
                self.head = None
                self.tail = None
            elif self.head == node:
                # 如果要删除的节点是头节点
                self.head = self.head.next
                self.head.prev = None
            elif self.tail == node:
                # 如果要删除的节点是尾节点
                self.tail = self.tail.prev
                self.tail.next = None
            else:
                # 如果要删除的节点是中间节点
                node.prev.next = node.next
                node.next.prev = node.prev
    
            self.size -= 1
    
    
    class LFUCache(object):
    
        def __init__(self, capacity):
            self.keyMap = {}  # keyMap用于记录key对应的node
            self.freqMap = {}  # freqMap的key是访问次数，value是具有相同访问次数的key对应的node组成的链表，链表头是最远访问的，链表尾是最近访问的
            self.capacity = capacity  # LFU缓存中能记录的最多key的数量
            self.minFreq = 0  # LFU缓存中所有的key中最少的访问次数
    
        def get(self, key):
            if key in self.keyMap:
                # 存在对应key，则返回对应val
                node = self.keyMap[key]
                self.incNodeFreq(node)  # get操作会新增对应key的访问次数
                return node.val
            else:
                # 不存在对应key，则返回-1
                return -1
    
        def put(self, key, value):
            if key in self.keyMap:
                # 对应key已存在，则为更新场景
                node = self.keyMap[key]
                self.incNodeFreq(node)  # 更新操作会增加对应key的访问次数
                node.val = value
            else:
                # 对应key不存在，则为新增场景
                # 先判断容量是否超过，keyMap的key数量就是LFU缓存中记录的key数量
                if len(self.keyMap) >= self.capacity:
                    link = self.freqMap[self.minFreq]
                    removeKey = link.head.key
                    link.remove(link.head)  # 最少访问次数所在链表的头节点，即为：最少、最远访问的key，容量不足时，需要优先删除它
                    self.keyMap.pop(removeKey)  # 注意，不要遗漏将keyMap中该key删除
    
                # 新增key，则对应key的访问次数为1，且为最少访问次数
                self.minFreq = 1
                node = Node(key, value, self.minFreq)
    
                # 将新增key对应的node加入到freqMap，和keyMap中
                self.freqMap.setdefault(self.minFreq, Link())
                self.freqMap.get(self.minFreq).addLast(node)
                self.keyMap[key] = node
    
        def incNodeFreq(self, node):
            """
            增加key的访问次数
            :param node: key对应的node
            """
            # 由于key的访问次数增加，因此要从原访问次数的链表中删除
            self.freqMap[node.freq].remove(node)
    
            # 如果原链表删除当前key对应的节点后为空，且原链表对应的访问次数就是最少访问次数
            if self.freqMap[node.freq].size == 0 and node.freq == self.minFreq:
                # 则最少访问次数对应的key没有了，因此最少访问次数++（即当前key访问次数++后，当前key的访问次数还是最少访问次数）
                self.minFreq += 1
    
            # 当前key访问次数++
            node.freq += 1
    
            # 将当前key对应的node转移到对应增加后的访问次数对应的链表尾部（最近访问）
            self.freqMap.setdefault(node.freq, Link())
            self.freqMap[node.freq].addLast(node)

[460. LFU _ - _LeetCode]: https://leetcode.cn/problems/lfu-cache/
[LFU]: https://baike.baidu.com/item/%E7%BC%93%E5%AD%98%E7%AE%97%E6%B3%95
[cf74cd265a2b40f7b4d5253422a4f6b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/233a69b781ea4062a3786c9ecc0f1422.png
[ccd04352d84d4259a8c0df3b839e801a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/c3cc547cc7dd4cf3b700307fb7f8a9d8.png
[677655fc324f4b3486c7bffc775bc3d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/71b212f3c80042d1a0a9c629df8be811.png
[fbede097377b478c80a0aed72205714a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/ef5fae35b06d4fabbf95668b75d0440f.png
[4ad0202822c74092b5889b1b8adbc79c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/5ce5be3622a44e269c43e4cac2c04d45.png
[403a8a769ef54fbb809a9ad7aead880c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/94c2e51ea3ed4e37a43404b784cb56e0.png
[fac7ffc4c52f481e9fc717e30b53c01d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/9660f02469f24c48af0751dfaa598d1d.png
[2526f47bd8b7419294c49b53e637aa81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/faf9d856f6c14f749a83921b951d4aca.png
[8be6b78ca8ef4ca5beb59a153bf3746e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/ddfb270a99124503a218da24513bbd21.png
[753111e628ec47bda62eebad2ecc6307.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/645601e961744a5cbfb0e51f764f873e.png