每日一题338

338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

输入: 2
输出: [0,1,1]

思路1 直接计算

  • 利用 x & (x-1), 每次可以消除最后一个二进制1的值,直到为0的特性
  • 时间复杂度是 o(k * num)
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num + 1);
        for (int i = 0; i < res.size(); i++) {
            res[i] = count(i);
        }
        return res;
    }

    int count(int x) {
        int one = 0;
        while (x > 0) {
            x = x & (x-1);
            one++;
        }
        return one;
    }
};

思路2 dp

  • 利用 x & (x-1), 可以通过该公式是否为0, 判断x是不是2的整数次幂
  • 通过之前的二进制1的个数得出当前二进制1的个数
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> bits(num + 1);
        bits[0] = 0;
        int high = 0;
        for (int i = 1; i <= num; i++) {
            if ((i & (i-1)) == 0) {
                high = i;
            }
            bits[i] = bits[i-high] + 1;
        }

        return bits;
    }
};

评论

暂无评论