LeetCode Counting Bits

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.
Hint:
  1. You should make use of what you have produced already.
  2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
  3. 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。 ]]>

Leave a Reply

Your email address will not be published. Required fields are marked *