题解 | #设计LFU缓存结构#

package main

type MyLinkedNode struct{
    Key int
    Value int
    Pre *MyLinkedNode
    Next *MyLinkedNode
    Count int
}


type MyLFU struct{
    Head *MyLinkedNode
    Tail *MyLinkedNode
    size int
    cap int
}

/**
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
func LFU( operators [][]int ,  k int ) []int {
    lfu:=&MyLFU{
        Head: new(MyLinkedNode),
        Tail: new(MyLinkedNode),
        cap: k,
    }
    lfu.Head.Next=lfu.Tail
    lfu.Tail.Pre=lfu.Head
    result:=[]int{}
    for i:=0;i<len(operators);i++{
        if operators[i][0]==1{
            lfu.set(operators[i][1], operators[i][2])
        }else{
            result=append(result, lfu.get(operators[i][1]))
        }
    }
    return result
}

func(m *MyLFU)set(k,v int){
    cur:=m.Head.Next
    for cur!=m.Tail{
        if k==cur.Key{
            cur.Count+=1
            cur.Value=v
            m.move(cur)
            return
        }else{
            cur=cur.Next
        }
    }
    if m.size<m.cap{
        m.size++
        newNode:=&MyLinkedNode{
            Key:k,
            Value: v,
        }
        pre:=m.Tail.Pre
        pre.Next=newNode
        newNode.Pre=pre
        newNode.Next=m.Tail
        m.Tail.Pre=newNode
    }else{
        pre:=m.Tail.Pre
        pre.Key=k
        pre.Value=v
        pre.Count=0
    }
    m.move(m.Tail.Pre)
}

func(m *MyLFU)get(k int)int{
    cur:=m.Head.Next
    for cur!=m.Tail{
        if cur.Key==k{
            v:=cur.Value
            cur.Count+=1
            m.move(cur)
            return v
        }else{
            cur=cur.Next
        }
    }
    return -1
}

func(m *MyLFU)move(s *MyLinkedNode){
    tmp:=s.Pre
    var d *MyLinkedNode
    for tmp!=m.Head{
        if tmp.Count>s.Count{
            d=tmp.Next
            break
        }else{
            tmp=tmp.Pre
        }
    }
    if d==nil{d=m.Head.Next}
    if d==s{return}
    pre1:=d.Pre
    pre2:=s.Pre
    next2:=s.Next
    pre2.Next=next2
    next2.Pre=pre2

    pre1.Next=s
    s.Pre=pre1
    s.Next=d
    d.Pre=s

}