难度: Easy
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2 输出：[0,1,1] 解释： 0 --> 0 1 --> 1 2 --> 10
示例 2：
输入：n = 5 输出：[0,1,1,2,1,2] 解释： 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101
提示：
0 <= n <= 105进阶：
O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？__builtin_popcount ）运行时间: 20 ms
内存: 16.8 MB
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0]
num = 1
cnt = 0
for i in range(1, n + 1):
if cnt < num:
cnt += 1
else:
cnt = 1
num <<= 1
ans.append(ans[i - num] + 1)
return ans
该题解采用了动态规划的思路。利用已知的结果来帮助计算后续的结果。基本思路是利用二进制数的性质：任何数x的二进制1的个数，可以由比它小的某个数的二进制1的个数加一得到。具体地，对于当前的数i，若i是2的幂（即i = 2, 4, 8, ...），则i的二进制表示中只有一个1。否则，可以找到最大的2的幂p，使得p < i，然后i的1的个数就是i - p的1的个数加1。这里利用数组ans存储结果，ans[i]表示数i的二进制中1的个数，通过迭代方式计算每一个i从1到n的1的个数。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] # 初始化结果数组，ans[0]为0，因为0的二进制中没有1
num = 1 # num表示当前的最大2的幂
cnt = 0 # cnt用于计数，以判断何时当前的i超过了当前的最大2的幂
for i in range(1, n + 1):
if cnt < num:
cnt += 1 # 如果当前的i没有超过最大的2的幂，增加计数
else:
cnt = 1 # 一旦达到或超过，重置计数，并将num左移一位（即num翻倍）
num <<= 1
ans.append(ans[i - num] + 1) # 根据i - num的结果加1来得到i的1的个数
return ans
在二进制中，每当我们到达一个2的幂，新的一位1将被添加到最左端，其他位均为0（例如2是10，4是100）。这意味着任何数i的1的个数可以看作是i减去这个最大的2的幂p后的数的1的个数加上一个1（因为p是一个2的幂，所以它的二进制中只有一个1）。例如，i = 14，最接近且小于14的2的幂是8（二进制1000），14的二进制是1110，14 - 8 = 6，二进制是110，6的1的个数是2，所以14的1的个数是3。这种方法利用了已知的较小数的结果来高效地计算较大数的结果。
在动态规划中，问题的解决策略是自底向上的。对于这个问题，我们从最简单的案例开始，即0的二进制中1的个数是0，然后逐步构建到更高的数字。对于每个新的i，我们利用数组ans中已经计算并存储的结果（即i - p的结果），这保证了每一步计算都是基于前面已经验证的正确结果进行的。这种方式确保了整个计算过程的正确性和效率。
在这个题解中，`cnt`变量用于跟踪当前数字i与当前的最大2的幂num之间的关系。每次当`cnt`小于`num`时，说明当前的i还没有达到下一个2的幂，我们可以继续利用当前的最大2的幂来计算1的个数；但一旦`cnt`等于`num`，表示达到了下一个2的幂，我们需要重置`cnt`并将`num`翻倍（左移一位），以此来更新我们使用的最大2的幂。这个机制保证了每当i到达一个新的2的幂，我们都正确地更新了2的幂的值和计数器，从而正确地计算接下来的数字的1的个数。