05 August 2008
一个整数的二进制表达式中，两个1之间的最长距离，相邻的距离为1，也就是找两个1之间最多能有多少个0，如果没有两个1就返回0
方法1，时间O(logn)，用临时数组 中记录数字 N 二进制表示中 1 的位置。要找到二进制表示中连续的 1 的最长距离，就是找到临时数组相邻元素差的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int binaryGap(int N) {
int[] temp = new int[32];
int t = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) != 0)
temp[t++] = i;
int result = 0;
for (int i = 0; i < t - 1; ++i)
result = Math.max(result, temp[i + 1] - temp[i]);
return result;
}
}
方法2，时间O(logn),一次遍历，因为我们只关心连续的 1，因此我们不需要存储整个数组。只需要记住前一个 1 的位置，用一个临时变量记住上一个1的位置即可
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int binaryGap(int N) {
int last = -1, result = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) > 0) {
if (last >= 0)
result = Math.max(result, i - last);
last = i;
}
return result;
}
}