题目地址：https://leetcode.com/PRoblems/counting-bits/?tab=Description
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].
Follow up:
It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?Space complexity should be O(n).Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.这个题目有点意思，简单的思考后我们很快地就能发现结果数组的下标与其对应的整数值的关系：下标对应的二进制中1的个数就是其对应的元素的数值。
那这个题目关键是不让去逐位分析整数，那咋办？
那我们随便写几个，看看有啥规律：
1 bitbc[0] => 0000 => 0bc[1] => 0001 => 12 bitsbc[2] => 0010 => 0010 + 0 => 1 + bc[0];bc[3] => 0011 => 0010 + 1 => 1 + bc[1];3 bitsbc[4] => 0110 => 0100 + 00 => 1 + bc[0];bc[5] => 0101 => 0100 + 01 => 1 + bc[1];bc[6] => 0110 => 0100 + 10 => 1 + bc[2];bc[7] => 0111 => 0100 + 11 => 1 + bc[3];看到这里貌似清晰不少了，于是有
rs[x] = rs[x & (x-1)] + 1那么实现如下：
public class CountingBits { public static int[] countBits(int num) { int[] rs = new int[num + 1]; for (int i = 0; i <= num; i++) { rs[i] = rs[i & (i - 1)] + 1; } return rs; } public static void main(String[] args) { System.out.println(Arrays.asList(countBits(5))); return; }}参考文献： https://github.com/haoel/leetcode/tree/master/algorithms/cpp/countingBits
新闻热点
疑难解答
