868. 二进制间距

Posted on Edited on In Views: Word count in article: 530 Reading time ≈ 1 mins.

868 二进制间距

题目链接：868. 二进制间距

解题思路

方法一：字符串转换解法

最直观的做法是调用内置函数将整数转换为二进制字符串（去掉前缀），然后遍历字符串，计算相邻 1 之间的距离。这种做法虽然容易实现，但没有充分利用整数在底层的二进制特性，并非最佳实践。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def binaryGap(self, n: int) -> int:
        t = bin(n)[2:]
        l = len(t)
        ans = 0
        first_flag = 1
        last_index = -1
        for i in range(l):
            if t[i] == '1' and first_flag:
                last_index = i
                first_flag = 0
                continue
            elif t[i] == '1' and not first_flag:
                ans = max(i - last_index, ans)
                last_index = i
                continue
            elif t[i] == '0':
                continue
        return ans

image-compressed.png

性能分析：通过字符串处理整数会涉及动态内存分配和逐字符的条件判断。这不仅降低了执行效率，且空间复杂度由理想情况下的 $O(1)$ 退化为 $O(\log n)$。

方法二：位运算解法（最优解）

整数在计算机底层本就以二进制形式存储，直接操纵位（Bitwise Operation）可以达到最优的时间与空间效率。

本题主要运用以下位运算逻辑：

  1. n & 1（按位与）：用于判断数字的最低位是否为 1。
  2. n >>= 1（右移赋值）：每次检查完最低位后，将数字整体向右平移一位。配合 n & 1 即可实现逐位检查。
  3. while n > 0：由于不断右移，当 n 的二进制表示中完全不再包含 1 时，整体值为 0，循环正常结束。

具体实现逻辑很简单：每次由于 n & 1 == 1 触发时，意味着读取到了新出现的 1。我们使用 cnt 累加当前的位数（位置），配合 pre 保存上一次遇到 1 时所在的位置，通过 max(res, cnt - pre) 更新最大跨度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def binaryGap(self, n: int) -> int:
        res = 0  # 记录最大的间距
        pre = -1  # 上一次出现 1 的位置
        cnt = 0  # 当前位的位置
        
        while n > 0:
            if n & 1:  # 当前位是 1
                if pre == -1:  # 第一次遇到 1
                    pre = cnt
                else:
                    res = max(res, cnt - pre)  # 更新最大间距
                    pre = cnt
            cnt += 1
            n >>= 1  # 右移一位
        return res

image-compressed.png