题解 | #牛群特殊路径的数量#

package main


type Solution struct {
     // write code here
    mp map[int]*Node
    cnt int
    left *Node
    right *Node
    cap   int
}


type Node struct{
    next *Node
    pre  *Node
    key  int
    val  int
}

func Constructor(capacity int) Solution {
    // write code here
    mp:=make(map[int]*Node)
    left:=new(Node)
    right:=new(Node)
    left.next=right
    right.pre=left
    return Solution{
        mp:mp,
        cnt:0,
        left:left,
        right:right,
        cap:capacity,
    }
}



func (this *Solution) get(key int) int {
    // write code here
    //1.判断是否存在，key不存在可直接返回-1
    node,ok:=this.mp[key]
    if !ok{
        return -1
    }
    //将原值删除重新插入
    this.delete(key)
    this.insert(key,node.val)
    return node.val
}


func (this *Solution) set(key int, value int)  {
    // write code here
    //判断是否存在
    _,ok:=this.mp[key]
    if ok{
        //若存在，将旧值删除，重新插入新值
        this.delete(key)
        this.insert(key,value)
    }else{
        //若不存在
        //判断是否cap满了
        if this.cap==this.cnt{
            //淘汰最前面的key
            this.taotai()
        }
        //插入到最后
        this.insert(key,value)
    }
}

func (this *Solution)delete(key int){
    node,_:=this.mp[key]
    l:=node.pre
    r:=node.next
    l.next=r
    r.pre=l
    delete(this.mp,key)
    this.cnt--
}
func (this *Solution)insert(key int,value int){
    node:=&Node{
        key:key,
        val:value,
    }
    pre:=this.right.pre
    pre.next=node
    node.pre=pre
    node.next=this.right
    this.right.pre=node
    this.cnt++
    this.mp[key]=node
}

func(this *Solution)taotai(){
    left:=this.left
    node:=left.next
    delete(this.mp,node.key)
    this.cnt--
    right:=node.next
    left.next=right
    right.pre=left
}