描述：
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
思路：
首先是一个数减1，对应二进制的变化就是最右的一个1变为0，而这个1右边的所有0变为1，即相当于包括最后一个1在内的右边所有位取反，例如12（1100）减1，得到11（1011），然后再与变化前的数12（1100）进行与&运算，得到8（1000），可以看出经过这样一个运算之后这个数的1的个数减少了一个，所以可以利用这个原理，得到res[i]=res[i&(i-1)]+1
class Solution {
public int[] countBits(int num) {
int[] dp = new int[num+1];
for(int i=1;i<num+1;i++){
dp[i] = dp[i&(i-1)]+1;
}
return dp;
}
}
网友评论