题目来源
要求计算从1到n的所有二进制数的1的个数。
我一开始是这么做的，dp[10111] = dp[111] + 1，就是去掉最高位之后的数的1的个数加1。
class Solution {
public:
int cal(int x)
{
int a = 1;
while (a <= x)
a = a * 2;
return x - a / 2;
}
vector<int> countBits(int num) {
vector<int> dp(num+1, 0);
dp[1] = 1;
for (int i=2; i<=num; i++) {
dp[i] = dp[cal(i)] + 1;
}
return dp;
}
};
然后把vector<int>dp改为static，快了一些，代码如下：
class Solution {
public:
int cal(int x)
{
int a = 1;
while (a <= x)
a = a * 2;
return x - a / 2;
}
vector<int> countBits(int num) {
static vector<int> dp;
if (dp.size() == 0)
dp.push_back(0);
for (int i=dp.size(); i<=num; i++) {
dp.push_back(dp[cal(i)] + 1);
}
return vector<int>(dp.begin(), dp.begin()+num+1);
}
};
然后我发现我有点傻啊，不懂得变通啊，明明去掉最高位的1和最低位的1都一样的呀！！！
代码如下：
class Solution {
public:
vector<int> countBits(int num) {
static vector<int> dp;
if (dp.size() == 0)
dp.push_back(0);
for (int i=dp.size(); i<=num; i++) {
dp.push_back(dp[i & (i-1)] + 1);
}
return vector<int>(dp.begin(), dp.begin()+num+1);
}
};
或者这样子：
class Solution {
public:
vector<int> countBits(int num) {
vector<int> dp(num+1, 0);
for (int i=1; i<=num; i++) {
dp[i] = dp[i & (i-1)] + 1;
}
return dp;
}
};
