題目地址：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
新聞熱點
疑難解答
