一、题目描述
给你一个整数 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]
解释：
1的个数
0 --> 0 | 0
1 --> 1 | 1
2 --> 10 | 1
3 --> 11 | 2
4 --> 100 | 1
5 --> 101 | 2
提示：
0 <= n <= 105
二、题目解释
题意为，给定一个正整数 n，求出不大于n的每一个正整数二进制表示中 1的个数。
2.1 如何求一个数的二进制
例如：
n = 5 的时候，满足条件的有 【0，1，2，3，4，5】这五个数，分别求出对应二进制中 1 的个数。
n = 2 的时候，满足条件的有 【0，1，2】这两个数，分别求出对应二进制中 1 的个数。
注：如何求一个数的二进制
直接上例子吧，
例：
求 11 的二进制表示：
11/2 = 5 ...1
5/2 = 2 ...1
2/2 = 1 ...0
1/2 = 0 ...1 则直接倒叙读取 【余数】即为二进制表示 1011 补上左边的0 到4位或8位或其它的，这不影响数值
求3的二进制表示
3/2 = 1 ...1
1/2 = 0 ...1 则直接倒叙读取 【余数】即为二进制表示 11 即 ： 0011
2.2 解题
搞清楚原理，这道题最简单的解法也就随之而出，我们只需要对符合条件的每个整数进行 除 2 取 余数的操作即可，直到 模为0.
我这里用了复杂度比较高的算法：
第一层for循环表示 对每个符合条件的数 i 进行求取 二进制的操作，并记录 1 的个数；
第二层循环表示每次循环的具体操作，也就是除2取余。你也可以使用for循环，我用的 while
public static int[] countBits(int n) {
int[] arr = new int[n+1];
for(int i = 0;i<=n;i++){
int sum = 0;
int copy = i;
while(copy > 0){
int yu = copy%2;
if(yu == 1)sum++;
copy = copy/2;
}
arr[i] = sum;
}
return arr;
}
public static void main(String[] args) {
int fib = fib(5);
System.out.println(fib);
}
其它的解法后续再更新吧 0.o … o.0