golang刷leetcode：设计LFU缓存结构

[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3

[4,-1]

在执行"1 4 4"后，"1 1 1"被删除。因此第二次询问的答案为-1解题思路：
1，lfu和lru思路一样都是hash加双链表
2，不同的地方是node上需要保存频率数据
3，需要一个map保存频率到相同频率的最前面节点的映射
4，每次访问的时候需要把节点摘除，如果存在频率加1的节点，移动到加1节点前面
5，如果不存在，移动到当前频率节点前面，频率加16，如果当前节点后续节点和当前节点频率一样，当前频率指向下一个节点，否则删除这个频率
7，插入的时候如果容量没有满，插入在频率为1的节点的前面，或者末尾
8，如果满了删除末尾节点和频率，如果末尾节点和前面频率一致，不删除
代码实现

package main
import . "nc_tools"
//import "fmt"
/**
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
func LFU( operators [][]int ,  k int ) []int {
    // write code here
    l:=NewLFU(k)
    var r []int
    for _,op:=range operators{
        if op[0]==1{
            l.set(op[1],op[2])
        }else{
            r=append(r,l.get(op[1])) 
        }
       /* for k,v:=range l.freqToNode{
            fmt.Print(v.key,k)
        }
        fmt.Print(":")
        for v:=l.head.next;v!=l.tail;v=v.next{
            fmt.Print(v.key)
        }
        fmt.Println("")*/
    }
    return r
}

type Node struct{
    prev,next *Node
    key,val,frequency int
}

type LFUCache struct{
    m map[int]*Node
    head,tail *Node
    freqToNode map[int]*Node
    capacity int
}

func NewLFU(capacity int)*LFUCache{
    c:=&LFUCache{
        head:&Node{},
        tail:&Node{},
        m:make(map[int]*Node),
        freqToNode:make(map[int]*Node),
        capacity:capacity,
    }
    c.head.next=c.tail
    c.tail.prev=c.head
    return c
}

func (l*LFUCache)get(key int)int{
    v,ok:=l.m[key]
    if !ok{
        return -1
    }
    if l.freqToNode[v.frequency]==v{
        if v.next!=l.tail && v.next.frequency==v.frequency{
            l.freqToNode[v.frequency]=v.next
        }else{
          delete(l.freqToNode,v.frequency)
        }
     }
     v.frequency++
    if v.prev==l.head{
         l.freqToNode[v.frequency]=v
        return v.val
    }
  
    prev,ok:=l.freqToNode[v.frequency]
     l.remove(v)
    if ok{
        l.addPrev(prev,v)        
        l.freqToNode[v.frequency]=v
        return v.val
    }
    prev=l.freqToNode[v.frequency-1]
    l.addPrev(prev,v)     
    l.freqToNode[v.frequency]=v
    return v.val    
}

func (l*LFUCache)addPrev(cur,node *Node){
    cur.prev.next=node
    node.prev=cur.prev
    
    cur.prev=node
    node.next=cur
}
func (l*LFUCache)remove(node *Node){
    node.prev.next=node.next
    node.next.prev=node.prev
}

func (l*LFUCache)set(key,val int){
    if l.get(key)!=-1{
        v:=l.m[key]
        v.val=val
        return 
    }
    node:=&Node{
        key:key,
        val:val,
        frequency:1,
    }
   
    
    if len(l.m)>=l.capacity{
         cur:=l.tail.prev
        if cur==l.head{
            return 
        }
        if cur.prev.frequency!=cur.frequency{
            delete( l.freqToNode,cur.frequency)
        }
        
        l.remove(cur)
        delete(l.m,cur.key)
     }
    l.m[key]=node
    cur,ok:=l.freqToNode[1]
    if ok{
        l.addPrev(cur,node)
        l.freqToNode[1]=node
        return 
    }
    
    l.addPrev(l.tail,node)
    l.freqToNode[1]=node
    return  
}