Leetcode 338. Counting Bits 题解

Last Updated At: 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;
    }
};

启发

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