問題：
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.
大意：
給出一個非負整數(shù)num。對于 0 ≤ i ≤ num 范圍的每個數(shù)計算它們二進制表示的數(shù)中的1的個數(shù)场航，并返回它們組成的數(shù)組紧武。
例子：
對 num = 5 你應(yīng)該返回 [0,1,1,2,1,2]选侨。
進階：
- 很容易找到時間復(fù)雜度為 O(n*sizeof(integer))的解決方案。但你能不能在線性時間復(fù)雜度O（n）中解決呢？
- 康健復(fù)雜度需要是O（n）。
你能不能像一個boss一樣做烛恤？不要使用像c++中 __builtin_popcount 一樣的內(nèi)置的函數(shù)去做。
思路：
把0~7的二進制表示法的數(shù)字列出來余耽，數(shù)其中的1的個數(shù)缚柏，找到一個規(guī)律，0對應(yīng)的數(shù)是0碟贾，1币喧、2對應(yīng)的是1個1。往上走只用計算不斷除以2一直除到1后袱耽，存在余數(shù)為1的次數(shù)杀餐，加上最后的1，就是該數(shù)二進制表示法中1的個數(shù)朱巨。
注意初始化結(jié)果數(shù)組的時候容量為 num+1史翘，不是 num。
我的做法時間復(fù)雜度應(yīng)該是O（nlogn）冀续。
初始化int型數(shù)組后恶座，數(shù)組所有元素默認為0，所以對0的判斷處理可以略去沥阳。
代碼（Java）：
public class Solution {
public int[] countBits(int num) {
int[] result = new int[num+1];
for (int i = 0; i <= num; i++) {
if (i == 0) result[i] = 0;
else if (i <= 2) result[i] = 1;
else {
int numberOfOne = 1;
int number = i;
while (number > 1) {
numberOfOne += number % 2;
number = number / 2;
}
result[i] = numberOfOne;
}
}
return result;
}
}
他山之石：
public int[] countBits(int num) {
int[] f = new int[num + 1];
for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1);
return f;
}
這個做法把上面的思想簡化了很多，i&1其實就是看最后一位有沒有1自点，也就是取余為1桐罕。然后加上 f[i >> 1]，這個其實就是當前數(shù)字除以2后對應(yīng)的數(shù)字的1的個數(shù)桂敛，所以可以看出我的做法做了很多無用功功炮，因為沒有利用到已經(jīng)得出的結(jié)果，而這個做法的時間復(fù)雜度就是O（n）了术唬。
合集：https://github.com/Cloudox/LeetCode-Record
