LeetCode 338. 比特位计数

原文链接: LeetCode 338. 比特位计数

https://leetcode-cn.com/problems/counting-bits/

给定一个非负整数 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）来执行此操作。

使用两种dp实现

方法一:

分为技术和偶数两种情况,

初始化dp[0] = 0

奇数时末尾为1, dp[i] = dp[i-1] + 1

偶数时末尾为0, dp[i[ = dp[i>>1]

1/**
2 * @param {number} num
3 * @return {number[]}
4 */
5var countBits = function(num) {
6  let dp = Array(num + 1).fill(0)
7  for (let i = 1; i <= num; i++)
8    (i & 1) ? dp[i] = dp[i - 1] + 1 : dp[i] = dp[i >> 1]
9  return dp
10};

方法二:

通过构造数字的形式, 按照最高位1的位置来进行dp

初始化dp[0] = 0

对于最高位第 i 位的数字为1时, 对于 j (0<=j<i) 来说 dp[ j + (1<<i) ] = dp[j] + 1 

注意i从0开始, 表示第0位为1即是数字1

j每次从0开始直到 (1<<i - 1)结束, 并且需要判断 j + (1<<i) 是否已经超出范围

j + (1<<i) 的取值范围 为 [1000.... , min(111111..., num)] 的双闭区间

1/**
2 * @param {number} num
3 * @return {number[]}
4 */
5var countBits = function(num) {
6  let dp = Array(num + 1).fill(0)
7  for (let i = 0; (1 << i) <= num; i++) {
8    for (let j = 0; j < (1 << i) && j + (1 << i) <= num; j++) {
9      dp[ j + (1 << i)] = dp[j] + 1
10    }
11  }
12
13  return dp
14};