Counting Bits
给一个数n, 返回一个数组里面是, 1到n所有1的bits的计数. 这个用dp做, dp[i] 就是i的bit.
class Solution {
public int[] countBits(int num) {
int result = 0;
int j = 1;
int dp[] = new int[num+1];
// for 0, it is 0
dp[0] = 0;
if(num == 0){
return dp;
}
// for 1, it is 1
dp[1] = 1;
if(num == 1){
return dp;
}
// for all power of 2, it is 1. for exmple 4 is 100 in binary
for(int i=2;i<=num;i=i*2){
dp[i] = 1;
}
// for rest of number,
for(int i=2;i<=num;i++){
if(dp[i] == 1){
j = i;
}else{ // if dp[i] == 0, then the number of 1 bit of i is equals to the previous number of 1 + number of 1 bit of dp[i-j]'s
dp[i] = dp[j] + dp[i-j];
}
}
return dp;
}
}