Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1‘s in their binary representation and return them as an array.
Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
Follow up:
public int[] countBits(int num) {//位运算 my
int[] res = new int[num+1];
for (int i = 0; i <=num ; i++) {
res[i]=0;
int n = i;
while (0!=n){
n= n&(n-1);
res[i]++;
}
}
return res;
}
时间复杂度O(n)，找规律
public int[] countBits(int num) {// O(n) my
int[] res = new int[num+1];
res[0]=0;
int flag = 1;
int j=0;
if(num>0){
res[1]=1;
}
for (int i = 2; i <=num ; i++) {
if(i==2*flag){
flag=flag*2;
j=0;
}
res[i]=res[j]+1;
j++;
}
return res;
}
简洁版
f[i] = f[i / 2] + i % 2
public int[] countBits(int num) {
int[] f = new int[num + 1];
for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1);
return f;
}
原文：https://www.cnblogs.com/zhacai/p/10430986.html