[Python]lintcode 664 ::给出一个 非负 整数 num，对所有满足 0 ≤ i ≤ num 条件的数字 i 均需要计算其二进制表示中数字 1 的个数并以数组的形式返回。

lintcode 664

:给出一个 非负 整数 num，对所有满足 0 ≤ i ≤ num 条件的数字 i 均需要计算其二进制表示中数字 1 的个数并以数组的形式返回。

code

def countBits(self, num):
    # write your code here
    dp=[[0] for _ in range(num+1)]
    dp[0]=0
    for i in range(1,num+1,1):
        dp[i]=dp[(int)(i/2)]+(i%2)
    
    
    return dp

想法

1.dp数组复用上一位，而这里dp[(int)(i/2)]这是由于这是二进制位，他的上一位需要/2，(i%2)代表是否进位，因为余数为1，说明其需要进位+1.
2.(int)(i/2)必须强制转换为int,不然报错 TypeError: list indices must be integers or slices, not float。