在 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]

Arnab Chakraborty

更新於： 2020 年 4 月 28 日

2K+ 瀏覽次數

開啟你的 職業生涯

完成課程並獲得認證

開始學習