一 题目:
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n 1 的数组 ans 作为答案。
代码语言：javascript复制示例 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二 思路:
动态规划: 划分子问题
- 如果当前数字i为奇数,则前一个数是偶数(最后一个数字为0),那前一个数字加1,就是二进制末位的0变成了1而已,1的数量加了1
- 如果当前数字i为偶数,那么其比特位计数和其i/2的值是一样的,为一个数是偶数那么他的二进制比他的一半的二进制只是多了一个0而已
另外这里判断奇偶可以用&运算,比如我们可以判断(i&1)是否等于1,等于1就是奇数,否则是偶数,至于为什么呢?因为&操作两个位均为1才为1,而数字1的前面N位均补充为0，跟它做与运算，前面肯定为0
三 代码:
代码语言：javascript复制 class Solution {
public int[] countBits(int n) {
int[] dp = new int[n 1];
dp[0] = 0;
// 如果当前数字i为奇数,则前一个数是偶数(最后一个数字为0),那前一个数字加1,就是二进制末位的0变成了1而已,1的数量加了1
// 如果当前数字i为偶数,那么其比特位计数和其i/2的值是一样的,为一个数是偶数那么他的二进制比他的一半的二进制只是多了一个0而已
for (int i = 1; i <= n; i ) {
//如果是奇数
if ((i&1)==1){
dp[i]=dp[i-1] 1;
}else{
dp[i]=dp[i/2];
}
}
return dp;
}
}
