golang刷leetcode 经典（4） 实现跳表

Skiplist skiplist = new Skiplist();


skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除

0 <= num, target <= 20000
最多调用 50000 次 search, add, 以及 erase操作。

const MAX_LEVEL=10
type Skiplist struct {
  maxLevel int
  root []*Node   
}
type Node struct{
    level int
    next []*Node
    prev []*Node
    value int
    count int
}

func NewNode(level,value int)*Node{
   return &Node{
            level:level,
            value:value,
            next:make([]*Node,level+1),
            prev:make([]*Node,level+1),
            count:1,
        }
}

func Constructor() Skiplist {
    return Skiplist{
        maxLevel:-1,
    }
}

func (this *Skiplist) SearchPos(target int)*Node{
 if this.maxLevel==-1{
        return nil
    }
 next:=this.root[this.maxLevel]
 for level:=next.level;level>=0;level--{
    if target==next.value{
            return next
    }else if target<next.value{
            for next.prev[level]!=nil && target<=next.prev[level].value{
                next=next.prev[level]
            }
    }else{
           for next.next[level]!=nil && target>=next.next[level].value{
               next=next.next[level]
           }
    }
    //fmt.Println("search :",target," level",level)
 }
    return next
}

func (this *Skiplist) Search(target int) bool {
    n:=this.SearchPos(target)
    //this.Print()
    if n==nil{
        return false
    }
    return n.value==target
}
func(this *Skiplist)Print(){
    if this.root==nil{
        return
    }
    fmt.Println(*this)
    for i:=this.maxLevel;i>=0;i--{
    cur:=this.root[i]
    for cur!=nil && cur.next!=nil{
       fmt.Print("->[",cur.value,cur.count,"]")
       cur=cur.next[i]
    }
      fmt.Println(i)
    }
}

func(this*Skiplist)randomUpgrade()bool{
     rand.Seed(time.Now().UnixNano()) 
     r:=rand.Intn(7)%2
     if this.maxLevel>MAX_LEVEL{
         return false
     }
     //fmt.Println("rand:---",r) 
    return r==1
}

func(n*Node)InsertLevelNode(level int,nn *Node){
        if n==nil ||n.prev==nil || n.next==nil || nn==nil ||nn.prev==nil ||nn.next==nil{
            return
        }
        if n.value>nn.value {
           prev:=n.prev[level]

           n.prev[level]=nn
           nn.next[level]=n
           
           nn.prev[level]=prev

           if prev!=nil{
             prev.next[level]=nn
           }
        }else{
           next:=n.next[level]

           n.next[level]=nn
           nn.prev[level]=n

           nn.next[level]=next
           if next!=nil{
            next.prev[level]=nn
           }
        }
}

func (this *Skiplist) Add(num int)  {
     //this.Print()
     n:=this.SearchPos(num)
     if n==nil{
         this.maxLevel=0
         n=NewNode(0,num)
         this.root=append(this.root,n)
         return
     }

     if n.value==num{
         n.count++
         return 
     }

      
    if this.randomUpgrade(){
        this.maxLevel++
        nn:=NewNode(this.maxLevel,num)
        this.root=append(this.root,nn)
        
        for i:=1;i<=this.maxLevel-1;i++{
            in:=this.root[i]
            for in!=nil && in.value>num  && in.prev!=nil && in.prev[i]!=nil{
                in=in.prev[i]
            }
            for in!=nil && in.value<num && in.next!=nil && in.next[i]!=nil{
                in=in.next[i]
            }
            in.InsertLevelNode(i,nn)   
        }

        n.InsertLevelNode(0,nn)
    }else{
      nn:=NewNode(0,num)
      n.InsertLevelNode(0,nn)
    }
}

func (this*Skiplist)DeleteNode(n*Node,level int){
    if n==nil{
        return
    }
    next:=n.next[level]
    prev:=n.prev[level]
    //fmt.Println("next",next,"prev",prev)
    if prev!=nil{
        prev.next[level]=next
    }else{
        this.root[level]=next
    }
    if next!=nil{
         next.prev[level]=prev
    }
}

func (this *Skiplist) Erase(num int) bool {
    //this.Print()
    n:=this.SearchPos(num)
    if n!=nil{
    //fmt.Println("erease ",*n)
    }
    if n==nil || n.value!=num{
        return false
    }

    if n.count>1{
        n.count--
        return true
    }

    for i:=0;i<=n.level;i++{
        //fmt.Println("-->",i)
        this.DeleteNode(n,i)
    }
    //fmt.Println("-->")
    //this.Print()
    //level i 删除了，i+1 肯定删除了，特殊情况，n层都是最高index，
    count:=0
    for level:=this.maxLevel;n.level==this.maxLevel && level>=0 && this.root!=nil && this.root[level]==nil ;level--{
        count++
    }
    this.root=this.root[:len(this.root)-count]
    this.maxLevel-=count

    n.count--
    n.level=-1
    n.next=nil
    n.prev=nil
    n=nil

    return true  
}


/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */