LeetCode LCR 003. 比特位计数

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ LCR 003. 比特位计数

思路分析

解法一：动态规划（推荐）

核心思路：

dp[i] 表示 i 的二进制 1 的个数。

利用关系 dp[i] = dp[i >> 1] + (i & 1)。

线性遍历即可得到全部结果。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数字上限。

空间复杂度：O(n)，用于保存 dp 数组。

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }

        return dp;
    }
}

func countBits(n int) []int {
	dp := make([]int, n+1)

	for i := 1; i <= n; i++ {
		dp[i] = dp[i>>1] + (i & 1)
	}

	return dp
}

相似题目

题目	难度	考察点
191. 位 1 的个数	简单	位运算
338. 比特位计数	简单	DP、位运算
190. 颠倒二进制位	简单	位运算
461. 汉明距离	简单	XOR、位运算
477. 汉明距离总和	中等	位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/58946351