LeetCode 338题 “Counting Bits” 是一个中等难度的题目，要求我们计算从0到n每个数的二进制表示中1的个数。这个问题可以通过动态规划的方法高效解决。

题目描述

给定一个非负整数 n，对于 0 ≤ i ≤ n 中的每个数 i，计算其二进制表示中1的个数，并将结果作为一个数组返回。

示例

输入: 2 输出: [0,1,1] 解释: 0的二进制表示为0，有0个1。 1的二进制表示为1，有1个1。 2的二进制表示为10，有1个1。

解法思路

我们可以利用动态规划的思想来解决这个问题。具体思路如下：

1. 初始化：创建一个长度为 n+1 的数组 dp，其中 dp[i] 表示数字 i 的二进制表示中1的个数。
2. 基准情况：dp[0] = 0，因为0的二进制表示中没有1。
3. 递推关系：
   • 对于任意一个数 i，我们可以将其表示为 i = 2 * k + b，其中 k 是一个整数，b 是0或1。
   • 如果 b 是0，那么 i 的二进制表示中1的个数与 k 相同，即 dp[i] = dp[k]。
   • 如果 b 是1，那么 i 的二进制表示中1的个数比 k 多1，即 dp[i] = dp[k] + 1。
   • 由于 b 只能是0或1，我们可以通过 i & 1 来判断 b 的值。

代码实现

以下是Python实现的代码：

def countBits(n):

dp = [0] * (n + 1)

# 遍历每个数，计算其二进制表示中1的个数
for i in range(1, n + 1):
    # dp[i] = dp[i >> 1] + (i & 1)
    # i >> 1 相当于 i // 2
    # i & 1 判断i的最低位是0还是1
    dp[i] = dp[i >> 1] + (i & 1)

return dp

n = 2 print(countBits(n)) # 输出: [0, 1, 1]

解释

• i >> 1 是将 i 右移一位，相当于 i 除以2。
• i & 1 是取 i 的最低位，判断是0还是1。

复杂度分析

• 时间复杂度：O(n)，因为我们只需要遍历一次从0到n的所有数。
• 空间复杂度：O(n)，因为我们需要一个长度为 n+1 的数组来存储结果。

通过这种方法，我们可以高效地解决 “Counting Bits” 问题。希望这个解释对你有所帮助！如果有更多问题，欢迎继续提问。