Cinte's Leetcode Record
0%

338. Counting Bits

Posted on Edited on In Disqus:
Symbols count in article: 812 Reading time ≈ 1 mins.

338. Counting Bits

O(32n) 解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret;
        for(int i = 0; i <= num; ++i)
        {
            int cur = i;
            int count = 0;
            // 10进制转2进制，每次共32bit
            while(cur)
            {
                int j = cur % 2;
                if(j == 1)
                    ++count;
                cur /= 2;
            }
            ret.push_back(count);
        }
        return ret;
    }
};
使用库
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret;
        for(int i = 0; i <= num; ++i)
        {
            ret.push_back(__builtin_popcount(i));
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ret(num + 1);
        for(int i = 0; i <= num; ++i)
        {
            ret[i] = ret[i >> 1] + (i & 1); // 右移相当于取出了除了最后一位的所有值，如果最后一位为1就加一，最后一位为0，那就和右移后的一样
        }
        return ret;
    }
};

右移加上最后一位，类似动态规划的思想