leetcode 868. 二进制间距

leetcode 868. 二进制间距

题目描述

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 <= n <= 109

解题思路

法1

位操作+模拟\

将数字右移i位然后与1进行与操作,如果得到结果为1,则证明数字的第i位为1

否则说明第i位为0

这样我们就可以判断第i位的0/1了

用两个变量储存1的位置,再用一个变量储存最大的两个1的位置差

遍历数字取两个1距离最长的进行输出

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

maxDist和dist变量为0，prevBit变量为-1。maxDist用于记录最大距离，dist用于临时存储两个相邻1之间的距离，prevBit用于记录上一个为1的位的索引。

通过对整数进行右移位操作，我们可以逐个检查每一位是否为1。如果某位为1，则表示找到了一个1。我们可以计算当前位的索引与上一个为1的位的索引之间的距离，并将其与之前记录的最大距离进行比较和更新。

最后，我们返回最大距离作为结果。

func binaryGap(n int) int {
 maxDist := 0
 dist := 0
 prevBit := -1

 for i := 0; i < 32; i++ {
  if (n>>i)&1 == 1 {
   if prevBit != -1 {
    dist = i - prevBit
    if dist > maxDist {
     maxDist = dist
    }
   }
   prevBit = i
  }
 }

 return maxDist
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 54.55% 的用户 通过测试用例： 261 / 261 炫耀一下: