LFU 算法
/**
* @param {number} capacity
*/
var LFUCache = function (capacity) {
this.map = new Map();// 存放 key:node 的索引,便于快速访问节点
this.freqArr = new Array() // 定义一个频次数组,存放一个双向链表
this.capacity = capacity // 可以保存的容量
this.minFreq = 1 // 方便找到访问次数最小的双向链表,默认设置为 1
this.freqArr.push(new DoubleLink())// 插入一个双向链表
this.freqArr.push(new DoubleLink())// 插入一个双向链表,因为 minFreq 默认设置为了 1,所以要push两次
};
/**
* @param {number} key
* @return {number}
*/
// 访问
LFUCache.prototype.get = function (key) {
const node = this.map.get(key); // 获取双向链表的 node 节点
if (node) {
this._updateFreq(node) // 如果节点存在,则更新频次
return node.value // 并返回 node节点值
}
return -1 // 否则返回-1
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
// 设置
LFUCache.prototype.put = function (key, value) {
if (this.capacity <=0 ) return // 如果容量设置为<=0,则直接退出
const node = this.map.get(key) // 获取 node 节点
if (node) {
// 如果节点值存在,则更新频次
this._updateFreq(node)
// 并设置节点的值为最新的值
node.value = value
return true
}
// 如果当前容量>=设定容量
if (this.map.size >= this.capacity) {
// 获取当前最小频次下双向链表中的最后一个节点,并删除
const lastNode = this.freqArr[this.minFreq].pop()
// 删除 map 维护的该节点的 key
this.map.delete(lastNode.key)
}
// 创建新的双向链表节点
const newNode = new DoubleLinkNode(key, value)
// 由于是新创建节点,则第一次频次为 1,获取频次为 1 的双向链表,并在最前面插入新节点
this.freqArr[1].unshift(newNode)
// 不管之前最小频次到几,这里重置为 1
this.minFreq = 1
// map 中新增 key:node 映射
this.map.set(key, newNode)
};
// 更新节点频次
LFUCache.prototype._updateFreq = function (node) {
// 获取节点频次
const freq = node.freq
// 给节点中的频次变量+1
node.incFreq()
// 删除原频次对应的双向链表中的该节点
this.freqArr[freq].del(node)
// 获取+1 后的频次数
const newFreq = freq + 1
// 如果频次数组对应的新的频次数的索引下没有节点
if (!this.freqArr[newFreq]) {
// 则给该频次数下赋值为新的双向链表
this.freqArr[newFreq] = new DoubleLink()
}
// 否则,直接获取对应频次数下的双向链表,并在开头插入新节点
this.freqArr[newFreq].unshift(node)
// 最小访问次数等于freq,并且freq的双向链表指向为空,证明需要更新最小访问次数为最新的访问次数,避免原频次下节点删除后对应的节点已不存在
if (freq === this.minFreq && this.freqArr[freq].size === 0) {
this.minFreq = newFreq
}
}
// 双向链表节点
var DoubleLinkNode = function (key, value) {
this.key = key
this.value = value
this.freq = 1
this.prev = null
this.next = null
}
// 更新双向链表节点的频次数,+1
DoubleLinkNode.prototype.incFreq = function () {
this.freq++
}
// 双向链表
var DoubleLink = function () {
this.head = new DoubleLinkNode(-1, -1) // 创建头部节点
this.tail = new DoubleLinkNode(-1, -1) // 创建尾部节点
this.head.next = this.tail // 将头部节点的下一个节点指针指向尾部节点
this.tail.prev = this.head // 将尾部节点的上一个节点指针指向头部节点
this.size = 0 // 由于只有头尾,还没有插入节点,size 设为 0
}
// 双向链表的开头插入新节点方法
DoubleLink.prototype.unshift = function (node) {
const tmp = this.head.next
this.head.next = node
node.next = tmp
node.prev = this.head
tmp.prev = node
this.size++ // 记得更改节点长度
}
// 双向链表删除节点方法
DoubleLink.prototype.del = function (node) {
const prev = node.prev
const next = node.next
prev.next = next
next.prev = prev
delete node.prev
delete node.next
this.size-- // 记得更改节点长度
}
// 双向链表从默认删除节点并返回该节点的方法
DoubleLink.prototype.pop = function () {
const lastNode = this.tail.prev
this.del(lastNode)
return lastNode
}
源代码链接:https://leetcode.cn/problems/lfu-cache/solution/javascriptban-jie-ti-si-lu-by-ityou-o-vuw5/
本文主要给该代码增加了注释,便于理解。
转载请注明出处:https://www.cnblogs.com/beileixinqing/p/16669653.html