LeetCode-Practice一

jiezi

5 年前

题目：

英文翻译过来就是把数字化成二进制，计算两个 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 的距离，比之前保存的最大间距大，更新，小，丢弃，调整位置继续计算

LeetCode-Practice一

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

我的思路

别人的思路