LeetCode 题解工作台
比特位计数
给你一个整数 n ，对于 0 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。 示例 1： 输入： n = 2 输出： [0,1,1] 解释： 0 --> 0 1 --> 1 2 --> 10 示例 2： 输入： n = 5 输出： [0,1,…
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 状态·转移·动态规划
答案摘要
我们直接枚举 $0 \leq i \leq n$ 中的每个数，对于每个数 ，我们用库函数或者 运算得到 中二进制位 的个数。 时间复杂度 $O(n \times \log n)$，忽略答案的空间消耗，空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数 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）
解题思路
方法一：位运算
我们直接枚举 中的每个数，对于每个数 ，我们用库函数或者 运算得到 中二进制位 的个数。
时间复杂度 ，忽略答案的空间消耗，空间复杂度 。
class Solution:
def countBits(self, n: int) -> List[int]:
return [i.bit_count() for i in range(n + 1)]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each dp[i] is computed in constant time using previously computed values. Space complexity is O(n) for the dp array storing counts for 0 through n. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect recognition of the state transition pattern for efficient DP.
- question_mark
Look for correct use of i & (i - 1) for bit manipulation optimization.
- question_mark
Check if candidate avoids naive per-number bit counting loops.
常见陷阱
外企场景- error
Recomputing bit counts for each i instead of using DP, leading to O(n log n) time.
- error
Forgetting to initialize dp[0], causing index errors or incorrect base cases.
- error
Misusing i & (i - 1) logic, resulting in off-by-one errors in counts.
进阶变体
外企场景- arrow_right_alt
Compute the number of 0 bits instead of 1 bits in each number from 0 to n.
- arrow_right_alt
Return bit counts only for odd numbers up to n.
- arrow_right_alt
Calculate bit counts for numbers in a given range [a, b] using the same DP approach.