LeetCode-338-比特位计数

image.png

解题思路：

1. 枚举：

dp[0]=0; dp[1]=1;
dp[2]=1; dp[3]=2;
dp[4]=1; dp[5]=2;
dp[6]=2; dp[7]=3;
dp[8]=1; dp[9]=2;
dp[10]=2; dp[11]=3;

2. 归纳数字的二进制属性：

• 奇数i比偶数i-1多一个1；
• 偶数i和偶数i/2的1的个数一样，偶数的末位为0，i/2相当于把有1的位数右移一位。

Python3代码

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