跳到主要内容

338.比特位计数

链接：338.比特位计数
难度：Easy
标签：位运算、动态规划
简介：给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

题解 1 - typescript​

  • 编辑时间：2021-03-03
  • 执行用时：120ms
  • 内存消耗：50.4MB
  • 编程语言：typescript
  • 解法介绍：计算每一个只含一个 1 的数，进行批量填充。
function countBits(num: number): number[] {
  const ans = [0, 1];
  let max2 = 1;
  while (max2 < num) {
    max2 <<= 1;
    ans.push(...ans.map(v => v + 1));
  }
  ans.length = num + 1;
  return ans;
}

题解 2 - cpp​

  • 编辑时间：2021-12-23
  • 执行用时：8ms
  • 内存消耗：8.4MB
  • 编程语言：cpp
  • 解法介绍：当遇到 2 的指数幂后，从 0 开始重新遍历。
class Solution {
   public:
    vector<int> countBits(int n) {
        vector<int> ans;
        ans.push_back(0);
        if (n == 0) return ans;
        ans.push_back(1);
        if (n == 1) return ans;
        for (int num = 2, i = 0; num <= n; num++, i++) {
            if ((num & (num - 1)) == 0) i = 0;
            ans.push_back(ans[i] + 1);
        }
        return ans;
    }
};

题解 3 - typescript​

  • 编辑时间：2021-03-03
  • 执行用时：156ms
  • 内存消耗：44.4MB
  • 编程语言：typescript
  • 解法介绍：优化题解 2。
function countBits(num: number): number[] {
  if (num === 0) return [0];
  const ans = [0, 1];
  for (let i = 2; i <= num; i++) ans[i] = ans[~~(i / 2)] + (i & 1);
  return ans;
}

题解 4 - typescript​

  • 编辑时间：2021-03-03
  • 执行用时：284ms
  • 内存消耗：48.7MB
  • 编程语言：typescript
  • 解法介绍：计算每一个数的 1 位。
function countBits(num: number): number[] {
  return new Array(num + 1).fill(0).map(
    (_, i) =>
      i
        .toString(2)
        .split('')
        .filter(v => v === '1').length
  );
}