LeetCode Counting Bits
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.
- 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~num之间每个数的二进制中1的个数列出来，比如num=5时，需要计算0,1,2,3,4,5这6个数字每个数字的二进制中，1的个数，分别是0,1,1,2,1,2。 这样就不能用LeetCode Number of 1 Bits的方法对每个数都求一遍了，复杂度肯定太高了。这题一看就知道是找规律的题，所以我们先把前几个数的二进制1的个数列出来看看。
观察的时候需要分组观察，比如[0,1]的结果为0,1，[2,3]的结果为1,2，也就是在[0,1]的结果上加了1；[4,7]的结果为1,2,2,3，也就是在[0,3]的结果上加了1；[8,15]的结果为1,2,2,3,2,3,3,4，也就是在[0,7]的结果上加了1。
所以重复的周期是以2的幂递增的，初始的时候，我们可以在ans数组中只存[0,1]的结果，然后每次添加2的幂个结果进ans，直到ans的大小大于num为止。
完整代码如下：
[cpp]
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ans = { 0,1 };
while (ans.size() <= num) {
int old_size = ans.size();
for (int i = 0; i < old_size; ++i) {
ans.push_back(ans[i] + 1);
}
}
return vector<int>(ans.begin(), ans.begin() + num + 1);
}
};
[/cpp]
本代码提交AC，用时73MS。
]]>