博客

今日心情：重新启程！

题目描述：

LeetCode 338. 比特位计数

给你一个整数

n

，对于

0 <= i <= n

中的每个

i

，计算其二进制表示中


1

的个数

，返回一个长度为

n + 1

的数组

ans

作为答案。

解题代码1 ：时间复杂度 O(n^2)

class Solution {
    
    public int[] countBits(int n) {
        int[] ans = new int[n+1];
        
        for(int i=0;i <= n;i++){
            ans[i] = countOne(i);

        }
        return ans;
    }
    
    public int countOne(int n){
        
        int count = 0;
        while(n != 0){
            n = n & (n-1);
            count++;
        }
        return count;
    }
}

解题思路：

（1）使用helper函数：countOne(int n) 计算一个数的1bit个数，使用位与操作进行计算，然后计数。n = n & (n-1) 的操作其实可以看作删除位为1的bit，每次删除count 都加1，直到 n 为 0 的时候，说明没有为 1 的 bit 了之后，count 的值就代表 所有bit 为1 的总个数。

（2）遍历0到n的数据，分别对每个数计算bit 为 1 的总个数。

解题代码2：（找到每段的最高位）

class Solution {

    // solution 2: find the highest bit
    public int[] countBits(int n) {
        
        int[] ans = new int[n+1];
        ans[0] = 0;
        int highbit = 0;
        
        for(int i = 1 ; i <=n; i++){
            // carry
            if((i & (i-1)) == 0){
                highbit = i;
            }
            ans[i] = ans[i-highbit]+1;
        }
        return ans;
    }
    
}

解题思路：以下面例子为例进行阐述

（1） 找到每次的 进位数：i & (i-1)) == 0 ；当 i 满足上述等式的时候，i 此时为一个进位数，比如说 2 ， 4 ，8。此时 2 到4之间的 3 的 1 bit数 就是  i ==1 的 为1所有的bit数加上 i == 2 为1的所有bit数。

（2）同理，在4到8之间的数 的 为1的所有bit数 为 （ i –  高位进位数的i ）的 为1的所有bit数 加上1（也就是加上这个进位数中的1，因为很明显进位数只有一个bit 位 为1）。