题解 | #设计LFU缓存结构#[GO实现]

参考官方解题方案的GO代码实现，使用双哈希表和双向链表。

package main

import (
	"container/list"
	//"fmt"
	"math"
)

type Node struct{
    key,val,freq int
}

type LFUContainer struct{
    capacity,size,min_freq int
    freq_mp map[int]*list.List
    mp map[int]*list.Element
}

func NewLFUContainer(c int) LFUContainer{
    return LFUContainer{
        capacity: c,
        size: 0,
        min_freq: math.MaxInt,
        freq_mp: make(map[int]*list.List),
        mp: make(map[int]*list.Element),
    }
}

func (l *LFUContainer) update(e *list.Element,key ,value int){
    //存下原节点
    node:=e.Value.(Node)
    freq:=node.freq
    //从原频率map中删除该节点
    l.freq_mp[freq].Remove(e)
    //若当前频率没有对应节点，删除
    if l.freq_mp[freq].Len()==0{
        delete(l.freq_mp, freq)
        //如果当前频率为最小，最小频率+1
        if l.min_freq==freq{
            l.min_freq++
        }
    }
    if _,ok:=l.freq_mp[freq+1];!ok{
        //更新频率的链表不存在
        l.freq_mp[freq+1]=list.New()
    }
    //更新节点值
    node.val=value
    node.freq++
    //插入链表表头
    l.freq_mp[freq+1].PushFront(node)
    //更新map
    l.mp[key]=l.freq_mp[freq+1].Front()
}

func (l *LFUContainer) deleteLFU() {
    //获取双向链表,元素,key
    linkl:=l.freq_mp[l.min_freq]
    e:=linkl.Back()
    key:=e.Value.(Node).key
    //删除链表尾部节点
    linkl.Remove(e)
    //如果链表为空，从频率map中删除
    if linkl.Len()==0{
        delete(l.freq_mp, l.min_freq)
    }
    //从map中移除key对应节点
    delete(l.mp, key)
}

func (l *LFUContainer) set(key,value int) {
    //检查key是否在l中存在
    if e,ok:=l.mp[key];ok{
        //存在，对应更新情况
        l.update(e,key,value)
        return
    }
    //插入情况
    //判断是否达到最大容量
    if l.size==l.capacity{
        //执行删除LFU操作
        l.deleteLFU()
    }else{
        l.size++
    }
    //设置最小频率
    l.min_freq=1
    node:=Node{key,value,1}
    //在频率map中插入该节点
    if _,ok:=l.freq_mp[1];!ok{
        l.freq_mp[1]=list.New()
    }
    l.freq_mp[1].PushFront(node)
    //在map中插入该节点
    l.mp[key]=l.freq_mp[1].Front()
}

func (l *LFUContainer) get(key int) int{
    res:=-1
    //查找map
    if e,ok:=l.mp[key];ok{
        //获取值
        res=e.Value.(Node).val
        //更新频率
        l.update(e, key, res)
    }
    return res
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
func LFU( operators [][]int ,  k int ) []int {
    // write code here
    container:=NewLFUContainer(k)
    res:=make([]int,0)
    for _,op:=range operators{
        switch op[0]{
            case 1:
                container.set(op[1], op[2])
            case 2:
            res = append(res, container.get(op[1]))
        }
    }
    return res
}