[338][中等][动态规划] 比特位计数

题目描述

338. 比特位计数

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

示例 1:

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

示例 2:

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

进阶:

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

• 要求算法的空间复杂度为O(n)。

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

解题思路

在时间复杂度要求是$O(n)$的情况下, 就不能遍历每个数字数1了, 需要结合之前遍历数字的结果信息, 减少重复的计算, 因此需要使用动态规划的方法

奇偶数规律

参考: 清晰的思路

对于所有的数字, 只有两类:

• 奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1

• 偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的

初始条件为数字0中为1位的个数是0.

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        for i in range(1, num + 1):
            if i & 1 == 0:
                bits.append(bits[i // 2])
            else:
                bits.append(bits[i - 1] + 1)
        return bits

最高有效位

计算数字$i$的一比特数时, 其二进制表达的最高为值肯定为1, 而使用从小到大遍历的方法, 抛开这个最高位的1, 剩余的位数组成的数字, 之前肯定见过, 也记录过这个数字的比特数.

因此当前数$i$的一比特数就是其最高位对应的数字, 设为$j$, 以及剩余部分$z=i-j$对应的比特数, 而这个数字在动态规划遍历的过程中已经记录了.

所以我们要使用一个变量记录当前的最高位. 最高位数字有个特点, 它只有最高位位1, 其余位都是0, 因此使用$y\&(y-1)==0$来判断当前数字是否是最高位, 因为$y\&(y-1)==0$的作用是将$y$中最低的1位置0.

或者满足最高位的数字肯定是2的整数次幂, 可以利用这个方法记录当前的最大的2的整数次幂.

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        highBit = 0
        for i in range(1, num + 1):
            if i & (i - 1) == 0:
                highBit = i
            bits.append(bits[i - highBit] + 1)
        return bits

或者省略记录, 直接寻找去掉最高位后剩余位数组成数字中的一比特数, 然后直接加一即可.

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        for i in range(1, num + 1):
            bits.append(bits[i & (i - 1)] + 1)
        return bits

参考资料

• 清晰的思路

• 比特位计数