338.比特位计数

比特位计数

给你一个整数 n，对于 0 <= i <= n 中的每个 i，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]

示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]

提示：

• 0 <= n <= $10^5$

解析

利用 DP：dp[i] = dp[i >> 1] + (i & 1)。

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i >> 1] + (i & 1);
  }
  return dp;
};

i >> 1 是去掉最低位后的数，i & 1 判断最低位是否为 1。时间复杂度 O(n)。