一. 題目描述
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.
Hint:
You should make use of what you have produced already.
Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
Or does the odd/even status of the number help you in calculating the number of 1s?
二. 題目分析
題目大意是，給定一個非負整數num，對於每一個滿足0 ≤ i ≤ num的數字i，計算這些數字的二進制表示中1的個數，並以數組vector的形式返回。
題目還給出了一系列提示：
很容易想到運行時間為：O(n*sizeof(integer)) 的解法。但你可以用線性時間：O(n)的一趟算法完成嗎？空間復雜度應當為：O(n)。
你可以像老板那樣？不要使用任何內建函數（比如C++的__builtin_popcount）。
提示：
你應該利用已經得到的結果。
將數字拆分為諸如 [2-3], [4-7], [8-15] 之類的范圍。並且嘗試根據已經生成的范圍產生新的范圍。
也許數字的奇偶性可以幫助你計算1的個數？
從題目中給出的諸多提示，加上手寫實例，容易發現一些規律，並得到多種方法，這裡只列出兩種位運算的解決方法。
方法一：
0 0000
1 0001
2 0010 // 左移一位，發現位數和(2/2 = 1)一致
3 0011 // 左移一位，發現位數和(2/2 = 1)一致，只是3為奇數，需要比1多1個1
4 0100
5 0101
6 0110
7 0111
8 1000 // 左移一位，發現位數和(8/2 = 4)一致
9 1001 // 左移一位，發現位數和(9/2 = 4)一致，只是9為奇數，需要比4多1個1
10 1010
11 1011
12 1100
13 1101
14 1110 // 左移一位，發現位數和(14/2 = 7)一致
15 1111 // 左移一位，發現位數和(15/2 = 7)一致，只是15為奇數，需要比7多1個1
根據以上實例，設F[n]表示正整數n的二進制個數，則可得到以下方程：
F[n] = F[n / 2] + F[n] & 1，根據這個方程，只需遍歷一次0 ~ num的整數，即可得到各整數的二進制表示中含1的個數。
方法二：
0 0000
1 0001
2 0010
3 0011 // 對於非2的冪次數n，其二進制表示中1的個數比(n & (n - 1))多一個
4 0100
5 0101
6 0110
7 0111
8 1000 // 對於2的冪次數n，(n & (n - 1)) = 0，同樣滿足二進制表示中1的個數比(n & (n - 1))多一個
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
該規律較難找出，可得到以下方程：F[n] = F[n & (n - 1)] + 1
三. 示例代碼
// C++，方法一
class Solution {
public:
vector countBits(int num) {
vector result;
if (num < 0) return result;
result.push_back(0);
for (int i = 1; i <= num; ++i)
{
result.push_back(result[i >> 1] + (i & 1));
}
return result;
}
};
# Python，方法一
class Solution(object):
def countBits(self, num):
"""
:type num: int
:rtpye: List[int]
"""
result = [0]
for i in range(1, num + 1):
result += result[i >> 1] + (i & 1),
return result
// C++，方法二
class Solution {
public:
vector countBits(int num) {
vector result;
if (num < 0) return result;
result.push_back(0);
for (int i = 1; i <= num; ++i)
{
result.push_back(result[i & (i - 1)] + 1);
}
return result;
}
};
# Python，方法二
class Solution(object):
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
result = [0]
for i in range(1, num + 1):
result += result[i & (i - 1)] + 1,
return result
四. 小結
最近項目組中期檢查，耗費了不少時間，算法也沒之前寫的多了，思想容易遲鈍。
