LeetCode 题解工作台
二进制间距
给定一个正整数 n ，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。 如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如， "1001" 中的两个 …
1
题型
8
代码语言
3
相关题
当前训练重点
简单 · 位运算·操作·driven·solution·strategy
答案摘要
我们用两个指针 和 分别表示上一个和当前的 的位置，初始时 $\textit{pre} = 100$, $\textit{cur} = 0$，然后遍历 的二进制表示，当遇到 时，计算当前位置和上一个 的位置之间的距离，并更新答案。 时间复杂度 $O(\log n)$，其中 是题目给定的整数。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 位运算·操作·driven·solution·strategy 题型思路
题目描述
给定一个正整数 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 <= 109
解题思路
方法一：位运算
我们用两个指针 和 分别表示上一个和当前的 的位置，初始时 , ，然后遍历 的二进制表示，当遇到 时，计算当前位置和上一个 的位置之间的距离，并更新答案。
时间复杂度 ，其中 是题目给定的整数。空间复杂度 。
class Solution:
def binaryGap(self, n: int) -> int:
ans = 0
pre, cur = inf, 0
while n:
if n & 1:
ans = max(ans, cur - pre)
pre = cur
cur += 1
n >>= 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log N) because each bit of n is processed once. Space complexity is O(1) since only a few variables are used to track positions and maximum distance. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Watch for off-by-one errors when calculating distances between 1's.
- question_mark
Check if the candidate efficiently uses bit operations instead of string conversion.
- question_mark
Listen for clarification questions on how to handle numbers with fewer than two 1's.
常见陷阱
外企场景- error
Counting the distance incorrectly when multiple zeros separate 1's.
- error
Converting to a string unnecessarily, increasing space complexity.
- error
Failing to update the maximum gap when the last bit is a 1.
进阶变体
外企场景- arrow_right_alt
Find the second-largest binary gap instead of the largest.
- arrow_right_alt
Compute the sum of all distances between consecutive 1's.
- arrow_right_alt
Return the positions of 1's that form the longest gap.