Easy
题目描述
给定一个正整数 n，找出并返回 n 的二进制表示中任意两个相邻的 1 之间的最长距离。如果不存在两个相邻的 1，返回 0。
如果只有 0 将两个 1 分隔开（可能没有 0），则称这两个 1 是相邻的。两个 1 之间的距离是它们位位置的绝对差值。例如，“1001” 中的两个 1 的距离为 3。
示例 1：
输入: n = 22
输出: 2
解释: 22 的二进制是 "10110"。
第一对相邻的 1 是 "10110"，距离为 2。
第二对相邻的 1 是 "10110"，距离为 1。
答案是这两个距离中较大的那个，即 2。
注意 "10110" 不是有效的一对，因为在两个加下划线的 1 之间有一个 1 分隔。
示例 2：
输入: n = 8
输出: 0
解释: 8 的二进制是 "1000"。
在 8 的二进制表示中没有相邻的两个 1，所以返回 0。
示例 3：
输入: n = 5
输出: 2
解释: 5 的二进制是 "101"。
约束条件：
1 <= n <= 10^9
解题思路
这道题要求找到二进制表示中相邻两个 1 之间的最大距离。
基本思路：
- 遍历数字 n 的二进制表示中的每一位
- 记录上一个 1 的位置，当遇到新的 1 时计算距离
- 更新最大距离
具体实现方法：
方法一：位运算（推荐）
- 使用位运算逐位检查，从右到左扫描
- 记录上一个 1 的位置索引
- 当找到新的 1 时，计算当前位置与上一个 1 位置的距离
- 更新最大距离
方法二：字符串转换
- 将数字转为二进制字符串，然后遍历字符串找 1 的位置
- 计算相邻 1 之间的距离
方法一更高效，避免了字符串转换的开销。算法的关键是正确维护位置索引和最大间距。
时间复杂度是 O(log n)，因为需要检查 n 的所有二进制位。空间复杂度是 O(1)。
代码实现
class Solution {
public:
int binaryGap(int n) {
int maxGap = 0;
int lastPos = -1;
int pos = 0;
while (n > 0) {
if (n & 1) {
if (lastPos != -1) {
maxGap = max(maxGap, pos - lastPos);
}
lastPos = pos;
}
n >>= 1;
pos++;
}
return maxGap;
}
};
class Solution:
def binaryGap(self, n: int) -> int:
max_gap = 0
last_pos = -1
pos = 0
while n > 0:
if n & 1:
if last_pos != -1:
max_gap = max(max_gap, pos - last_pos)
last_pos = pos
n >>= 1
pos += 1
return max_gap
public class Solution {
public int BinaryGap(int n) {
int maxGap = 0;
int lastPos = -1;
int pos = 0;
while (n > 0) {
if ((n & 1) == 1) {
if (lastPos != -1) {
maxGap = Math.Max(maxGap, pos - lastPos);
}
lastPos = pos;
}
n >>= 1;
pos++;
}
return maxGap;
}
}
var binaryGap = function(n) {
let maxGap = 0;
let lastPos = -1;
let pos = 0;
while (n > 0) {
if (n & 1) {
if (lastPos !== -1) {
maxGap = Math.max(maxGap, pos - lastPos);
}
lastPos = pos;
}
n >>= 1;
pos++;
}
return maxGap;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(log n) | 需要遍历 n 的所有二进制位 |
| 空间复杂度 | O(1) | 只使用常数额外空间 |