跳至主要內容

0338. 比特位计数

ITCharge大约 2 分钟

0338. 比特位计数open in new window

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

题目链接

题目大意

描述:给定一个整数 n

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

说明

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

示例

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

解题思路

思路 1:动态规划

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

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

另外,边界 00 的二进制表示中 11 的个数为 00

于是可以根据规律,从 00 开始到 nn 进行递推求解。

1. 划分阶段

按照整数 nn 进行阶段划分。

2. 定义状态

定义状态 dp[i]dp[i] 表示为:整数 ii 对应二进制表示中 11 的个数。

3. 状态转移方程
  • 如果 ii 为奇数,则整数 ii 对应二进制表示中 11 的个数等于整数 i1i - 1 对应二进制表示中 11 的个数加 11,即 dp[i]=dp[i1]+1dp[i] = dp[i - 1] + 1
  • 如果 ii 为偶数,则整数 ii 对应二进制表示中 11 的个数等于整数 i//2i // 2 对应二进制表示中 11 的个数,即 dp[i]=dp[i//2]dp[i] = dp[i // 2]
4. 初始条件

整数 00 对应二进制表示中 11 的个数为 00

5. 最终结果

整个 dpdp 数组即为最终结果,将其返回即可。

思路 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)
  • 空间复杂度O(n)O(n)。用到了一位数组保存状态,所以总的时间复杂度为 O(n)O(n)