【剑指 Offer II 003】前 n 个数字二进制中 1 的个数 c++

题目描述：

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 1:

输入: n = 2
输出: [0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10

示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

说明 :

0 <= n <= 105

用c++内置函数 c++代码：

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> v;
        for(int i=0;i<=n;i++){
           v.push_back(__builtin_popcount(i));
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10

__builtin_popcount(x)函数表示计算十进制数字x转化为2进制，其中’1’的个数。

动态规划 c++代码：

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> v;
        int dp[n+1];
        dp[0]=0;
        for(int i=0;i<=n;i++){
            if(i%2==0)dp[i]=dp[i>>1];
            if(i%2!=0)dp[i]=dp[i>>1]+1;
            v.push_back(dp[i]);
        }
        return v;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

动态规划。找两个数字的 ‘1’ 的个数之间的关系：

若x为偶数，右移一位，1的个数不影响因为最低位为0：
dp[x] = dp[x>>1]
若x为奇数，右移一位，1的个数会减少1因为最低位为1：
dp[x]=dp[x>>1]+1

总结：

动态规划的状态转移式子，不一定是dp[i]和dp[i-1]之间的关系，可以是dp[f(i)]与dp[g(i)]之间的关系（如i与i/2，i与i>>1…），找dp[i]之间的规律时，思路要打开。