Solutions CS101

Appearance

E868.二进制间距 ​

bit manipulation, https://leetcode.cn/problems/binary-gap/

给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。

如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3 。

示例 1：

输入：n = 22
输出：2
解释：22 的二进制是 "10110" 。
在 22 的二进制表示中，有三个 1，组成两对相邻的 1 。
第一对相邻的 1 中，两个 1 之间的距离为 2 。
第二对相邻的 1 中，两个 1 之间的距离为 1 。
答案取两个距离之中最大的，也就是 2 。

示例 2：

输入：n = 8
输出：0
解释：8 的二进制是 "1000" 。
在 8 的二进制表示中没有相邻的两个 1，所以返回 0 。

示例 3：

输入：n = 5
输出：2
解释：5 的二进制是 "101" 。

提示：

  • 1 <= n <= 10^9

思路：遍历二进制字符串，记录上一个 '1' 的位置，并在遇到新的 '1' 时更新最大距离。

python
class Solution:
    def binaryGap(self, n: int) -> int:
        s = bin(n)[2:]
        max_dis = 0
        left, right = 0, 0
        for i in range(1, len(s)):
            if s[i] == '1':
                max_dis = max(max_dis, i - left)
                left = i
        
        return max_dis

为了代码的清晰性和鲁棒性，可以稍作优化，使其逻辑更明确，并避免依赖“s[0] 一定是 '1'”这一隐含前提（尽管在本题中成立）。

此外，还可以不转成字符串，直接用位运算处理，更高效、更符合“二进制间距”的题意。

优化版本 1：保持字符串思路，但逻辑更清晰

python
class Solution:
    def binaryGap(self, n: int) -> int:
        s = bin(n)[2:]
        max_dis = 0
        prev = -1  # 上一个 '1' 的位置
        for i, ch in enumerate(s):
            if ch == '1':
                if prev != -1:
                    max_dis = max(max_dis, i - prev)
                prev = i
        return max_dis

优点：

  • 明确只在两个 '1' 之间计算距离。
  • 初始 prev = -1 表示尚未遇到第一个 '1'，逻辑清晰。
  • 避免了对 s[0] == '1' 的隐式依赖（虽然实际成立）。

优化版本 2：使用位运算（推荐，更高效）

python
class Solution:
    def binaryGap(self, n: int) -> int:
        max_dis = 0
        prev = -1
        i = 0
        while n:
            if n & 1:
                if prev != -1:
                    max_dis = max(max_dis, i - prev)
                prev = i
            n >>= 1
            i += 1
        return max_dis

优点：

  • 不需要生成字符串，节省空间。
  • 时间复杂度相同 O(log n)，但常数更小。
  • 更贴近底层二进制操作，适合面试展示位运算能力。

总结

你原来的代码在 LeetCode 上可能能通过（因为 bin(n)[2:] 确实以 '1' 开头），但存在逻辑隐患（比如若输入允许前导零就会出错）。推荐使用 优化版本 1 或 2，尤其是版本 2 的位运算解法更为优雅高效。