江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第338题：比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

📖 文章摘要

本文详细解析LeetCode第338题“比特位计数”，这是一道中等难度的位运算和动态规划问题。文章提供了多种解法，包括动态规划和位运算的组合方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升位运算和动态规划能力的程序员。

核心知识点： 位运算、动态规划、二进制表示
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升位运算能力的程序员

题目描述

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

解题思路

方法一：动态规划 + 最低有效位

利用动态规划的思想，结合位运算的特性来解决问题。

关键点：

  • 对于任意数字x，x>>1去掉最低位后的1的个数已经计算过
  • x的1的个数等于x>>1的1的个数加上最低位是否为1
  • 可以用x&1判断最低位是否为1

具体步骤：

  1. 创建长度为n+1的结果数组
  2. 从1开始遍历到n
  3. 对于每个数i，dp[i] = dp[i>>1] + (i&1)
  4. 返回结果数组

时间复杂度：O(n) 空间复杂度：O(1)，不计算返回数组

方法二：动态规划 + 最高有效位

另一种动态规划思路，利用最高有效位的性质。

关键点：

  • 记录当前的最高有效位b
  • 当i达到b的两倍时更新b
  • dp[i] = dp[i-b] + 1

图解思路

方法一：动态规划 + 最低有效位分析

数字 二进制 右移一位 最低位 1的个数
0 0 0 0 0
1 1 0 1 1
2 10 1 0 1
3 11 1 1 2
4 100 10 0 1
5 101 10 1 2

方法二：动态规划 + 最高有效位分析

数字 二进制 最高位b i-b 1的个数
0 0 1 - 0
1 1 1 0 1
2 10 2 0 1
3 11 2 1 2
4 100 4 0 1
5 101 4 1 2

代码实现

C# 实现

public class Solution {
    // 方法一：动态规划 + 最低有效位
    public int[] CountBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
    
    // 方法二：动态规划 + 最高有效位
    public int[] CountBits2(int n) {
        int[] ans = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            ans[i] = ans[i - highBit] + 1;
        }
        return ans;
    }
}

Python 实现

class Solution:
    # 方法一：动态规划 + 最低有效位
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans
    
    # 方法二：动态规划 + 最高有效位
    def countBits2(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        high_bit = 0
        for i in range(1, n + 1):
            if (i & (i - 1)) == 0:
                high_bit = i
            ans[i] = ans[i - high_bit] + 1
        return ans

C++ 实现

class Solution {
public:
    // 方法一：动态规划 + 最低有效位
    vector<int> countBits(int n) {
        vector<int> ans(n + 1);
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
    
    // 方法二：动态规划 + 最高有效位
    vector<int> countBits2(int n) {
        vector<int> ans(n + 1);
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            ans[i] = ans[i - highBit] + 1;
        }
        return ans;
    }
};

执行结果

C# 实现

  • 执行用时：84 ms
  • 内存消耗：42.1 MB

Python 实现

  • 执行用时：68 ms
  • 内存消耗：20.8 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：7.8 MB

性能对比

语言 执行用时 内存消耗 特点
C# 84 ms 42.1 MB 代码结构清晰
Python 68 ms 20.8 MB 实现最简洁
C++ 4 ms 7.8 MB 性能最优

代码亮点

  1. 🎯 巧妙的位运算应用
  2. 💡 优雅的动态规划转移
  3. 🔍 高效的空间利用
  4. 🎨 清晰的实现逻辑

常见错误分析

  1. 🚫 忽略边界条件n=0
  2. 🚫 位运算优先级错误
  3. 🚫 动态规划状态设计不当
  4. 🚫 空间复杂度分析不准确

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
最低有效位 O(n) O(1) 实现简单 不够直观
最高有效位 O(n) O(1) 思路清晰 代码较多

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第338题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！