j

jaryue

V1

2023/05/20阅读:10主题:默认主题

leetcode 868. 二进制间距

leetcode 868. 二进制间距


题目描述

  1. 二进制间距

给定一个正整数 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 炫耀一下:



分类:

后端

标签:

后端

作者介绍

j
jaryue
V1