在 Python 中计算位数

假设我们有一个非负整数 num。对于范围 0 ≤ i ≤ num 内的每个数字 i，我们必须计算其二进制对应数字中的 1 的个数，并将它们作为列表返回。因此，如果数字为 5，则数字为 [0, 1, 2, 3, 4, 5]，而这些数字中 1 的个数为 [0, 1, 1, 2, 1, 2]

为了解决此问题，我们将按照以下步骤操作：

  • res := 一个包含 num + 1 个 0 的数组
  • offset := 0
  • 对于 1 到 num + 1 范围内的 i
    • 如果 i 和 i – 1 = 0，则 res[i] := 1 且 offset := 0
    • 否则增加 offset 1，且 res[i] := 1 + res[offset]
  • 返回 res

示例（Python）

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

 在线演示

class Solution:
   def countBits(self, num):
      result = [0] * (num+1)
      offset = 0
      for i in range(1,num+1):
         if i & i-1 == 0:
            result[i] = 1
            offset = 0
         else:
            offset+=1
            result[i] = 1 + result[offset]
      return result
ob1 = Solution()
print(ob1.countBits(6))

输入

6

输出

[0, 1, 1, 2, 1, 2, 2]

更新于： 2020 年 4 月 28 日

2K+ 浏览次数

开启你的 职业生涯

完成课程并获得认证

开始学习
广告