题目要求:
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]
大概题意:
给定一个正整数n，计算 0<= i <= n 中 i 的二进制中的1的个数，并以数组的形式返回。
解题思路:
维护一个数组dp, 对于 i，如果 i 是 2 的 n 次幂，则dp[i] = 1，
否则，dp[i] = 1 + dp[i-2^log2(i)]。因为对于一个非0 整数 i,其二进制的最高位必定为1,对应的十进制整数为 2^log2(i)。我们可以把原问题分解为 最高位中1的个数 + 剩余位中1的个数，剩余位又可继续分，形成递归。
- 源码示例:
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;
}
