Python 中的二进制间隙

假设我们有一个正整数 N，我们需要在 N 的二进制表示中找出两个连续 1 之间的最长距离。如果不存在两个连续的 1，则返回 0。

因此，如果输入类似于 22，则输出将为 2，因为 22 的二进制形式是 10110。在 22 的二进制表示中，有三个 1 和两个连续的 1 对。第一个连续的 1 对的距离为 2，第二个连续的 1 对的距离为 1。答案将是这两个距离中的较大值，即 2。

要解决此问题，我们将遵循以下步骤 -

  • K := 列出 N 的二进制表示位
  • Max := 0，C := 0，S := 0
  • Flag := False
  • i 从 0 到 K 的大小范围， do
    • 如果 K[i] 等于 '1'，且 C 等于 0，且 Flag 等于 False，则
      • C:= i
      • Flag := True
    • 否则当 K[i] 等于 '1' 且 Flag 为 true 时，则
      • S:= i
      • 如果 Max<abs(S-C)，则
        • Max := |S-C|
      • C:= S
  • 返回 Max

让我们看看以下实现以获得更好的理解 -

示例

 现场演示

class Solution:
   def binaryGap(self, N):
      B = bin(N).replace('0b','')
      K = str(B)
      K = list(K)
      Max = 0
      C = 0
      S =0
      Flag =False
      for i in range(len(K)):
         if K[i] is '1' and C is 0 and Flag is False:
            C=i
         Flag = True
         elif K[i] is '1' and Flag:
            S=i
            if Max<abs(S-C):
               Max = abs(S-C)
               C=S
      return Max
ob = Solution()
print(ob.binaryGap(22))

输入

22

输出

2

更新于：04-Jul-2020

2K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始吧
广告