|
难度： 简单
题目： 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
解题：
x&(x-1) 这个公式很关键，比如
5 | 101
4 | 100
3 | 011
2 | 010
1 | 001
0 | 000
每个数字与比它小1的数字进行按位与运算，会将从右至左的最后一个1去掉。
对于一个数字去求它二进制数1的个数，可以使用如下方式：
int iNum = 0;
while(x)
{
iNum++;
x = x&(x-1);
}
因此可以得到一个公式：
f
[
x
]
=
f
[
x
(
x
?
1
)
]
+
1
f[x] = f[x(x-1)] + 1
f[x]=f[x(x?1)]+1
可通过上面的公式，以动态规划的思想构建大小为num+1数组大小的数组dp，dp[0] 是初始状态，表示数字0二进制1的个数。
class Solution {
public:
vector<int> countBits(int n) {
vector<int> dp(n+1,0);
for(int i = 1; i < n+1; ++i)
{
dp[i] = dp[i&(i-1)] + 1;
}
return dp;
}
};
|