力扣热题100题-比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 –> 0
1 –> 1
2 –> 10
示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 –> 0
1 –> 1
2 –> 10
3 –> 11
4 –> 100
5 –> 101

提示：

0 <= n <= 105

进阶：

很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/counting-bits

解答1：

class Solution {
    public int[] countBits(int n) {
        int [] result = new int[n+1];
        for(int i =0;i<=n;i++){
            result[i] = Integer.bitCount(i);
        }
        return result;
    }
}

使用Integer工具计算二进制中1的个数。

但是显而易见，这种就是占了使用工具的便宜，那么如果是自己思考，又是怎么处理呢？

解法2：

class Solution {
    public int[] countBits(int n) {
        int [] result = new int[n+1];
        for(int i =0;i<=n;i++){
            result[i] = getOneNum(i);
        }
        return result;
    }

    /**
    * 获取二进制中1的个数
    当i为1 时，结果为：1
    当i为2时，结果为：1
    当i为3时，结果为：2
    1 & 0 = 01;
    2 & 1 = 00
    3 & 2 = 01
     */
    public int getOneNum(int i){
        int count =0;
        while(i > 0){
            i = i&(i-1);
            count++;
        }
        return count;
    }
}

此算法的时间复杂度为：O(N log N)

空间复杂度：O(1)。除了返回的数组以外，空间复杂度为常数。

思考：上面的算法可知在循环的过程中其实有一些重复的动作，例如：计算3的时候，3&2 = 1 下一步要计算 1&0 但在此之前已经计算过1&0了，所有，可以减少这类计算的次数，由此得到解法3.

解法3：

class Solution {
    public int[] countBits(int n) {
        int [] result = new int[n+1];
        int bigHight = 0;
        for(int i =1;i<=n;i++){
            bigHight = i&(i-1);
            if(bigHight == 0){
                result[i] = 0 + 1;
            } else {
                result[i] = result[bigHight] +1;
            }
        }
        return result;
    }
}

时间复杂度：O(N)

优化为：

class Solution {
    public int[] countBits(int n) {
        int [] result = new int[n+1];
        for(int i =1;i<=n;i++){
            result[i] = result[i&(i-1)] +1;
        }
        return result;
    }
}

赞👍🏻