Skip to content

Latest commit

 

History

History
260 lines (224 loc) · 9.31 KB

460.lfu-cache.md

File metadata and controls

260 lines (224 loc) · 9.31 KB

题目地址(460. LFU缓存)

https://leetcode-cn.com/problems/lfu-cache/

题目描述

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。 get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。 put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。   进阶： 你是否可以在 O(1) 时间复杂度内执行两项操作？   示例： LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4

前置知识

  • 链表
  • HashMap

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

本题已被收录到我的新书中，敬请期待～

LFU（Least frequently used) 但内存容量满的情况下，有新的数据进来，需要更多空间的时候，就需要删除被访问频率最少的元素。

举个例子，比如说 cache 容量是 3，按顺序依次放入 1，2，1，2，1，3， cache 已存满 3 个元素 (1，2，3)， 这时如果想放入一个新的元素 4 的时候，就需要腾出一个元素空间。 用 LFU，这里就淘汰 3， 因为 3 的次数只出现依次， 1 和 2 出现的次数都比 3 多。

题中 get 和 put 都是 O(1)的时间复杂度，那么删除和增加都是O(1)，可以想到用双链表，和HashMap，用一个HashMap, nodeMap, 保存当前key，和 node{key, value, frequent} 的映射。 这样get(key)的操作就是O(1). 如果要删除一个元素，那么就需要另一个HashMap，freqMap，保存元素出现次数（frequent）和双链表（DoublyLinkedlist） 映射， 这里双链表存的是 frequent 相同的元素。每次get或put的时候，frequent+1，然后把node插入到双链表的head node, head.next=node 每次删除freqent最小的双链表的tail node, tail.prev。

用给的例子举例说明：

1. put(1, 1), - 首先查找 nodeMap 中有没有 key=1 对应的 value， 没有就新建 node(key, value, freq) -> node1(1, 1, 1), 插入 nodeMap，{[1, node1]} - 查找 freqMap 中有没有 freq=1 对应的 value， 没有就新建 doublylinkedlist(head, tail), 把 node1 插入 doublylinkedlist head->next = node1. 如下图，

460.lfu-cache-1

2. put(2, 2), - 首先查找 nodeMap 中有没有 key=2 对应的 value， 没有就新建 node(key, value, freq) -> node2(2, 2, 1), 插入 nodeMap，{[1, node1], [2, node2]} - 查找 freqMap 中有没有 freq=1 对应的 value， 没有就新建 doublylinkedlist(head, tail), 把 node2 插入 doublylinkedlist head->next = node2. 如下图，

460.lfu-cache-2

3. get(1), - 首先查找 nodeMap 中有没有 key=1 对应的 value，nodeMap:{[1, node1], [2, node2]}, 找到 node1，把 node1 freq+1 -> node1(1,1,2) - 更新 freqMap，删除 freq=1，node1 - 更新 freqMap，插入 freq=2，node1 如下图，

460.lfu-cache-3

4. put(3, 3), - 判断 cache 的 capacity，已满，需要淘汰使用次数最少的元素，找到最小的 freq=1，删除双链表 tail node.prev 如果 tailnode.prev != null, 删除。然后从 nodeMap 中删除对应的 key。 - 首先查找 nodeMap 中有没有 key=3 对应的 value， 没有就新建 node(key, value, freq) -> node3(3, 3, 1), 插入 nodeMap，{[1, node1], [3, node3]} - 查找 freqMap 中有没有 freq=1 对应的 value， 没有就新建 doublylinkedlist(head, tail), 把 node3 插入 doublylinkedlist head->next = node3. 如下图，

460.lfu-cache-4

5. get(2) - 查找 nodeMap，如果没有对应的 key 的 value，返回 -1。 6. get(3) - 首先查找 nodeMap 中有没有 key=3 对应的 value，nodeMap:{[1, node1], [3, node3]}, 找到 node3，把 node3 freq+1 -> node3(3,3,2) - 更新 freqMap，删除 freq=1，node3 - 更新 freqMap，插入 freq=2，node3 如下图，

460.lfu-cache-5

7. put(4, 4), - 判断 cache 的 capacity，已满，需要淘汰使用次数最少的元素，找到最小的 freq=1，删除双链表 tail node.prev 如果 tailnode.prev != null, 删除。然后从 nodeMap 中删除对应的 key。 - 首先查找 nodeMap 中有没有 key=4 对应的 value， 没有就新建 node(key, value, freq) -> node4(4, 4, 1), 插入 nodeMap，{[4, node4], [3, node3]} - 查找 freqMap 中有没有 freq=1 对应的 value， 没有就新建 doublylinkedlist(head, tail), 把 node4 插入 doublylinkedlist head->next = node4. 如下图，

460.lfu-cache-6

8. get(1) - 查找 nodeMap，如果没有对应的 key 的 value，返回 -1。 9. get(3) - 首先查找 nodeMap 中有没有 key=3 对应的 value，nodeMap:{[4, node4], [3, node3]}, 找到 node3，把 node3 freq+1 -> node3(3,3,3) - 更新 freqMap，删除 freq=2，node3 - 更新 freqMap，插入 freq=3，node3 如下图，

460.lfu-cache-7

10. get(4) - 首先查找 nodeMap 中有没有 key=4 对应的 value，nodeMap:{[4, node4], [3, node3]}, 找到 node4，把 node4 freq+1 -> node4(4,4,2) - 更新 freqMap，删除 freq=1，node4 - 更新 freqMap，插入 freq=2，node4 如下图，

460.lfu-cache-8

关键点分析

用两个Map分别保存 nodeMap {key, node} 和 freqMap{frequent, DoublyLinkedList}。 实现get 和 put操作都是O(1)的时间复杂度。

可以用 Java 自带的一些数据结构，比如 HashLinkedHashSet，这样就不需要自己自建 Node，DoublelyLinkedList。 可以很大程度的缩减代码量。

代码（Java code）

publicclassLC460LFUCache { classNode { intkey, val, freq; Nodeprev, next; Node(intkey, intval) { this.key = key; this.val = val; freq = 1; } } classDoubleLinkedList { privateNodehead; privateNodetail; privateintsize; DoubleLinkedList() { head = newNode(0, 0); tail = newNode(0, 0); head.next = tail; tail.prev = head; } voidadd(Nodenode) { head.next.prev = node; node.next = head.next; node.prev = head; head.next = node; size++; } voidremove(Nodenode) { node.prev.next = node.next; node.next.prev = node.prev; size--; } // always remove last node if last node existsNoderemoveLast() { if (size > 0) { Nodenode = tail.prev; remove(node); returnnode; } elsereturnnull; } } // cache capacityprivateintcapacity; // min frequentprivateintminFreq; Map<Integer, Node> nodeMap; Map<Integer, DoubleLinkedList> freqMap; publicLC460LFUCache(intcapacity) { this.minFreq = 0; this.capacity = capacity; nodeMap = newHashMap<>(); freqMap = newHashMap<>(); } publicintget(intkey) { Nodenode = nodeMap.get(key); if (node == null) return -1; update(node); returnnode.val; } publicvoidput(intkey, intvalue) { if (capacity == 0) return; Nodenode; if (nodeMap.containsKey(key)) { node = nodeMap.get(key); node.val = value; update(node); } else { node = newNode(key, value); nodeMap.put(key, node); if (nodeMap.size() == capacity) { DoubleLinkedListlastList = freqMap.get(minFreq); nodeMap.remove(lastList.removeLast().key); } minFreq = 1; DoubleLinkedListnewList = freqMap.getOrDefault(node.freq, newDoubleLinkedList()); newList.add(node); freqMap.put(node.freq, newList); } } privatevoidupdate(Nodenode) { DoubleLinkedListoldList = freqMap.get(node.freq); oldList.remove(node); if (node.freq == minFreq && oldList.size == 0) minFreq++; node.freq++; DoubleLinkedListnewList = freqMap.getOrDefault(node.freq, newDoubleLinkedList()); newList.add(node); freqMap.put(node.freq, newList); } }

参考（References）

  1. LFU(Least frequently used) Cache
  2. Leetcode discussion mylzsd
  3. Leetcode discussion aaaeeeo
close