LeetCode Practice（一）

Mandelbrot_Kobe · · 1073 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

第一题：计算二进制数两个1之间的间距

题目：

我的思路

英文翻译过来就是把数字化成二进制，计算两个1之间的最大间距。1000,1100,1010的最大间距分别是0,1,2.以此类推
我的第一反应是大学数字逻辑课上的一个知识点，十进制转化为二进制——短除法！
也就是说，在接收到输入的十进制数之后，利用短除法，转化为二进制数。转化的过程进行间距的计算
虽然短除法先计算出来的是二进制低位的数，但是1010的间距从左往右数和从右往左数，结果是等价的
实现如下：

func BiggestGap(n int) int {
    distance,temp := 0,0
    bValue := 0
    for n,bValue = bDiv(n);bValue==0; {
        n,bValue = bDiv(n)
    }
    for (n>0)  {
        n,bValue = bDiv(n)
        temp+=1
        if bValue==1 {
            if temp>distance {
                distance=temp
            }
            temp = 0
        }
    }
    return distance
}

func bDiv(n int)(remainder,bValue int){
    if n%2 == 0 {
        return n/2,0
    }else {
        return (n-1)/2,1
    }
}

别人的思路

看完题目，肯定是得自己先琢磨。琢磨完了，得学习学习别人是怎么分析的。先贴上别人的实现，源码是C++，我翻译成golang版本了
别人家的版本：

func BinaryDistance(n uint) int {
    var i uint
    distance,last:=0,-1
    for i=0;i<32;i++{
        if (n >> i) & 1 !=0 {
            if last>=0 {
                distance = max(distance,int(i)-last)
            }
            last = int(i)
        }
    }
    return distance
}

func max(numbers ...int)  int{
    max := 0
    for _,num := range numbers{
        if num>max {
            max=num
        }
    }
    return max
}