题目描述
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 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [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.
解题思路
先来解释一下题目的意思吧。题目的意思相对比较简单：输入一个整数num，我们要返回一个数组。对于所有小于等于num的整数，我们要求出它们的二进制形式的1的数目，并且放到数组里面。
先讲一个比较简单的思路吧。对于每个小于num的整数我们都可以将它们变成二进制形式的字符串，然后遍历这个字符串，我们就可以找到1的数目:
let str = num.toString(2);
let count = 0;
for (let i = 0; i < str.length; ++i) {
if (str.slice(i, i + 1) === '1') {
count ++;
}
}
上面是一个用js写的简单的demo，我们很容易可以得到每个count的大小。但是这样显然无法完成题目的“隐藏任务”。题目中的follow up要求我们只用O(1 * n)的时间得到结果，这样显然是不符合题目要求的。
为了用O(n)解决上面的问题，显然我们还需要利用已经求出来的结果。让我们先观察0-10的二进制表吧。
| 十进制 | 二进制 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |
| 3 | 11 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 7 | 111 |
| 8 | 1000 |
| 9 | 1001 |
| 10 | 1010 |
根据观察，我们可以发现偶数的二进制是它的一半往左移一位得到。而在移位运算中我们会发现1的数量是不变的，也就是说，如果一个数是偶数，那么它1的数量跟它的一半是一样多的。那么奇数呢？在c++中9/2的结果和8/2的结果是一样的，我们可以看到，4的二进制左移一位之后，将右边补上的0变成1就是9，因此奇数的1的数量是它一半的1的数量再加1.
这样，只要固定0的时候的1的数量（0个1），我们就可以把后续的1的数量全部算出来。
时间复杂度分析
O(n)
空间复杂度分析
O(n)
源码
class Solution {
public:
vector<int> countBits(int num) {
vector<int> result = vector<int>(num + 1, 0);
for (int i = 1; i <= num; ++i) {
result[i] = result[i / 2] + i % 2;
}
return result;
}
};
