LeetCode 868：二进制间距超详细题解

LeetCode 868二进制间距超详细题解LeetCode 868. 二进制间距【模拟遍历优化】超详细题解题目描述给定一个正整数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 8输出0解释8 的二进制是 “1000” 。在 8 的二进制表示中没有相邻的两个 1所以返回 0 。示例 3输入n 5输出2解释5 的二进制是 “101” 两个 1 之间的距离为 2 。提示1 n 10^9解题思路1. 核心思路模拟遍历最直观易懂本题的核心是找到二进制中所有 1 的位置计算相邻两个 1 之间的距离取最大值。核心步骤分为 3 步记录所有 1 的位置将正整数n转换成二进制遍历二进制的每一位记录下所有值为 1 的位的索引从 0 开始计数最右边为第 0 位计算相邻 1 的距离遍历记录的 1 的位置列表计算每两个相邻位置的差值后一个位置 - 前一个位置这个差值就是两个相邻 1 之间的距离取最大值并返回如果 1 的个数小于 2即没有相邻的 1返回 0否则返回所有相邻距离中的最大值。2. 优化思路一次遍历空间优化上述基础思路需要额外存储所有 1 的位置空间复杂度为 O(k)k 是二进制中 1 的个数。优化后可实现一次遍历、O(1) 额外空间记录上一个 1 的位置初始化一个变量如last_one用于存储上一个出现 1 的位置初始值设为 -1表示尚未找到第一个 1遍历二进制每一位从第 0 位开始依次判断当前位是否为 1计算距离并更新最大值如果当前位是 1且last_one ! -1说明已经找到过前一个 1则计算当前位置与last_one的差值更新最大距离同时将last_one更新为当前位置如果是第一个 1last_one -1则直接将last_one设为当前位置返回结果遍历结束后返回记录的最大距离若未找到两个及以上 1最大距离仍为 0。3. 二进制遍历技巧关键细节如何高效遍历正整数n的二进制每一位核心技巧是位运算 循环此处修正笔误“的是”为“是”用n amp; 1判断当前最右边的位是否为 1结果为 1 则当前位是 1否则是 0用n n 1将二进制右移一位依次判断每一位直到n 0时遍历结束用一个变量如index记录当前遍历的位的索引从 0 开始每右移一次index 加 1。4. 复杂度分析两种思路对比算法思路时间复杂度空间复杂度适用场景基础模拟存储1的位置O(logn)O(log n)O(logn)O(k)O(k)O(k)k为1的个数新手入门、逻辑直观优化版一次遍历O(logn)O(log n)O(logn)O(1)O(1)O(1)面试优选、空间敏感场景说明O(logn)O(log n)O(logn)的时间复杂度源于——正整数n的二进制位数为log2n1log_2 n 1log2​n1遍历所有位的次数与二进制位数成正比效率极高即使n10^9二进制也仅 30 位左右。AC 代码两种版本贴合要求格式版本一基础模拟版存储1的位置直观易懂from typing import List class Solution: def binaryGap(self, n: int) - int: # 存储所有1的位置 one_positions [] index 0 # 遍历二进制每一位记录1的位置 while n 0: # 判断当前位是否为1 if n 1 1: one_positions.append(index) # 右移一位索引加1 n n 1 index 1 # 计算相邻1的最大距离 max_gap 0 # 至少需要2个1才有相邻距离 for i in range(1, len(one_positions)): gap one_positions[i] - one_positions[i-1] if gap max_gap: max_gap gap return max_gap版本二优化版一次遍历O(1)额外空间面试优选from typing import List class Solution: def binaryGap(self, n: int) - int: max_gap 0 # 记录上一个1的位置初始为-1未找到第一个1 last_one -1 index 0 while n 0: # 判断当前位是否为1 if n 1 1: # 不是第一个1计算距离 if last_one ! -1: gap index - last_one if gap max_gap: max_gap gap # 更新上一个1的位置为当前索引 last_one index # 右移一位索引加1 n n 1 index 1 return max_gap代码解释分版本说明版本一基础模拟版代码解释初始化one_positions列表用于存储所有 1 的位置index用于记录当前遍历的二进制位索引从 0 开始二进制遍历循环条件n 0确保遍历完所有二进制位n 1判断当前最右位是否为 1若是则将当前索引加入列表n n 1右移一位index自增 1计算最大距离遍历one_positions列表从索引 1 开始因为要计算相邻两个 1 的距离计算当前位置与前一个位置的差值更新最大距离返回结果若列表长度小于 2无相邻 1max_gap仍为 0直接返回否则返回最大距离。版本二优化版代码解释初始化max_gap初始化为 0用于记录相邻 1 之间的最长距离即使没有找到两个及以上 1最终也能直接返回 0无需额外判断last_one初始化为 -1作为标记位——当值为 -1 时说明尚未找到第一个 1避免误计算距离index初始化为 0用于记录当前遍历的二进制位索引从最右侧第 0 位开始计数。二进制遍历逻辑循环条件n 0确保遍历完正整数n的所有二进制位当n右移至 0 时所有位已遍历完毕。每次循环中先通过n 1判断当前最右侧的位是否为 1这是位运算判断二进制位的核心技巧高效且简洁。距离计算与更新若当前位是 1先判断last_one是否不等于 -1——若不等于说明已经找到过前一个 1此时计算当前索引与last_one的差值即两个相邻 1 的距离若该差值大于当前max_gap则更新max_gap无论是否计算距离都要将last_one更新为当前索引为下一次找到 1 时计算距离做准备。遍历推进每次循环末尾通过n n 1将n的二进制右移一位同时index自增 1确保下一次遍历的是当前位的左一位索引计数准确。结果返回遍历结束后max_gap中存储的就是相邻 1 之间的最长距离若未找到两个及以上 1max_gap仍为初始值 0直接返回即可逻辑简洁且无冗余。测试案例验证两种版本均适用案例 1n 22二进制 “10110”遍历过程优化版index0n2210110n10 → 不处理n右移为111011index1index1n111011n11 → last_one-1更新last_one1n右移为5101index2index2n5101n11 → last_one1距离2-11max_gap1更新last_one2n右移为210index3index3n210n10 → 不处理n右移为11index4index4n11n11 → last_one2距离4-22max_gap2更新last_one4n右移为0循环结束返回 max_gap2 ✅案例 2n 8二进制 “1000”遍历过程优化版index0n81000n10 → 不处理n右移为4index1index1~3n1均为0不处理n逐步右移至1index4index4n1n11 → last_one-1更新last_one4n右移为0循环结束全程仅找到1个1max_gap0 ✅案例 3n 5二进制 “101”遍历过程优化版index0n5101n11 → last_one-1更新last_one0n右移为2index1index1n210n10 → 不处理n右移为1index2index2n11n11 → last_one0距离2-02max_gap2更新last_one2n右移为0循环结束返回 max_gap2 ✅常见易错点提醒易错点1索引计数错误——误将二进制最左侧作为第0位正确做法是最右侧为第0位如5的二进制101两个1的位置分别是0和2距离为2易错点2last_one初始值设置错误——若初始化为0会误将第一个1的位置当作前一个1导致计算错误必须初始化为-1易错点3循环条件错误——误将n 0作为循环条件当n0时会多执行一次循环无需处理正确条件为n 0易错点4位运算使用错误——误将n 1 0当作判断1的条件或误用右移运算符为左移导致遍历逻辑混乱。总结本题属于二进制位运算基础题核心考察两点一是二进制位的遍历与判断技巧二是空间优化思维。