题目描述:
给你一个整数 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 <=
进阶:
- 很容易就能实现时间复杂度为
O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？ - 你能不使用任何内置函数解决此问题吗？（如，C++ 中的
__builtin_popcount ）
题目分析:
这道题可以利用动态规划和位运算进行快速的求解。首先，对于所有的数字，可以分为奇数和偶数两类，在二进制中，我们很容易知道对应一个奇数，肯定比这个奇数之前的那个偶数多一个 1 ，也就是多了二进制表示中最低位的那个 1 。例如， 3 的二进制为 11 ， 3 - 1 = 2 ， 2 的二进制表示法中 1 的个数为 1 ，再加上 1 刚好就是 2 ，即 3 的二进制表示法中 1 的个数为 2 。
十进制 | 二进制 | 十进制 | 二进制 |
0 | 0 | 1 | 1 |
2 | 10 | 3 | 11 |
而对于偶数来说，二进制表示中，偶数中 1 的个数与当前这个数舍弃最低一位后得到的数中的 1 的个数相同。例如， 4 的二进制表示为 100 ，舍弃掉最后一位变为 10 ，对应的十进制值为 2 ， 2 的二进制表示法中 1 的个数为 1 ，则对于 4 的二进制表示法中 1 的个数也为 1 。
十进制 | 二进制 | 十进制 | 二进制 |
0 | 0 | 1 | 1 |
2 | 10 | 3 | 11 |
4 | 100 | 5 | 101 |
6 | 110 | 7 | 111 |
我们先定义一个结果数组，其中索引 i 上的值表示数字 i 的二进制含有 1 的个数。对于第 i 个数字，如果它二进制的最后一位为 1 ，即它为奇数，那么它含有 1 的个数为索引 i-1 上的值加上 1 ；如果它二进制的最后一位为 0 ，即它为偶数，那么它含有 1 的个数和其算术右移结果相同，即与索引 i>>1 上的值相同。
题解:
执行用时: 1 ms
内存消耗: 42 MB
class Solution {
public int[] countBits(int n) {
// 结果数组
int[] dp = new int[n + 1];
// 循环每个数
for (int i = 1; i <= n; ++i) {
// 如果当前数 i 和 1 按位与结果为 0
// 则 i 为偶数
if ((i & 1) == 0) {
// 1 的个数为 i 舍弃最后一位对应的数的 1 的个数
dp[i] = dp[i >> 1];
} else {
// 否则为奇数
// 1 的个数为 i - 1 对应的数的 1 的个数值加 1
dp[i] = dp[i - 1] + 1;
}
}
// 返回结果集
return dp;
}
}题目来源:力扣(LeetCode)