01

题目描述

题目描述：

给定一个非负整数num。

对于0≤i≤num范围中的每个数字i，计算其二进制数中的1的数目并将它们作为数组返回。

示例：

输入: 2

输出: [0,1,1]

解释：

十进制0，1，2三个数的二进制数分别为
0：0000 含有0个1
1：0001 含有1个1
2：0010 含有1个1
因此输出为0，1，1

输入: 7

输出: [0,1,1,2,1,2,2,3]

解释：

十进制0,1,2,3,4,5,6,7八个数的二进制数分别为
0：0000 含有0个1
1：0001 含有1个1
2：0010 含有1个1
3：0011 含有2个1
4：0100 含有1个1
5：0101 含有2个1
6：0110 含有2个1
7：0111 含有3个1
因此输出为0，1，1，2，1，2，2，3

02

代码分析

由题目描述可知

设f(x)为x二进制中1的个数

如f(3)=2

3的二进制表达式为0011，故二进制中1的个数为2。

1.如果输入i为偶数，那么f(i)=f(i//2),因为i//2本质上是i的二进制右移一位，高位补零，所以1的数量不变。

如4, 6, 8等
4的二进制为0100，2的二进制为0010
f(4)=1=f(2)

6的二进制为0110，3的二进制为0011
f(6)=2=f(3)

8的二进制为1000，4的二进制为0100
f(8)=1=f(4)

2.如果输入i为奇数，那么f(i)=f(i-1)+1，i为奇数时，i-1必定为偶数，而偶数的二进制最低位一定是0，

那么该偶数二进制加1后的二进制最低位变为1且不会进位，所以奇数二进制中1的个数比它上一个偶数二进制中1的个数多一个1，

即f(i)=f(i-1)+1。

如3, 5, 7, 9等
3的二进制为0011，3-1=2的二进制为0010
f(3)=f(2)+1=1+1=2

5的二进制为0101，4的二进制为0100
f(5)=f(4)+1=1+1=2

7的二进制为0111，6的二进制为0110
f(7)=f(6)+1=2+1=3

9的二进制为0101，8的二进制为0100
f(9)=f(8)+1=1+1=2

所以代码为：

class Solution:
    def countBits(self, num: int) -> List[int]:
        res=[0]
        for i in range(1,num+1):
            if i%2==0:
                res.append(res[i//2])
            else:
                res.append(res[i-1]+1)
        return res