给你一个整数 n ,对于 0 <= i <= n 中的每个 i ,计算其二进制表示中 1 的个数 ,返回一个长度为 n + 1 的数组 ans 作为答案。
时间: 2024-02-18 14:06:07 浏览: 29
好的,这是一个经典的问题,有很多解法。以下是两种常见的解法:
解法一:暴力枚举
对于每个数字,我们可以通过位运算来判断每一位是否为 1。具体来说,我们可以循环遍历每个数字 i,同时维护一个计数器 count,统计 i 的二进制表示中 1 的个数。具体实现可以参考下面的代码:
```python
def countBits(n):
ans = []
for i in range(n + 1):
count = 0
while i > 0:
if i & 1 == 1:
count += 1
i = i >> 1
ans.append(count)
return ans
```
解法二:动态规划
我们可以利用动态规划的思想来优化上面的暴力解法。具体来说,我们可以将一个数字 i 拆分成 i//2 和 i%2 两个部分,其中 i//2 表示 i 右移一位后的结果,i%2 表示 i 的最低位是否为 1。这样,我们可以得到以下状态转移方程:
```
dp[i] = dp[i//2] + i%2
```
其中 dp[i] 表示 i 的二进制表示中 1 的个数。具体实现可以参考下面的代码:
```python
def countBits(n):
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i//2] + i%2
return ans
```
以上两种解法的时间复杂度均为 O(nlogn),空间复杂度均为 O(n)。