LCR 003. 比特位计数

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

示例 1:

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

示例 2:

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

说明 :

  • 0 <= n <= 105

进阶:

  • 给出时间复杂度为 O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？
  • 要求算法的空间复杂度为 O(n) 。
  • 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作。
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
// import java.util.ArrayList;

// class Solution {
//     public int[] countBits(int n) {
        
//         ArrayList<Integer> list = new ArrayList<>();
//         // 将0-n每一个数字首先转换为二进制数，存放于list中
//         for (int i = 0; i <= n; i++) {
//             String str = Integer.toBinaryString(i);
//             int ans = Integer.parseInt(str, 2);
//             list.add(ans);
//         }

//         return count(list);
        



//     }
//     // 计数函数
//     public int[] count(ArrayList<Integer> list) {
//         int[] res = new int[list.size()];
//         res[0] = 0;
//         res[1] = 1;
//         int count = 0;
//         int size = res.length;

//         for (int i = 0; i < size; i++) {
//             int a = list.get(i);
//             int b = list.get(i);

//             if ((a & (b - 1)) == 0)
//                 res[i] = 1;
//             else {
//                 char[] ch = String.valueOf(a).toCharArray();
//                 for (int j = 0; j < ch.length; j++) {
//                     if (ch[j] == '1') {
//                         count++;
//                     }
//                 }
//                 res[i] = count;
//             }
//             count = 0;
//         }

//         return res;
//     }
// }

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        res[0] = 0;

        for (int i = 1; i <= n; i++) {
            // 使用 i & (i - 1) 来计算 i 的二进制表示中包含的 1 的个数
            res[i] = res[i & (i - 1)] + 1;
        }

        return res;
    }
}