[数据结构与算法]leetcode 比特位计数

leetcode 比特位计数

338. 比特位计数

给你一个整数 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 ）

Related Topics

位运算

动态规划

思路1 ：位运算

用&和>>运算符提高效率。

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n+1];
        for(int i = 1; i <= n;i++){
            int count = 0;
            int num = i;
            while(num > 0){
                count += num & 1;
                num = num >> 1;
            }
            result[i] = count;
        }
        return result;
    }
}

思路2：Brian Kernighan 算法

将x&(x-1)就可以将x的最后一个1变成0。

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

思路3：动态规划

当计算i的比特数时，如果存在一个数0<= j < i，比i的二进制只少了一个1.那么dp[i] = dp[j]+1.

1. 对于正整数x而言，如果我们知道正整数y<=x,并且y是的2的幂。则y的二进制只有高位的1.那么z = x-y.显然z只比x少一个1。

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n+1];
        int height = 0;
        for(int i = 1; i <= n;i++){
            //更新幂
            if((i&(i-1)) ==  0){ //当i是2的幂时，二进制只有一个1
                height = i;
            }
            result[i] = result[i-height]+1;
        }
        return result;
    }
}
解答成功:
			执行耗时:1 ms,击败了99.93% 的Java用户
			内存消耗:45.5 MB,击败了11.43% 的Java用户