原文链接: 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]
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
let dp = Array(num + 1).fill(0)
for (let i = 1; i <= num; i++)
(i & 1) ? dp[i] = dp[i - 1] + 1 : dp[i] = dp[i >> 1]
return dp
};
方法二:
通过构造数字的形式, 按照最高位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)] 的双闭区间
/**
* @param {number} num
* @return {number[]}
*/
var countBits = function(num) {
let dp = Array(num + 1).fill(0)
for (let i = 0; (1 << i) <= num; i++) {
for (let j = 0; j < (1 << i) && j + (1 << i) <= num; j++) {
dp[ j + (1 << i)] = dp[j] + 1
}
}
return dp
};