338. 比特位计数
338. 比特位计数
题目
Given an integer n, return an arrayans of lengthn + 1 such that foreachi (0 <= i <= n) , ans[i] is thenumber of1 's in the binary representation of i.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Constraints:
0 <= n <= 10^5
Follow up:
- It is very easy to come up with a solution with a runtime of
O(n log n). Can you do it in linear timeO(n)and possibly in a single pass? - Can you do it without using any built-in function (i.e., like
__builtin_popcountin C++)?
题目大意
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入： n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入： n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示：
0 <= n <= 10^5
进阶：
- 很容易就能实现时间复杂度为
O(n log n)的解决方案，你可以在线性时间复杂度O(n)内用一趟扫描解决此问题吗？ - 你能不使用任何内置函数解决此问题吗？（如，C++ 中的
__builtin_popcount）
解题思路
思路一：逐位统计（暴力解法）
- 对于每个数字
i，计算其二进制表示中的1的个数。 - 使用内置函数
toString(2)将数字转换为二进制，然后用split('1').length - 1统计1的个数。
复杂度分析
- 时间复杂度：
O(n * k)，其中k是转换为二进制表示的位数。 - 空间复杂度：
O(n)，用于存储结果数组，处理数字时的临时空间需求为O(log n)。
思路二：动态规划 + 最低有效位
观察规律，对于数字 i：
- 如果
i是偶数，i的二进制中1的个数与i / 2相同，因为最低位是0。 - 如果
i是奇数，i的二进制中1的个数比i - 1多1，因为最低位是1。
递推公式：
result[i] = result[i >> 1] + (i & 1)。
复杂度分析
- 时间复杂度：
O(n)，因为仅需线性遍历i从0到n。 - 空间复杂度：
O(n)，用于存储结果数组。
思路三：动态规划 + 最高有效位
观察规律，对于数字 i：
如果找到数字 i 所对应的最高有效位（如 2^k），可以将 i 分解为 2^k + x，其中 x 是比 2^k 小的余数。
因此，result[i] = result[i - 2^k] + 1。
复杂度分析
- 时间复杂度：
O(n)，因为仅需线性遍历i从0到n。 - 空间复杂度：
O(n)，用于存储结果数组。
代码
逐位统计（暴力解法）
/**
* @param {number} n
* @return {number[]}
*/
var countBits = function (n) {
return new Array(n + 1)
.fill(0)
.map((_, i) => i.toString(2).split('1').length - 1);
};
动态规划 + 最低有效位
/**
* @param {number} n
* @return {number[]}
*/
var countBits = function (n) {
let result = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
result[i] = result[i >> 1] + (i & 1);
}
return result;
};
动态规划 + 最高有效位
/**
* @param {number} n
* @return {number[]}
*/
var countBits = function (n) {
const result = new Array(n + 1).fill(0);
let highBit = 0; // 记录当前最高有效位
for (let i = 1; i <= n; i++) {
if ((i & (i - 1)) === 0) {
// 判断是否是 2^k
highBit = i;
}
result[i] = result[i - highBit] + 1;
}
return result;
};
相关题目
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
|---|---|---|---|---|---|
| 191 | 位1的个数 | [✓] | 位运算 分治 | 🟢 | 🀄️ 🔗 |
| 2859 | 计算 K 置位下标对应元素的和 | 位运算 数组 | 🟢 | 🀄️ 🔗 | |
| 2917 | 找出数组中的 K-or 值 | 位运算 数组 | 🟢 | 🀄️ 🔗 |