LeetCode(460)：手写LFU算法

题目描述

image

实现思路

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
};
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,718评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,683评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,207评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,755评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,862评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,050评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,136评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,882评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,330评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,651评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,789评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,477评论 4赞 333
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,135评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,864评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,099评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,598评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,697评论 2赞 351