LeetCode 868. 二进制间距

LeetCode 868. 二进制间距

题目描述

给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离。如果不存在两个相邻的 1，返回 0。

• 距离定义为两个 1 的索引差值的绝对值（索引从最低位（0）开始向右增加）。
• 示例：
  • 输入：n = 22 (二进制 10110)，输出：2
  • 解释：22 的二进制是 10110，1 的位置为 1、2、4，相邻的 1 之间的距离分别为 1 和 2，最大为 2。

解法一：遍历每一位 + 记录上一个 1 的位置（最直观）

思路

从低位到高位依次检查 n 的每一位，用变量 last 记录上一个 1 出现的索引。当遇到一个新的 1 时，若 last 不是初始值 -1，则计算当前索引 i 与 last 的差值，更新最大距离 res。最后返回 res。

代码

classSolution{public:intbinaryGap(int n){int res =0, last =-1;// n 最大 10^9 < 2^30，检查 30 位即可for(int i =0; i <30;++i){if((n >> i)&1){// 当前位为 1if(last !=-1){ res =max(res, i - last);} last = i;// 更新上一个 1 的位置}}return res;}};

举例分析

以 n = 22（二进制 10110）为例，索引从低位到高位：

最终 res = 2，正确。

复杂度分析

• 时间复杂度：O(位数) ≈ O(30) = O(1)
• 空间复杂度：O(1)

解法二：逐位扫描 + 计数（另一种巧妙解法）

思路

同样从低位到高位扫描，用变量 cnt 记录从上一个 1 到当前位置所经过的位数（即当前已经遇到的连续 0 的个数 + 1）。初始化 cnt 为一个极小的负数（如 INT_MIN/2），确保第一个 1 出现时不会错误更新答案。

• 遇到 0：cnt++，表示距离增加 1。
• 遇到 1：
  • 用当前 cnt 更新最大距离 ans。
  • 重置 cnt = 1，表示从当前这个 1 开始，到下一个可能的 1 至少相隔 1 位。
• 循环结束返回 ans。

代码

classSolution{public:intbinaryGap(int n){int ans =0, cnt = INT_MIN /2;// 初始为极小负数，避免第一个 1 误更新while(n >0){if(n %2==0){// 当前最低位为 0 cnt++;}else{// 当前最低位为 1 ans =max(ans, cnt); cnt =1;} n /=2;// 右移一位}return ans;}};

举例分析

仍以 n = 22（二进制 10110）为例，从低位向高位处理：

• 初始：ans = 0, cnt = INT_MIN/2（假设 -1073741824）
• 第 0 位（0）：cnt++ → cnt = -1073741823
• 第 1 位（1）：遇到第一个 1，ans = max(0, -1073741823) = 0，cnt = 1
• 第 2 位（1）：ans = max(0, 1) = 1，cnt = 1
• 第 3 位（0）：cnt++ → cnt = 2
• 第 4 位（1）：ans = max(1, 2) = 2，cnt = 1

最终 ans = 2。

复杂度分析

• 时间复杂度：O(log n) ≈ O(30)
• 空间复杂度：O(1)

两种解法对比

两种方法本质上都是扫描所有二进制位，时间复杂度相同，可以根据个人喜好选择。

总结

本题是二进制位运算的基础题，主要考察对二进制表示的遍历和相邻 1 之间距离的计算。掌握这两种解法后，可以轻松应对类似的位操作问题。