[LeetCode]338. Counting Bits 数字的二进制中1的个数

之前的答案也能成为后面的前提条件。

题目描述:

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 ≤ i ≤ num的数字i,计算其数字的二进制表示中1的个数,并以数组形式返回。

测试用例如题目描述。

进一步思考:

很容易想到运行时间 O(n*sizeof(integer)) 的解法。但你可以用线性时间O(n)的一趟算法完成吗?

空间复杂度应当为O(n)。

你可以像老板那样吗?不要使用任何内建函数(比如C++的__builtin_popcount)。

提示:

你应当利用已经生成的结果。

将数字拆分为诸如 [2-3], [4-7], [8-15] 之类的范围。并且尝试根据已经生成的范围产生新的范围。

数字的奇偶性可以帮助你计算1的个数吗?

 


 

想了很多,我将十进制0-15的所有二进制全都写出来。可是并没有什么用。让它们不停地除以2取整,然后用%取模的最基本算法肯定不行,因为我们要让空间复杂度为O(n),肯定不会那么复杂。

 

虽然根据进位制,我知道这些数是如何加起来的。可是毫无头绪。只是知道逢2进一。我的想法是,但凡2的平方数,比如4、8、16、32,他们的二进制中,1的个数始终就是1。然后根据其他数字与该数字的差值,比如说,9和8相差1,所以就多1,也就是2(8的二进制为1000,9的二进制为1001),10与8的差值是2,根据进位制,末尾为0,第二位为1,所以也多1(10的二进制为1010)。

可是我很快白高兴了一把。是的这样算下去,诸如49这样的数字怎么办?他在32与64的中间位置,离32太远了,能算,可是这样空间复杂度又肯定不是O(n)了。

算法新手肯定需要别人指点,搜狗了一下(搜狗搜索引擎对leetcode比百度友好,额,个人意见)。发现了某前辈的博客里这样写的:

“(引用)
原地址:http://blog.csdn.net/u010005161/article/details/51340145

我得解答:
主要是观察到
1
10
11
100
101
110
111
1000
上述观察到1->10/11  10->100/101 11->110/111
即循环地在每个数后面加0、1可得接下来的数字。因此第i位就是第i/2位+(i%2)的值。

好牛逼。让我赞叹的是他的观察。二进制,在后方每多一位(额我知道我知道是左移一位)就相当于是乘以2。那么这个问题中要我们从0到那个指定的数,而非直接计算那个指定的数的二进制数中1的个数,其实是因为之前的数字也能成为后面的数字的已知条件被使用。

数字就像是滚雪球一样慢慢增大,而之前的二进制数也可以拿来用。确实,每一个非0十进制数都可以除以2取整,得到的数其实就是它本身二进制位右移一位的1的个数。那这样就好办了。如果是偶数,那么右移被丢弃的一定是0,如果是奇数,那么被丢弃的是1,把1补回去就行了。

然后随之而来的是一个哲学问题:为什么老子想不到?

新手上路嘛。

附:解决代码