🥈338. 比特位计数@

🥈Medium

给定一个非负整数 num。对于 0 ≤ i ≤ num范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]

示例 2:

输入: 5
输出: [0,1,1,2,1,2]

进阶:

• 给出时间复杂度为的解答非常容易。但你可以在线性时间内用一趟扫描做到吗？
• 要求算法的空间复杂度为。
• 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++中的 __builtin_popcount）来执行此操作。

题解

直接计算

因为每一个int型数都可以用32位二进制表示。最直观就是遍历每一个数，变成二进制，然后计算每个数二进制中1的个数：

class Solution:
    def countBits(self, num: int) -> List[int]:
        ans=[]
        for i in range(0,num+1):
            temp=str(bin(i))
            count=0
            for j in temp:
                if j=='1':
                    count=count+1
            ans.append(count)
        return ans

这样也行，但复杂度就是。可以利用位运算进行优化！
按位与运算()一个性质是：对任意整数，令，该运算将的二进制表示的最后一个变成，因此对重复操作，直到全部变成，则操作次数就是中1的个数：

Python

class Solution:
    def countBits(self, num: int) -> List[int]:
        def countOnes(x: int) -> int:
            ones = 0
            while x > 0:
                x &= (x - 1)
                ones += 1
            return ones

        bits = [countOnes(i) for i in range(num + 1)]
        return bits

JavaScript

var countBits = function(num) {
    const bits = new Array(num + 1).fill(0);
    for (let i = 0; i <= num; i++) {
        bits[i] = countOnes(i);
    }
    return bits
};

const countOnes = (x) => {
    let ones = 0;
    while (x > 0) {
        x &= (x - 1);
        ones++;
    }
    return ones;
}

复杂度分析

• 时间复杂度：，其中是 型的二进制位数，。需要对从到的每个数使用的时间计算「一比特数」，因此时间复杂度是。

• 空间复杂度：。除了返回的数组以外，空间复杂度为常数。

  动态规划

  一步步推导

动态规划还不熟，一步一步来分析！原题解

刚开始想到的就是遍历与统计，也就是上面的代码：

class Solution:
    def countBits(self, num: int) -> List[int]:
        ans=[]
        for i in range(0,num+1):
            temp=str(bin(i))
            count=0
            for j in temp:
                if j=='1':
                    count=count+1
            ans.append(count)
        return ans

如果把它写成递归，可能会有点懵，需要知道一点二进制的内容。

把第个数分为两种情况：

• 为偶数。那它的二进制1的个数和的二进制1的个数位数相同。因为偶数二进制末尾为0，右移一位就是，二进制中的1未发生变化。

例如4的二进制为00000100，右移之后就变成00000010，也就是2，同样2右移之后变成了00000001，是1

所以对正数而言，右移1位n>>1，就相当于/2，而且比除法效率高
**

• 为奇数，那二进制1的位数=![](https://cdn.nlark.com/yuque/__latex/800ba394e806c049c98cf4b570d04c72.svg#card=math&code=i-1&height=16&width=34)的二进制位数+1；因为奇数二进制末尾为1，如果去掉就是偶数，剩下的推导和就上面一样了😉。

例如5的二进制位00000101，二进制中1个数为2，而4的二进制1个数为1

知道了上面的结论，就可以用递归写出来了：

class Solution(object):
    def countBits(self, num):
        res = []
        for i in range(num + 1):
            res.append(self.count(i))
        return res

    def count(self, num):
        if num == 0:
            return 0
        if num % 2 == 1:
            return self.count(num - 1) + 1
        return self.count(num // 2)

这样