0868. 二进制间距

• 标签：位运算
• 难度：简单

题目链接

• 0868. 二进制间距 - 力扣

题目大意

描述：给定一个正整数 $n$。

要求：找到并返回 $n$ 的二进制表示中两个相邻 $1$ 之间的最长距离。如果不存在两个相邻的 $1$，返回 $0$。

说明：

• $1 \le n \le 10^9$。

示例：

• 示例 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。

解题思路

思路 1：遍历

1. 将正整数 $n$ 转为二进制字符串形式 $bin\underline{}n$。
2. 使用变量 $pre$ 记录二进制字符串中上一个 $1$ 的位置，使用变量 $ans$ 存储两个相邻 $1$ 之间的最长距离。
3. 遍历二进制字符串形式 $bin\underline{}n$ 的每一位，遇到 $1$ 时判断并更新两个相邻 $1$ 之间的最长距离。
4. 遍历完返回两个相邻 $1$ 之间的最长距离，即 $ans$。

思路 1：代码

class Solution:
    def binaryGap(self, n: int) -> int:
        bin_n = bin(n)
        pre, ans = 2, 0
        
        for i in range(2, len(bin_n)):
            if bin_n[i] == '1':
                ans = max(ans, i - pre)
                pre = i
            
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$。