查找整数二进制表示中最长零序列

问题是将一个整数进行转换，将其表示为一串二进制数字，然后确定其中被“1”包围的最长的“0”序列。换句话说，如果二进制表示字符串不包含任何夹在“1”之间的“0”，则结果应为 0。

此外，二进制数中的零后缀，如果未被“1”包围，则不应被计算在内。以二进制形式表示，数字 9 是 1001。最长的零序列的长度是 00，因此二进制间隙为 2。那么，数字 20 的二进制形式是 10100。最长的零序列是 0，因此二进制间隙为 1。

方法一

• 将整数转换为二进制： 就像在 Java 中一样，可以通过 `Integer` 类将一个 int 转换为二进制字符串。
• 截断并识别间隙： 转换后，删除未被“1”包围的、跟在“1”后面的多余的零。然后，利用事实：二进制字符串可以在每个“1”处分割，并且只检查零序列的长度。
• 查找最长序列： 遍历列表，找到零序列的最大长度。

让我们在 Java 程序中实现上述方法。

文件名：LongestBinaryGap.java

输出

 
The longest binary gap for 529 is: 4   

时间复杂度： 顺便说一句，该算法的时间复杂度也是 O(log n)，因为在将整数转换为二进制格式后，算法只遍历二进制字符串或位数，这相当于 log n。

空间复杂度： 空间复杂度为 O(log n)，主要是由于存储了整数的二进制形式，其大小约为 log n。

方法二

• 跳过尾随零： 首先，为了正确表示间隙，必须移除给定二进制表示中的尾随零。
• 迭代位： 将给定的整数作为一个数字进行迭代，并计算两个“1”之间的“0”的位数。
• 跟踪最大间隙： 存储最大间隙长度以备后用，但不要存储整个二进制字符串。

让我们在 Java 程序中实现上述方法。

文件名：LongestBinaryGap.java

输出

 
The longest binary gap for 529 is: 4   

时间复杂度： 该解决方案的时间复杂度为 log(n)。这里，整数的每一位都需要一定的步数，而这些步数的数量与整数中存在的位数成正比。

空间复杂度： 空间复杂度为 O(1)，因为程序仅创建几个整数变量，而与输入的大小无关。

结论

基于字符串操作的第一个解决方案提供了一个常规、显而易见的解决方案，空间复杂度为 O(log n)，但仍然足够。然而，上述位操作不需要存储整个二进制字符串，并且通过仅操作每一位，具有 O(1) 的空间复杂度。

两者都属于 O(log n) 的时间复杂度，但第一种方法需要较少的空间，在空间受限的环境中，第二种方法是首选。