338. 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 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [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.
思路分析
思路一
我们来看探究一下规律:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 10 | 11 | 100 | 101 | 110 | 111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
0 | 1 | 1 | 2 | 1 | 2 | 2 | 3 | 1 | 2 | 2 | 3 | 2 | 3 | 3 | 4 |
如果用动态规划思路求解的话,我们有如下规律:
dp[0] = 0;
dp[1] = dp[0] + 1;
dp[2] = dp[0] + 1;
dp[3] = dp[1] +1;
dp[4] = dp[0] + 1;
dp[5] = dp[1] + 1;
dp[6] = dp[2] + 1;
dp[7] = dp[3] + 1;
dp[8] = dp[0] + 1;
dp[9] = dp[1] + 1;
…
进一步一般化这个规律:
dp[0] = 0;
dp[1] = dp[1-1] + 1;
dp[2] = dp[2-2] + 1;
dp[3] = dp[3-2] +1;
dp[4] = dp[4-4] + 1;
dp[5] = dp[5-4] + 1;
dp[6] = dp[6-4] + 1;
dp[7] = dp[7-4] + 1;
dp[8] = dp[8-8] + 1;
dp[9] = dp[9-8] + 1;
…
所以使用动态规划解决的思路如下:
dp[0] = 0
dp[index] = dp[index - offset] + 1
这个offset是2的倍数
思路二
第二个思路比较奇妙,有这样一个规律:对于一个整数i, i&(i-1)这个操作会去掉以二进制表示的i的最后一个1
比如:10=1010,11=1011,则11&10=1010;13=1101,14=1110,则14&13=1100
这样的话,使用动态规划进行解决的思路如下:
dp[0] = 1
dp[i] = dp[i & (i-1)] + 1
i&{i-1}去掉了一个1,我们再给加上,则可以得到i中包含的1的总个数
C++实现
思路一
class Solution {
public:
vector<int> countBits(int num) {
vector<int> bits(num + 1, 0);
int offset = 1;
for (int i = 1; i <= num; ++i) {
offset = i == offset * 2 ? i : offset;
bits[i] = bits[i - offset] + 1;
}
return bits;
}
};
思路二
class Solution {
public:
vector<int> countBits(int num) {
vector<int> bits(num + 1, 0);
for (int i = 1; i <= num; ++i) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
};
Scala实现
object CountingBits {
def countBits(num: Int): Array[Int] = {
val bits = Array.ofDim[Int](num + 1)
for (i <- 1 to num) {
bits(i) = bits(i & (i - 1)) + 1
}
bits
}
}
注意:使用Scala版本在LeetCode提交会报Time Limit Exceeded错误,而使用Java相同的代码就不会。我觉得是Scala中使用Java原生数组实现的,而且还有装箱拆箱的操作,所以效率比较低,就导致了超时了。