LeetCode(460):手写LFU算法
2021-01-08 04:31
标签:最小 多个 type efi 映射 capacity 图片 key 手写 依据题目,可以列举出几个显而易见的事实: 如果我们希望在O(1)的时间复杂度内解决这些需求,就要逐个击破: 为了实现“最不经常使用”的功能,我们需要: 至此,我们就可以写出LFUcache的基本数据结构(初始化): 定义节点类和双向链表类: get方法的逻辑很简单: put方法的逻辑稍微有点复杂: 要注意的是:在更新freqToKeys时,要先判断是否有freq=1的key链表 如果没有,要先创建一个空的双向链表 然后通过addLast方法,将新的key节点插入到链表尾部 首先通过freqToKeys 找到minFreq对应的链表 记为list 然后删除list的第一个节点 为HashedList编写一个removeFirst方法,在删除第一个节点的同时,返回其key值 如果删除后,list变为空,则在freqToKeys中删除这个freq对应的映射 最后更新另外2个哈希表 为什么在删除minFreq对应的映射时,不需要更新minFreq呢? 因为removeMinFreqKey只在put方法且新插入的key不存在的时候发生,在此之后,minFreq一定为1 首先 通过keyToFreq找到key对应的freq 记为freq 然后 更新keyToFreq 然后 更新 freqToKeys: 同样地,要处理freq链表为空 以及 freq+1链表不存在的这2种特殊情况 最后,为HashedList类编写一个remove方法,从链表中删除指定key的节点 附上完整的代码: LeetCode(460):手写LFU算法 标签:最小 多个 type efi 映射 capacity 图片 key 手写 原文地址:https://www.cnblogs.com/baebae996/p/14238303.html题目描述
实现思路
1、大致分析
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方法
LFUCache.prototype.get = function(key) {
if(!this.keyToVal.has(key)){
return -1
}
this.increaseFreq(key)
return this.keyToVal.get(key)
};
2.2、 put方法
LFUCache.prototype.put = function(key, value) {
if(this.capacity
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方法
removeFirst(){
var first = this.head.next
this.head.next = first.next
first.next.prev = this.head
this.size--
return first.key
}
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)
}
3.2、increaseFreq方法
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++
}
}
}
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
文章标题:LeetCode(460):手写LFU算法
文章链接:http://soscw.com/index.php/essay/40856.html