《leetCode》: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: For num = 5 you should return [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.
構想一:run time O(n*sizeof(integer))
ヒントに示すように,時間複雑度がO(n*sizeof(integer))であれば,かなり簡単である.すなわち,各数のバイナリ表現のうち1の個数がどれだけであるかを順次判断する.

int countBitOne(int a){
    if(a<0){
        return 0;
    }
    int count=0;
    while(a){
        int temp=a%2;
        count+=temp;
        a=a>>1;
    }
    return count;
}

int* countBits(int num, int* returnSize) {
    if(num<0){
        return NULL;
    }
    int *res=(int *)malloc((num+1)*sizeof(int));//  ：   num+1    
    for(int i=0;i<=num;i++){
        res[i]=countBitOne(i);
    }
    *returnSize=num+1;
    return res;
}

こんな考えでやれば、ACができないと思っていたのに、意外にもACができた.
考え方2:時間複雑度O(n)
考え方:num<2の場合結果:0 1 num<4の場合結果:0 1 1 2 num<8の場合結果:0 1 1 2,1 2 3
以上の結果から分かるように、2^i~(2^(i+1))-1区間における数が1を含む個数は、対応する0~(2^i)-1の個数に1を足す.すなわち

res[pow(2,i)+j]=res[j]+1;0<=j<pow(2,i) pow(2,i)+j<=num;

実装コードは次のとおりです.

int mypow(int a,int b){
    int res=1;
    for(int i=0;i<b;i++){
        res*=a;
    }
    return res;
}

int* countBits(int num, int* returnSize) {
    if(num<0){
        return NULL;
    }
    int *res=(int *)malloc((num+1)*sizeof(int));//  ：   num+1    
    if(res==NULL){
        printf("malloc failure");

    }
    res[0]=0;
    *returnSize=num+1;
    if(num==0){
        return res;
    }
    res[1]=1;
    if(num==1){     
        return res;
    }
    //    num     num 2    
    int n=num;
    int count=1;
    while(n!=1){
        n=n>>1;
        count++;
    }   
    for(int i=1;i<count;i++){
        int powValue=mypow(2,i);
        for(int j=0;powValue+j<=num&&j<powValue;j++){//  ： powValue+j<=num
            res[powValue+j]=res[j]+1;
        }       
    }   
    return res;
}