leetcode 338. Counting Bits

统计数字的二进制表示的中的　１　的个数

自己写的　思路

9 = ret[8] + ret[9-8]
12 = ret[8]+ret[12-8]
i = ret[ 小于ｉ的２的最大幂次 ｊ ] +ret[ i-j ]

代码

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int num, int* returnSize) {

    *returnSize = num+1;

    int* res = (int*)malloc(sizeof(int)*num+1);

    for(int i=0;i<=num&&i<=2;i++){
        if(i == 0){
            res[i] = 0;
        }
        else{
            res[i] = 1;
        }
    }
    if(num<=2){
        return res;
    }

    int* index = (int*)malloc(sizeof(int)*num+1);

    memset(index,0,num*sizeof(int));
    int count = 2;
    int bcount = 2*count;
    for(int i=2;i<=num;i++){
        if(i>=count && i<bcount){
            index[i] = count;
        }
        else{
            index[i] = bcount;
            count = bcount;
            bcount = 2*count;
        }
    }
    res[0] = 0;
    res[1] = res[2] = 1;
    for(int i=3;i<=num;i++){
        if( index[i] ==i ){
            res[i] = 1;
        }
        else{
            res[i] = res[index[i]] + res[ i-index[i] ];
        }
    }
    free(index);
    return res;
}

看到别人的代码　才知道什么叫做　excellent idea

参考　338. Counting Bits 数字的二进制中1的个数

代码

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* countBits(int num, int* returnSize) {
    *returnSize = num+1;
    int* ret = (int*)malloc(sizeof(int)*(num+1));
    memset(ret,0,(num+1)*sizeof(int));
    for(int i=0;i<=num;i++){
        ret[i] = ret[i>>1] + i%2;
    }
    return ret;
}