Counting Bits
给一个数n, 返回一个数组里面是, 1到n所有1的bits的计数. 这个用dp做, dp[i] 就是i的bit.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
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; } } |