题目链接：https://leetcode-cn.com/problems/counting-bits/
难度：简单

描述：
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

题解

  • 当i的末尾为1时，它二进制表示中1的个数比i - 1的多一个。（i是奇数）
  • 当i的末尾为0时，它二进制表示中1的个数与i / 2的一样多。（i是偶数）
  • 当i == 0时，1的个数是0。
    1. class Solution:
    2.   def countBits(self, n: int) -> List[int]:
    3.       ret = [0 for _ in range(n+1)]
    4.       # ret[0] = 0
    5.       for i in range(1, n+1):
    6.           if i & 1 == 1:
    7.               ret[i] = ret[i-1]+1
    8.           else:
    9.               ret[i] = ret[i//2]
    10.       return ret