Leetcode 338.比特位计数

题目描述：

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

1
2

输入: 2
输出: [0,1,1]

示例 2:

1
2

输入: 5
输出: [0,1,1,2,1,2]

进阶:

• 给出时间复杂度为 $O(n*sizeof(integer))$ 的解答非常容易。但你可以在线性时间 $O(n)$ 内用一趟扫描做到吗？
• 要求算法的空间复杂度为 $O(n)$。
• 你能进一步完善解法吗？要求在 C++ 或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

链接：

https://leetcode-cn.com/problems/counting-bits

题目分析

1.动态规划 - 最高位

  按照进阶要求中的意思，应该就是不要对每一个数都去模 2 取余一个一个算，那么应该就是要好好利用前面已经算好的结果。观察了一下它们的特点，发现每到 2 的幂次时，就会开启一个新的最高位，并且只有最高位为 1，其他都重置为 0，这个时候前面的那些位又相当于从 0 开始，那么我们就可以取前面的结果。而取前面结果的差值刚好就是这个 2 的幂次。如何判断 2 的幂次呢？它的前一位是全 1，而自己开启了一个新的最高位，并且前面全部置为 0，那么刚好就是没有一位是同 1 的，用“按位与”这种位运算得到的结果是 0。
  其实，用位运算判断 2 的幂次这种方法，我是看了题解才了解的。然后又思索了一下，这样的代码下，对于每一个数，都要判断它与它前一位的“按位与”，这样的运算难道不也是 $O(sizeof(integer))$ 的运算吗？这里还是存在着一点不解的。当然，我自己想到的是套一层内层循环，每次循环大小乘 2，也就是直接用我们所知道的“个数”去使它准确。转念想想，每个循环也都需要判断一次是否满足循环条件，而判断循环条件在底层不也是一次位运算吗？并且循环还有自增等运算，在底层也是一次位运算吧。所以应该还是直接套用位运算是最快的，就姑且认为一次位运算是常数时间的咯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n+1);
        int highBit = 0;
        for(int i = 1; i <= n; i++){
            if((i & i-1) == 0){
                highBit = i;
            }
            dp[i] = dp[i - highBit] + 1;
        }
        return dp;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 就是题目中所给的 n。我们对于每个数的操作是常数时间复杂度的。
  空间复杂度：$O(1)$。通常作为答案返回的数组是不计入空间复杂度的，那我们所需的额外空间只有几个变量。

2.动态规划 - 最低位

  看了一下官方题解，有 3 种动态规划，这种也是非常好理解的一种。我们也可以从最低位找规律。与前面的思路一样，我们最好能用到前面已经得出的结果，如果我们直接将数字右移一位（也就是除以 2，得到的结果肯定更小），如果最低位是 1，那么就还要加上 1，如果最低位是 0，那 1 的个数是不变的。而获取最低位就是直接将其和 1 进行按位与就可以了。

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n+1);
        for(int i = 1; i <= n; i++){
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
};

  时间复杂度：$O(n)$。同上。
  空间复杂度：$O(1)$。同上。