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

题目来源

460. LFU 缓存 - 力扣（LeetCode）

题目描述

请你为最不经常使用（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 <= 1040 <= key <= 1050 <= value <= 109最多调用 2 * 10^5 次 get 和 put 方法

题目解析

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

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

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

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

key：本题的keyval：本题的valuefreq：对应key使用次数

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

‘

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

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

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

那么代码该如何实现呢？

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

1、put新增操作一定会带来一个使用次数freq=1的键，且此新键的使用次数1一定是最少的，此时我们可以更新minFreq=12、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 keyMap;

/** freqMap的key是访问次数，value是具有相同访问次数的key对应的node组成的链表，链表头是最远访问的，链表尾是最近访问的 */

HashMap 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)

金钥匙

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

leetcode 动态规划算法精品讲解(2)——DP问题入门（适合零基础者，一看就会）

linux 数据库 LeetCode 每日一题 Day 10 || 并查集/二分搜索

发表评论取消回复

金钥匙

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

leetcode 动态规划 算法精品讲解(2)——DP问题入门（适合零基础者，一看就会）

linux 数据库 LeetCode 每日一题 Day 10 || 并查集/二分搜索

相关文章

发表评论取消回复

leetcode 动态规划算法精品讲解(2)——DP问题入门（适合零基础者，一看就会）