LeetCode(460):手写LFU算法
题目描述
实现思路
1、大致分析
依据题目,可以列举出几个显而易见的事实:
- 调用get方法, 返回该key对应的val
- 调用get或者put方法访问某个key,该key对应的freq加一
- 如果在容量满了以后进行插入,则需要将freq最小的key删除,如果最小的freq对应多个key,则删除其中最旧(最早put进来)的那个
如果我们希望在O(1)的时间复杂度内解决这些需求,就要逐个击破:
- 使用一个Map存储key到val的映射,命名为keyToVal
- 使用一个Map存储key到freq的映射,命名为keyToFreq
为了实现“最不经常使用”的功能,我们需要:
- 使用一个Map存储freq到key的映射,命名为freqToKeys
- 用变量minFreq来记录当前最小的freq
- 可能有多个key具有相同的freq,所以每个freq应该对应一个key的列表
- 当容量已满时,我们需要淘汰最不经常使用且最早被插入的key,这就要求freq对应的key列表要有时序
- 因此,每个freq对应的key用双向链表来维护:要淘汰key时,删除链表的第一个节点;要更新key时,在链表尾部插入新节点
至此,我们就可以写出LFUcache的基本数据结构(初始化):
var LFUCache = function(capacity) {
this.keyToVal = new Map()
this.keyToFreq = new Map()
this.freqToKeys = new Map()
this.capacity = capacity
this.minFreq = 0
};
定义节点类和双向链表类:
class Node {
constructor(key){
this.key = key
}
}
class HashedList {
constructor(){
this.head = new Node(0)
this.head.next = this.tail
this.tail = new Node(0)
this.tail.prev = this.head
this.size = 0
}
}
2.1、get方法
get方法的逻辑很简单:
- 在keyToVal中查找,找不到则返回-1,找到则返回val
- 增加key对应的freq
LFUCache.prototype.get = function(key) {
if(!this.keyToVal.has(key)){
return -1
}
this.increaseFreq(key)
return this.keyToVal.get(key)
};
2.2、 put方法
put方法的逻辑稍微有点复杂:
- 在keyToVal中查找key是否存在:若存在,则修改key对应的val,并增加key对应的freq
- 若不存在:判断容量是否已满
- 若容量已满,则淘汰一个freq最小的key
- 更新3个哈希表
LFUCache.prototype.put = function(key, value) {
if(this.capacity <= 0){
return
}
// key已存在
if(this.keyToVal.has(key)){
this.keyToVal.set(key,value)
this.increaseFreq(key)
return
}
// key不存在,且容量已满
if(this.capacity <= this.keyToVal.size){
this.removeMinFreqKey()
}
// 插入key和value,对应的freq为1
// 插入KV表
this.keyToVal.set(key,value)
// 插入KF表
this.keyToFreq.set(key,1)
// 插入FK表
if(!this.freqToKeys.has(1)){
let list = new HashedList()
this.freqToKeys.set(1,list)
}
this.freqToKeys.get(1).addLast(key)
this.minFreq = 1
};
要注意的是:在更新freqToKeys时,要先判断是否有freq=1的key链表
如果没有,要先创建一个空的双向链表
然后通过addLast方法,将新的key节点插入到链表尾部
addLast(key){
let x = new Node(key)
x.prev = this.tail.prev
x.next = this.tail
this.tail.prev.next = x
this.tail.prev = x
this.size++
}
3.1、removeMinFreqKey方法
首先通过freqToKeys 找到minFreq对应的链表 记为list
然后删除list的第一个节点
为HashedList编写一个removeFirst方法,在删除第一个节点的同时,返回其key值
removeFirst(){
var first = this.head.next
this.head.next = first.next
first.next.prev = this.head
this.size--
return first.key
}
如果删除后,list变为空,则在freqToKeys中删除这个freq对应的映射
最后更新另外2个哈希表
LFUCache.prototype.removeMinFreqKey = function(){
var list = this.freqToKeys.get(this.minFreq)
var deleteKey = list.removeFirst()
if(list.size === 0){
this.freqToKeys.delete(this.minFreq)
}
this.keyToVal.delete(deleteKey)
this.keyToFreq.delete(deleteKey)
}
为什么在删除minFreq对应的映射时,不需要更新minFreq呢?
因为removeMinFreqKey只在put方法且新插入的key不存在的时候发生,在此之后,minFreq一定为1
3.2、increaseFreq方法
首先 通过keyToFreq找到key对应的freq 记为freq
然后 更新keyToFreq
然后 更新 freqToKeys:
- 将key从freq对应的链表中删除
- 将key加入freq+1对应的链表中
同样地,要处理freq链表为空 以及 freq+1链表不存在的这2种特殊情况
LFUCache.prototype.increaseFreq = function(key) {
var freq = this.keyToFreq.get(key)
this.keyToFreq.set(key,freq+1)
this.freqToKeys.get(freq).remove(key)
if(!this.freqToKeys.has(freq+1)){
let list = new HashedList()
this.freqToKeys.set(freq+1,list)
}
this.freqToKeys.get(freq+1).addLast(key)
if(this.freqToKeys.get(freq).size === 0){
this.freqToKeys.delete(freq)
if(freq === this.minFreq){
this.minFreq++
}
}
}
最后,为HashedList类编写一个remove方法,从链表中删除指定key的节点
remove(key){
var p = this.head.next
while(p != this.tail){
if(p.key === key){
break
}
p = p.next
}
p.prev.next = p.next
p.next.prev = p.prev
this.size--
}
代码实现(JavaScript)
附上完整的代码:
class Node {
constructor(key){
this.key = key
}
}
class HashedList {
constructor(){
this.head = new Node(0)
this.head.next = this.tail
this.tail = new Node(0)
this.tail.prev = this.head
this.size = 0
}
addLast(key){
let x = new Node(key)
x.prev = this.tail.prev
x.next = this.tail
this.tail.prev.next = x
this.tail.prev = x
this.size++
}
remove(key){
var p = this.head.next
while(p != this.tail){
if(p.key === key){
break
}
p = p.next
}
p.prev.next = p.next
p.next.prev = p.prev
this.size--
}
removeFirst(){
var first = this.head.next
this.head.next = first.next
first.next.prev = this.head
this.size--
return first.key
}
}
var LFUCache = function(capacity) {
this.keyToVal = new Map()
this.keyToFreq = new Map()
this.freqToKeys = new Map()
this.capacity = capacity
this.minFreq = 0
};
LFUCache.prototype.removeMinFreqKey = function(){
var list = this.freqToKeys.get(this.minFreq)
var deleteKey = list.removeFirst()
if(list.size === 0){
this.freqToKeys.delete(this.minFreq)
}
this.keyToVal.delete(deleteKey)
this.keyToFreq.delete(deleteKey)
}
LFUCache.prototype.increaseFreq = function(key) {
var freq = this.keyToFreq.get(key)
this.keyToFreq.set(key,freq+1)
this.freqToKeys.get(freq).remove(key)
if(!this.freqToKeys.has(freq+1)){
let list = new HashedList()
this.freqToKeys.set(freq+1,list)
}
this.freqToKeys.get(freq+1).addLast(key)
if(this.freqToKeys.get(freq).size === 0){
this.freqToKeys.delete(freq)
if(freq === this.minFreq){
this.minFreq++
}
}
}
LFUCache.prototype.get = function(key) {
if(!this.keyToVal.has(key)){
return -1
}
this.increaseFreq(key)
return this.keyToVal.get(key)
};
LFUCache.prototype.put = function(key, value) {
if(this.capacity <= 0){
return
}
if(this.keyToVal.has(key)){
this.keyToVal.set(key,value)
this.increaseFreq(key)
return
}
if(this.capacity <= this.keyToVal.size){
this.removeMinFreqKey()
}
this.keyToVal.set(key,value)
this.keyToFreq.set(key,1)
if(!this.freqToKeys.has(1)){
let list = new HashedList()
this.freqToKeys.set(1,list)
}
this.freqToKeys.get(1).addLast(key)
this.minFreq = 1
};
LeetCode(460):手写LFU算法
原文地址:https://www.cnblogs.com/baebae996/p/14238303.html