描述

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

示例

示例 1:

  1. 输入: n = 2
  2. 输出: [0,1,1]
  3. 解释: 
  4. 0 --> 0
  5. 1 --> 1
  6. 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

    进阶

  • 给出时间复杂度为 O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？

  • 要求算法的空间复杂度为 O(n) 。
  • 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作。

解题思路

题解有一种常规解法，三种动规解法，这里选择最好理解的一种动规记录下来，其他解法可以看官方题解

方法三：动态规划——最低有效位

对于正整数 x，将其二进制表示右移一位，等价于将其二进制表示的最低位去掉，得到的数是 ⌊x/2⌋。如果 bits[⌊x/2⌋] 的值已知，则可以得到 bits[x] 的值：

  • 如果 x 是偶数，则 bits[x]=bits[⌊x/2⌋]；
  • 如果 x 是奇数，则 bits[x]=bits[⌊x/2⌋]+1。

上述两种情况可以合并成：bits[x] 的值等于 bits[⌊x/2⌋] 的值加上 x 除以 2 的余数。
由于 ⌊x/2⌋ 可以通过 x>>1 得到，x 除以 2 的余数可以通过 x & 1 得到，因此有：
bits[x]=bits[x>>1]+(x & 1)。

遍历从 1 到 n 的每个正整数 i，计算 bits 的值。最终得到的数组 bits 即为答案。

代码

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
}

复杂度分析

  • 时间复杂度：O(n)。对于每个整数，只需要 O(1) 的时间计算「一比特数」。
  • 空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。