LeetCode(460):手写LFU算法


	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

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » LeetCode(460):手写LFU算法