leetcode解题: counting bits (338)

发表于 | 分类于

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:

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?

解法1： 找规律 + Memorization, One pass O(N) Time

这题需要多写几个数出来找一下规律:
如果我们把0到15的二进制表达式写出来，并且把对应的set bit的个数写出来，我们可以得到如下：

0 0000 0

1 0001 1

2 0010 1

3 0011 2

4 0100 1
5 0101 2
6 0110 2

7 0111 3

8 1000 1
9 1001 2
10 1010 2
11 1011 3
12 1100 2
13 1101 3
14 1110 3
15 1111 4

观察后联系hint,发现偶数X的bit数是X/2的bit数，奇数X的bit数是X/2的bit数+1，于是可以得到一个O(N)的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] countBits(int num) {
   
   int[] dp = new int[num + 1];
   // dp[0] is 0
   for (int i = 1; i <= num; i++) {
        if (i % 2 == 0) {
            dp[i] = dp[i / 2];
        } else {
            dp[i] = dp[i / 2] + 1;
        }
    }
    
    return dp;
}

解法2： 找规律 + Memorization, One pass O(N) Time

另一种规律，我们使用i & (i - 1) 来看对应的结果。

0 0000 0 N/A

1 0001 1 0000

2 0010 1 0000

3 0011 2 0010

4 0100 1 0000
5 0101 2 0100
6 0110 2 0100

7 0111 3 0110

8 1000 1 0000
9 1001 2 1000
10 1010 2 1000
11 1011 3 1010
12 1100 2 1000
13 1101 3 1100
14 1110 3 1100
15 1111 4 1110

更加简化的一个规律是dp[i] = dp[i & (i - 1)] + 1, 比如15, 15 & 14 = ‘1110’， ’1110‘的bits是3，所以15的bits是4
那么就可以得到如下的程序。这个程序更简短。

1
2
3
4
5
6
7
8
9
10
public int[] countBits(int num) {
   
   int[] dp = new int[num + 1];
   // dp[0] is 0
   for (int i = 1; i <= num; i++) {
        dp[i] = dp[i & (i - 1)] + 1;
    }
    
    return dp;
}