题目
Given a positive integer N, find and return the longest distance between two consecutive 1’s in the binary representation of N.
If there aren’t two consecutive 1’s, return 0.
Example 1:
Input: 22
Output: 2
Explanation:
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1’s.
The first consecutive pair of 1’s have distance 2.
The second consecutive pair of 1’s have distance 1.
The answer is the largest of these two distances, which is 2.
Example 2:
Input: 5
Output: 2
Explanation:
5 in binary is 0b101.
Example 3:
Input: 6
Output: 1
Explanation:
6 in binary is 0b110.
Example 4:
Input: 8
Output: 0
Explanation:
8 in binary is 0b1000.
There aren’t any consecutive pairs of 1’s in the binary representation of 8, so we return 0.
Note:
1 <= N <= 10^9
题目地址
讲解
首先一定要理解题目的意思，题目的意思是两个连续 1 之间的最大距离，比如 11，最大距离是 1，10001 最大距离是 4.
然后简单的做法是，记录每个 1 的坐标，然后算最大的差值。但这样要额外扫描一遍坐标数组。
我的代码做到了只扫描一遍 N，需要三个值进行记录，index 记录是否扫描到 1，count 记录每一段 1 的距离，max 记录最大距离。
Java 代码
class Solution {
public int binaryGap(int N) {
int index=0;
int count=0;
int max=0;
int temp = N;
while(temp>0){
if(temp%2==1){
if(index==1){
count++;
max = max<count?count:max;
count=0;
}else{
index = 1;
}
}else{
if(index==1){
count++;
max = max<count?count:max;
}
}
temp >>= 1;
}
return max;
}
}