338. 比特位计数

338. 比特位计数

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

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

示例  2:

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

进阶:

• 给出时间复杂度为O(n*sizeof(integer))**的解答非常容易。但你可以在线性时间O(n)**内用一趟扫描做到吗？
• 要求算法的空间复杂度为**O(n)**。
• 你能进一步完善解法吗？要求在 C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

思路

一种暴力转二进制字符串然后对 1 计数解。
另外一种找规律：如果 i 为偶数，说明只是上一个偶数向左移动了一位，1 的个数不变；如果 i 为奇数，则相当于上一个偶数加上一个 1。

解答

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const res = [];
  for (let i = 0; i <= n; i++) {
    let temp = 0;
    for (const num of i.toString(2)) {
      if (num + "" === "1") temp++;
    }
    res.push(temp);
  }
  return res;
};

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const res = [0];
  for (let i = 1; i <= n; i++) {
    if (i % 2 === 0) res.push(+res[i / 2]);
    else res.push(+res[i - 1] + 1);
  }
  return res;
};