LeetCode

September 8, 2018

Leetcode: Counting Bits

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:

1 2	Input: 2 Output: [0,1,1]

Example 2:

1 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原生数组实现的，而且还有装箱拆箱的操作，所以效率比较低，就导致了超时了。