Easy

题目描述

给你一个整数 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 ）

解题思路

这道题要求计算从 0 到 n 的每个数字的二进制表示中 1 的个数。有三种主要解法：

方法一：暴力解法（O(n log n)） 对每个数字直接计算其二进制中 1 的个数。虽然简单，但时间复杂度较高。

方法二：动态规划 + 最高有效位（推荐） 观察规律发现，对于范围 [2^k, 2^(k+1) - 1] 内的数字，其 1 的个数等于该数字减去 2^k 后的结果的 1 的个数再加 1。例如：

  • dp[4] = dp[4-4] + 1 = dp[0] + 1 = 1
  • dp[5] = dp[5-4] + 1 = dp[1] + 1 = 2

我们维护当前最高有效位 highBit，当 i 是 2 的幂次时更新它。

方法三：动态规划 + 奇偶性质 利用位运算的性质：dp[i] = dp[i >> 1] + (i & 1)。即一个数的 1 的个数等于它右移一位后的 1 的个数，加上最低位是否为 1。

这里采用方法二，因为它直观且易于理解。

代码实现

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1);
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            dp[i] = dp[i - highBit] + 1;
        }
        return dp;
    }
};

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        highBit = 0
        for i in range(1, n + 1):
            if (i & (i - 1)) == 0:
                highBit = i
            dp[i] = dp[i - highBit] + 1
        return dp

public class Solution {
    public int[] CountBits(int n) {
        int[] dp = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            dp[i] = dp[i - highBit] + 1;
        }
        return dp;
    }
}

var countBits = function(n) {
    const ans = new Array(n + 1);
    ans[0] = 0;
    
    for (let i = 1; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    
    return ans;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历一次数组，每次操作为 O(1)
空间复杂度O(1)除了返回数组外，只使用常数额外空间

相关题目