英文原文
Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.
Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.
Example 1:
Input: n = 22 Output: 2 Explanation: 22 in binary is "10110". The first adjacent pair of 1's is "10110" with a distance of 2. The second adjacent pair of 1's is "10110" with a distance of 1. The answer is the largest of these two distances, which is 2. Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.
Example 2:
Input: n = 5 Output: 2 Explanation: 5 in binary is "101".
Example 3:
Input: n = 6 Output: 1 Explanation: 6 in binary is "110".
Example 4:
Input: n = 8 Output: 0 Explanation: 8 in binary is "1000". There aren't any adjacent pairs of 1's in the binary representation of 8, so we return 0.
Example 5:
Input: n = 1 Output: 0
Constraints:
1 <= n <= 109
中文题目
给定一个正整数 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 = 5 输出：2 解释： 5 的二进制是 "101" 。
示例 3：
输入：n = 6 输出：1 解释： 6 的二进制是 "110" 。
示例 4：
输入：n = 8 输出：0 解释： 8 的二进制是 "1000" 。 在 8 的二进制表示中没有相邻的两个 1，所以返回 0 。
示例 5：
输入：n = 1 输出：0
提示：
1 <= N <= 10^9
通过代码
官方题解
方法一：记录索引
因为我们想知道 N 二进制下连续 1 之间的距离，所以我们记录 1 在二进制表示中的位置。例如，若 N = 22 = 0b10110。则我们会记下 A = [1, 2, 4]。则我们可以在数组中计算我们的答案。
算法：
在列表 A 中记录数字 N 二进制表示中 1 的位置。
要找到二进制表示中连续的 1 的最长距离，就是找到数组 A 中相邻元素差的最大值。
[solution1-Python]class Solution(object): def binaryGap(self, N): A = [i for i in xrange(32) if (N >> i) & 1] if len(A) < 2: return 0 return max(A[i+1] - A[i] for i in xrange(len(A) - 1))
[solution1-Java]class Solution { public int binaryGap(int N) { int[] A = new int[32]; int t = 0; for (int i = 0; i < 32; ++i) if (((N >> i) & 1) != 0) A[t++] = i; int ans = 0; for (int i = 0; i < t - 1; ++i) ans = Math.max(ans, A[i+1] - A[i]); return ans; } }
复杂度分析
- 时间复杂度：$O(\log N)$。
- 空间复杂度：$O(\log N)$，数组
A所使用的空间。
方法二：一次遍历
在方法一中我们用数组 A 记录了数字 N 二进制表示中的 1 的位置。
因为我们只关心连续的 1，因此我们不需要存储整个数组。只需要记住前一个 1 的位置。
算法：
我们用 last 存储上一个 1 的位置。如果数字 N 在第 i 个位置为 1，则我们的候选答案为 i - last，然后更新 last = i。
[solution2-Python]class Solution(object): def binaryGap(self, N): last = None ans = 0 for i in xrange(32): if (N >> i) & 1: if last is not None: ans = max(ans, i - last) last = i return ans
[solution2-Java]class Solution { public int binaryGap(int N) { int last = -1, ans = 0; for (int i = 0; i < 32; ++i) if (((N >> i) & 1) > 0) { if (last >= 0) ans = Math.max(ans, i - last); last = i; } return ans; } }
复杂度分析
- 时间复杂度：$O(\log N)$。
- 空间复杂度：$O(1)$。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 16924 | 27089 | 62.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
