LeetCode 338. 比特位计数（C++）*

1.题目如下：

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
1
2

解释：
0 --> 0
1 --> 1
2 --> 10

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
1
2

解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

提示：

0 <= n <= 105

进阶：

很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

原题链接：https://leetcode.cn/problems/counting-bits/?favorite=2cktkvj

2.代码如下：

class Solution {
public:
//方案一：时间复杂度O(nlogn)
/*
    vector countBits(int n) {
        vector res(n+1,0);
        for(int i=0;i<=n;i++){
            res[i]=getSum(i);
        }
        return res;
    }

    int getSum(int n){
        int sum=0;
        while(n>0){
            if(n%2==1){
                sum++;
            }
            n=n/2;
        }
        return sum;
    }
*/
//方案二：递归
/*
    vector countBits(int n) {
        vector res(n+1,0);
        for(int i=0;i<=n;i++){
            res[i]=getSum(i);
        }
        return res;
    }

    int getSum(int n){
        if(n==1){
            return 1;
        }
        if(n==0){
            return 0;
        }
        if(n==2){
            return 1;
        }
        int s=sqrt(n);
        return getSum(pow(2,s))+getSum(n-pow(2,s));
    }
*/

//方案三：动态规划，最高有效位：
/*
    例：n=9时，res[9]=res[9-8]+1;res[6]=res[6-4]+1
*/

    vector<int> countBits(int n) {
        vector<int> res(n+1,0);
        int highBit=0;
        for (int i=1;i<=n;i++) {
            //当i&(i-1)==0的时候代表此时i就是2的某个整数次幂，直到下一次的整数次幂出现才更改
            if ((i&(i-1))==0) {
                highBit=i;
            }
            //例：res[6]=res[6-4]+1=res[2]+1=2;
            res[i]=res[i-highBit]+1;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67