0338. 比特位计数.md

0338. 比特位计数

• 标签：位运算、动态规划
• 难度：简单

题目链接

• 0338. 比特位计数 - 力扣

题目大意

描述：给定一个整数 n。

要求：对于 0 ≤ i ≤ n 的每一个 i，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。

说明：

• $0 \le n \le 10^5$。
• 使用线性时间复杂度 $O(n)$ 解决此问题。
• 不使用任何内置函数解决此问题。

示例：

• 示例 1：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

解题思路

思路 1：动态规划

根据整数的二进制特点可以将整数分为两类：

• 奇数：其二进制表示中 $1$ 的个数一定比前面相邻的偶数多一个 $1$。
• 偶数：其二进制表示中 $1$ 的个数一定与该数除以 $2$ 之后的数一样多。

另外，边界 $0$ 的二进制表示中 $1$ 的个数为 $0$。

于是可以根据规律，从 $0$ 开始到 $n$ 进行递推求解。

1. 划分阶段

按照整数 $n$ 进行阶段划分。

2. 定义状态

定义状态 $dp[i]$ 表示为：整数 $i$ 对应二进制表示中 $1$ 的个数。

3. 状态转移方程

• 如果 $i$ 为奇数，则整数 $i$ 对应二进制表示中 $1$ 的个数等于整数 $i - 1$ 对应二进制表示中 $1$ 的个数加 $1$，即 $dp[i] = dp[i - 1] + 1$。
• 如果 $i$ 为偶数，则整数 $i$ 对应二进制表示中 $1$ 的个数等于整数 $i // 2$ 对应二进制表示中 $1$ 的个数，即 $dp[i] = dp[i // 2]$。

4. 初始条件

整数 $0$ 对应二进制表示中 $1$ 的个数为 $0$。

5. 最终结果

整个 $dp$ 数组即为最终结果，将其返回即可。

思路 1：动态规划代码

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0 for _ in range(n + 1)]
        for i in range(1, n + 1):
            if i % 2 == 1:
                dp[i] = dp[i - 1] + 1
            else:
                dp[i] = dp[i // 2]
        return dp

思路 1：复杂度分析

• 时间复杂度：$O(n)$。一重循环的时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$。用到了一位数组保存状态，所以总的时间复杂度为 $O(n)$。