Leetcode 338. Counting Bits 题解

最后编辑于: 2016-03-28

我的解

手写出前几个答案序列会发现规律：[[[[0][1]][1,2]][1,2,2,3]]…

从0开始作为“一层”，后一层与前一层包含的数个数相同，且与之前一层组成新的一层。对于相邻层，后一层之内的元素是前一层内对应位置的元素值+1。这样的递推归入如下：

0 -> 1
[0, 1] -> [1, 2]
[0, 1, 1, 2] -> [1, 2, 2, 3]

设置 flag 变量表示每一层的元素个数，计算完每一层后flag值翻倍。使用 cnt 变量计数，任何时候超出num则退出循环。代码如下：

132 ms

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res;
        int cnt = 1;
        int flag = 1;
        res.push_back(0);
        while(cnt <= num)
        {
            int start = cnt;
            for (int tmp = flag; tmp > 0 && cnt <= num; --tmp)
            {
                res.push_back(1 + res[start-tmp]);
                cnt++;
            }
            flag *= 2;
        }
        return res;
    }
};

更好的解

一个数 * 2 就是把它的二进制形式全部左移一位，反过来看，一个数的二进制形式除去最后一位之外，其余位包含的1的总数，和其一半（/2）对应的二进制形式中的1的总数是相同的，也就是右移1位对应的结果。另外，最后1位是不是1，可以用i & 1来判断。

128 ms

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res = vector<int>(num+1,0);
        for(int i=1;i<=num;i++){
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
};

启发

看到类似的题，先考虑位运算。