题目
给你一个整数 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)内用一趟扫描解决此问题吗？ - 你能不使用任何内置函数解决此问题吗？（如，C++ 中的
__builtin_popcount）
解答
- 暴力解法
思路：首先新建一个数组用来保存结果，接下来从0开始一直循环到输入的n，用while循环+循环内的数字temp=temp&(temp-1)的操作获得每一个数字对应的二进制1的个数，然后把对应的个数保存在数组中，最后返回结果数组。C++代码实现如下：
class Solution {
public:
vector<int> countBits(int n) {
vector<int> results; // 创建一个用于存储结果的向量
for (int i = 0; i <= n; i++) { // 循环从 0 到 n
int temp = i; // 将当前迭代的数值保存到 temp 变量中
int count = 0; // 初始化计数器为 0
while (temp) { // 进行求解二进制中 1 的个数的操作
temp = temp & (temp - 1); // 通过该操作，每次能将 temp 中最右边的 1 变为 0，并统计操作次数，即为 1 的个数
count++; // 统计 1 的个数
}
results.push_back(count); // 将统计得到的 1 的个数添加到结果向量中
}
return results; // 返回结果向量
}
};- 动态规划
在这个问题中，我们可以利用已经计算过的结果来求解新的结果。思路如下：对于任意的非负整数 i，其二进制表示中 1 的个数可以通过以下方式求得：
- 如果 i 是偶数，那么 i 的二进制表示中 1 的个数等于 i/2 的二进制表示中 1 的个数，因为 i 相当于将 i/2 左移一位并在末尾补上一个 0。
- 如果 i 是奇数，那么 i 的二进制表示中 1 的个数等于 i-1 的二进制表示中 1 的个数再加 1，因为 i 相当于将 i-1 的二进制表示中最右边的 1 变为 0。
class Solution {
public:
vector<int> countBits(int n) {
vector<int> results(n + 1, 0); // 创建一个长度为 n+1 的向量，并初始化所有元素为 0
for (int i = 1; i <= n; i++) {
if (i % 2 == 0) {
// 对于偶数 i，其二进制表示中 1 的个数等于 i/2 的二进制表示中 1 的个数
results[i] = results[i / 2];
} else {
// 对于奇数 i，其二进制表示中 1 的个数等于 i-1 的二进制表示中 1 的个数再加 1
results[i] = results[i - 1] + 1;
}
}
return results;
}
};