Python程式：計算0到n範圍內所有數字的集合位總數

假設我們有一個數字num。對於0 ≤ i ≤ num範圍內的每個數字i，我們必須計算其二進位制對應物中1的個數，並將它們作為列表返回。因此，如果數字是5，則數字為[0, 1, 2, 3, 4, 5]，這些數字中1的個數為[0, 1, 1, 2, 1, 2]，所以它將返回7。

為了解決這個問題，我們將遵循以下步驟：

  • 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元素的總和

讓我們看下面的實現來更好地理解：

示例

 線上演示

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 sum(result)
ob1 = Solution()
print(ob1.countBits(5))

輸入

5

輸出

7

更新於：2020年10月21日

143 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告