比特位计数
难度:
标签:
题目描述
给你一个整数 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 <= 105
进阶：
- 很容易就能实现时间复杂度为
O(n log n)的解决方案，你可以在线性时间复杂度O(n)内用一趟扫描解决此问题吗？ - 你能不使用任何内置函数解决此问题吗？（如，C++ 中的
__builtin_popcount）
代码结果
运行时间: 20 ms, 内存: 16.8 MB
// 思路：利用Stream的IntStream.rangeClosed生成从0到n的整数流，然后使用map方法计算每个数二进制中1的个数。
// 使用Integer.bitCount来计算1的个数，并将结果收集到数组中。
import java.util.stream.IntStream;
public int[] countBits(int n) {
return IntStream.rangeClosed(0, n)
.map(i -> Integer.bitCount(i))
.toArray();
}解释
方法:
该题解采用了动态规划的思路。利用已知的结果来帮助计算后续的结果。基本思路是利用二进制数的性质：任何数x的二进制1的个数，可以由比它小的某个数的二进制1的个数加一得到。具体地，对于当前的数i，若i是2的幂（即i = 2, 4, 8, ...），则i的二进制表示中只有一个1。否则，可以找到最大的2的幂p，使得p < i，然后i的1的个数就是i - p的1的个数加1。这里利用数组ans存储结果，ans[i]表示数i的二进制中1的个数，通过迭代方式计算每一个i从1到n的1的个数。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在计算i的二进制中1的个数时，可以通过查找最大的2的幂p来确定i - p的1的个数加1？
▷🦆
动态规划在此题中是如何确保每次计算都是基于已知正确的结果进行的？
▷🦆
在题解中提到的`cnt`变量具体是用来实现什么功能？它如何帮助管理2的幂的更新？
▷相关问题
位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数
-3。
示例 1：
输入：n = 00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：n = 00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：n = 11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
- 输入必须是长度为
32的 二进制串 。
进阶：
- 如果多次调用这个函数，你将如何优化你的算法？