LeetCode Practice（一）

第一题：计算二进制数两个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
}

• 这个思路的关键点是 xxxxx0 & 000001的结果恒为零，xxxxx1 & 000001的结果恒为1（x的意思是为0或1）。
• 有了这个计算基础之后，加上int类型默认是32位，借助移位运算符 >>，就能够判断二进制数的每一位是0还是1了
• 最后这部分就没什么难度了，不断计算相邻两个1的距离，比之前保存的最大间距大，更新，小，丢弃，调整位置继续计算