題目要求:
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:
For num = 5 you should return [0,1,1,2,1,2]
大概題意:
給定一個正整數(shù)n，計算 0<= i <= n 中 i 的二進制中的1的個數(shù)猜惋，并以數(shù)組的形式返回臀稚。
解題思路:
維護一個數(shù)組dp, 對于 i培慌，如果 i 是 2 的 n 次冪谅河，則dp[i] = 1双抽，
否則详幽，dp[i] = 1 + dp[i-2^log2(i)]尖阔。因為對于一個非0 整數(shù) i,其二進制的最高位必定為1,對應(yīng)的十進制整數(shù)為 2^log2(i)。我們可以把原問題分解為 最高位中1的個數(shù) + 剩余位中1的個數(shù)晃听，剩余位又可繼續(xù)分百侧，形成遞歸。
- 源碼示例:
public int[] countBits(int num) {
int [] dp = new int[num+1];
dp[0] = 0;
for (int i =1; i <=num ; i++) {
int v1 = (int) (Math.log(i)/Math.log(2)); //log2N = logeN /loge2
int v2 = (int) Math.pow(2,v1); // 2^n
dp[i] = v2 == i ? 1: 1 + dp[i-v2];
}
return dp;
}
