338. Counting Bits

Problem description

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).

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和num之间的数字（包括0和num）输出他们二进制形式中1的个数。

例子：

输入：5，返回[0,1,1,2,1,2]。

进一步思考：

非常容易想到复杂度是O(n*sizeof(integer))的解决办法。是否有O(n)或者说遍历一次的解决方法？空间复杂度应该是O(n)

提示：

你应该使用你之前生成的结果。把数字分成一个个区间，例如[2-3], [4-7], [8-15]。然后利用已生成的区间去计算新的区间。或者利用奇偶性来帮助你计算1的数目。 链接：https://leetcode.com/problems/counting-bits/

结题思路：

我们用count来表示这个数组，前后存在递推关系。一个偶数是由小于它2倍的偶数乘2得到，与小于它的偶数相比，二进制形式中1的个数并没有变；一个奇数是由小于它两倍的偶数乘2、加1得到的，二进制形式中1的个数为小于它两倍的偶数1的个数+1。(n & 1) 就是用于判断需不需要加1。 递推式：count[n] = count[n >> 1] + (n & 1) python代码如下： class Solution(object): def countBits(self, num): """ :type num: int :rtype: List[int] """ l = [0] for i in range(1, num + 1): l.append(l[i >> 1] + (i & 1)) return l 运行时间248ms。 java代码如下： public class Solution { public int[] countBits(int num) { int[] count = new int[num + 1]; count[0] = 0; for(int i = 1; i < num + 1; i++){ count[i] = count[i >> 1] + (i & 1); } return count; } }运行时间2ms。