今天刷leetcode-338, 题目是求出1~n中每个整数的二进制表达式中1的数量， 要求算法复杂度是O(n)。如果不要求时间复杂度的话， 那么这道题其实挺简单的， 就是循环的算每个值的1的数量就行，代码如下：
public int[] countOnes(int n){
int[] res = new int[n+1];
for(int i = 1;i <= n;i++){
int num = 0;
while (i != 0){
num += (i & 1) == 0 ? 0 : 1;
i >>= 1;
}
res[i] = num;
}
return res;
}
这样子的话因为有两个循环， 所以时间复杂度是O(n2), 不满足题目的要求。
这时候要考虑使用动态规划的思想了，就是使用之前已经计算好的结果，已达到减少时间复杂度。 而且我们还可以利用二进制的一个特殊的规律， 就是n&(n-1)会去除掉n 二进制的最后一个1, 所以n的二进制的1的数量其实就是n&(n-1) 的二进制1的数量加1。 所以动态规划的转换方程是 dp[i] = dp[i&(i-1)] + 1 代码如下：
public int[] countBits(int num) {
int[] dp = new int[num+1];
for(int i = 1; i <= num;i++){
dp[i] = dp[i&(i-1)] + 1;
}
return dp;
}
