描述
请你为 最不经常使用（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) 的平均时间复杂度运行。
解题思路
1、构造节点结构体
保存对应的数据信息
const LFUNode = function (
key = "",
val = "",
freq = 0,
pre = null,
next = null
) {
this.key = key;
this.val = val;
this.freq = freq;
this.pre = pre;
this.next = next;
};2、构造双向链表
构造带有头尾节点的双向链表，head和tail为哨兵节点，不保存信息，仅用于标记头尾。
const LFULinkLine = function (node) {
let head = new LFUNode("head");
let tail = new LFUNode("tail");
head.next = node;
tail.pre = node;
node.pre = head;
node.next = tail;
this.head = head;
this.tail = tail;
};3、编写链表头添加节点方法
将节点插入到链表的头结点之后，其他节点往后移。
LFULinkLine.prototype.addNode = function (node) {
this.head.next.pre = node;
node.pre = this.head;
node.next = this.head.next;
this.head.next = node;
};4、编写删除节点方法
将节点从链表中删除。
LFULinkLine.prototype.removeNode = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
};5、构造LRU缓存结构体
构造LRU缓存结构体，具体信息如下代码，capacity用于保存最大缓存数，即该类的容量；num保存当前存储的数据量，用于判别是否超出最大容量；minFreq保存当前存储的数据中的最小频率，删除的时候需要优先删除频率最小的；kvMap保存节点详细信息，索引为节点的key值，查询可以直接从这里查出信息；freqMap保存对应频率的链表信息，索引为节点的freq（频率），删除的时候可以快速从这里获取需要删除节点的信息。
/**
* @param {number} capacity
*/
var LFUCache = function (capacity) {
this.capacity = capacity;//最大缓存
this.num = 0;//当前数目
this.minFreq = 0;//当前最小频率
this.kvMap = new Map();//保存节点信息
this.freqMap = new Map();//保存对应频率的链表信息
};6、编写get方法
get主要有以下两种情况：
（1）节点存在
- 通过kvMap获取到对应节点
- 将节点从freqMap中删除
- 判断是否需要修改minFreq
- 修改节点的freq
- 重新将节点插入freqMap
- 返回节点的value
（2）节点不存在
容量capacity为0或者kvMap中没有该节点信息，直接返回-1即可。
/**
* @param {number} key
* @return {number}
*/
LFUCache.prototype.get = function (key) {
if (this.capacity === 0) return -1;
if (!this.kvMap.has(key)) return -1;
//通过kvMap获取到对应节点
let node = this.kvMap.get(key);
let linkLine = this.freqMap.get(node.freq);
//将节点从freqMap中删除
linkLine.removeNode(node);
//判断是否需要修改minFreq
//清空了
if (linkLine.head.next === linkLine.tail) {
this.freqMap.delete(node.freq);
if (this.minFreq == node.freq) this.minFreq++;
}
//修改节点的freq
node.freq++;
//重新将节点插入freqMap
if (this.freqMap.has(node.freq)) {
linkLine = this.freqMap.get(node.freq);
linkLine.addNode(node);
} else {
this.freqMap.set(node.freq, new LFULinkLine(node));
}
//返回节点的value
return node.val;
};7、编写put方法
put操作主要有以下两种情况：
（1）更新
- 通过kvMap获取到对应节点
- 将节点从freqMap中删除
- 判断是否需要修改minFreq
- 更新节点信息
- 重新将节点插入freqMap
（2）存入
存入情况下又有两种情况：
容量已满
- 通过minFreq找到需要删除的节点
- 将节点从freqMap中删除
- 判断是否需要修改minFreq
- 将新节点插入freqMap
- 更新minFreq
容量未满
- 修改num
- 将新节点插入freqMap
- 更新minFreq
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LFUCache.prototype.put = function (key, value) {
if (this.capacity === 0) return;
if (this.kvMap.has(key)) {
//更新
//通过kvMap获取到对应节点
let node = this.kvMap.get(key);
//将节点从freqMap中删除
let linkLine = this.freqMap.get(node.freq);
linkLine.removeNode(node);
//判断是否需要修改minFreq
if (linkLine.head.next === linkLine.tail) {
if (this.minFreq == node.freq) this.minFreq++;
this.freqMap.delete(node.freq);
}
//更新节点信息
node.val = value;
node.freq++;
//重新将节点插入freqMap
if (this.freqMap.has(node.freq)) {
linkLine = this.freqMap.get(node.freq);
linkLine.addNode(node);
} else {
linkLine = new LFULinkLine(node);
this.freqMap.set(node.freq, linkLine);
}
} else {//存入
if (this.capacity == this.num) {//存满
//通过minFreq找到需要删除的节点
let freq = this.minFreq;
let linkLine = this.freqMap.get(freq);
let node = linkLine.tail.pre;
//将节点从freqMap中删除
linkLine.removeNode(node);
this.kvMap.delete(node.key);
//判断是否需要修改minFreq
if (linkLine.head.next === linkLine.tail) {
this.freqMap.delete(node.freq);
}
} else {
//修改num
this.num++;
}
//将新节点插入freqMap
let node = new LFUNode(key, value, 0);
this.kvMap.set(key, node);
if (this.freqMap.has(0)) {
let linkLine = this.freqMap.get(0);
linkLine.addNode(node);
} else {
let linkLine = new LFULinkLine(node);
this.freqMap.set(0, linkLine);
}
//更新minFreq
this.minFreq = 0;
}
};代码
const LFUNode = function (
key = "",
val = "",
freq = 0,
pre = null,
next = null
) {
this.key = key;
this.val = val;
this.freq = freq;
this.pre = pre;
this.next = next;
};
const LFULinkLine = function (node) {
let head = new LFUNode("head");
let tail = new LFUNode("tail");
head.next = node;
tail.pre = node;
node.pre = head;
node.next = tail;
this.head = head;
this.tail = tail;
};
LFULinkLine.prototype.addNode = function (node) {
this.head.next.pre = node;
node.pre = this.head;
node.next = this.head.next;
this.head.next = node;
};
LFULinkLine.prototype.removeNode = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
};
/**
* @param {number} capacity
*/
var LFUCache = function (capacity) {
this.capacity = capacity;
this.num = 0;
this.minFreq = 0;
this.kvMap = new Map();
this.freqMap = new Map();
};
/**
* @param {number} key
* @return {number}
*/
LFUCache.prototype.get = function (key) {
if (this.capacity === 0) return -1;
if (!this.kvMap.has(key)) return -1;
let node = this.kvMap.get(key);
let linkLine = this.freqMap.get(node.freq);
linkLine.removeNode(node);
//清空了
if (linkLine.head.next === linkLine.tail) {
this.freqMap.delete(node.freq);
if (this.minFreq == node.freq) this.minFreq++;
}
node.freq++;
if (this.freqMap.has(node.freq)) {
linkLine = this.freqMap.get(node.freq);
linkLine.addNode(node);
} else {
this.freqMap.set(node.freq, new LFULinkLine(node));
}
return node.val;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LFUCache.prototype.put = function (key, value) {
if (this.capacity === 0) return;
if (this.kvMap.has(key)) {
//更新
let node = this.kvMap.get(key);
node.val = value;
let linkLine = this.freqMap.get(node.freq);
linkLine.removeNode(node);
if (linkLine.head.next === linkLine.tail) {
if (this.minFreq == node.freq) this.minFreq++;
this.freqMap.delete(node.freq);
}
node.freq++;
if (this.freqMap.has(node.freq)) {
linkLine = this.freqMap.get(node.freq);
linkLine.addNode(node);
} else {
linkLine = new LFULinkLine(node);
this.freqMap.set(node.freq, linkLine);
}
} else {
//存入
if (this.capacity == this.num) {
//存满
let freq = this.minFreq;
let linkLine = this.freqMap.get(freq);
let node = linkLine.tail.pre;
linkLine.removeNode(node);
this.kvMap.delete(node.key);
if (linkLine.head.next === linkLine.tail) {
this.freqMap.delete(node.freq);
}
} else {
this.num++;
}
let node = new LFUNode(key, value, 0);
this.kvMap.set(key, node);
if (this.freqMap.has(0)) {
let linkLine = this.freqMap.get(0);
linkLine.addNode(node);
} else {
let linkLine = new LFULinkLine(node);
this.freqMap.set(0, linkLine);
}
this.minFreq = 0;
}
};
/**
* Your LFUCache object will be instantiated and called as such:
* var obj = new LFUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/