LeetCode 338 Counting Bits 详解从 O(n log n) 到 O(n) 的五种解法与动态规划推导【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文基于当前仓库中 LeetCode 338Counting Bits比特位计数的完整题解体系展开既有 提示文档 中给出的核心思路目标 O(n) 时间、O(n) 空间递推式dp[i] 1 dp[i - offset]也有 完整题解文章 中覆盖的从暴力枚举到最优 DP 的五种实现路径。读者读完后将掌握「统计 0 到 n 每个整数二进制中 1 的个数」的全部主流解法理解位运算与动态规划结合的核心套路并能在 C、C、Java、Python、Go、Rust、Kotlin、TypeScript 等语言中直接落地实现。1. 问题定义与前置知识题目要求给定一个非负整数n返回一个长度为n 1的数组ans其中ans[i]表示整数i的二进制表示中1的个数约束0 n 10^5参见 c/0338-counting-bits.c 顶部注释。例如n 2时0 00有 0 个 11 01有 1 个 12 10有 1 个 1答案为[0, 1, 1]。在动手解题前题解文章 建议先掌握三块前置知识位运算Bit Manipulation理解二进制表示与 AND、OR、移位等位运算动态规划Dynamic Programming能够利用先前计算结果增量构建解二进制数制Binary Number System理解整数如何以二进制表示、如何数出其中的 1 位。提示文档 同时给出了性能基准目标应达到 O(n) 时间与 O(n) 空间其中n为给定整数。2. 解法一逐位暴力检查Bit Manipulation - I2.1 思路这是最直观的思路对0到n的每个数num依次检查它的 32 个比特位整数通常用 32 位表示看第i位是否为 1。判断方法是用掩码1 i与num做按位与(1 i) num非零则说明该位为 1。这种解法虽然不高效但能非常直观地展示位运算的底层工作方式。2.2 算法步骤初始化结果列表res遍历num从0到n初始化计数器one 0遍历位位置i从0到31若(1 i) num非零则one加一将one追加到res返回res。核心代码Pythonarticles/counting-bits.md 完整多语言版本见原文class Solution: def countBits(self, n: int) - List[int]: res [] for num in range(n 1): one 0 for i in range(32): if num (1 i): one 1 res.append(one) return res2.3 复杂度时间复杂度$O(n \log n)$——每个数最多检查 32 位可视为常数 32整体为 $O(32n)$记为 $O(n \log n)$ 量级与数位成正比空间复杂度$O(1)$ 额外空间$O(n)$ 用于输出数组。3. 解法二Brian Kernighan 算法Bit Manipulation - II3.1 思路暴力法对每个数都要检查全部 32 位显然有浪费。Brian Kernighan 算法基于一个著名观察操作n (n - 1)会清除n的最低位的 1。反复执行该操作直到n变为 0执行次数就是n中 1 的个数。这样我们只遍历「实际存在的 1」而不是全部位。3.2 算法步骤创建大小为n 1的数组res初始化为 0对每个i从1到n令num i当num ! 0时res[i]加一然后执行num (num - 1)清除最低位 1返回res。Python 实现class Solution: def countBits(self, n: int) - List[int]: res [0] * (n 1) for i in range(1, n 1): num i while num ! 0: res[i] 1 num (num - 1) return res仓库中的 rust/0338-counting-bits.rs 正是采用这一思路它先为每个i调用辅助函数set_bits该函数用n n (n - 1)循环消去最低位 1 并计数与本题解完全一致。3.3 复杂度时间复杂度$O(n \log n)$最坏情况下每个数平均需要数次迭代空间复杂度$O(1)$ 额外空间$O(n)$ 用于输出数组。4. 解法三语言内置函数In-Built Function4.1 思路不少语言原生提供了「转换为二进制」或「直接统计置位」的工具。当n较小时用内置函数可以写出极其简洁、可读性最高的代码。这在以下场景特别适用n规模较小或中等可读性优先于极致性能希望快速获得可靠实现。4.2 各语言内置写法语言内置能力核心代码Pythonbin(i).count(1)return [bin(i).count(1) for i in range(n 1)]JavaInteger.bitCount(i)res[i] Integer.bitCount(i);C__builtin_popcount(i)res[i] __builtin_popcount(i);JavaScripti.toString(2)res.push(i.toString(2).split(1).length - 1);C#Convert.ToString(i, 2)res[i] Convert.ToString(i, 2).Count(c c 1);Gobits.OnesCount(uint(i))需math/bitsres[i] bits.OnesCount(uint(i));Kotlinit.countOneBits()return IntArray(n 1) { it.countOneBits() }Swiftnum.nonzeroBitCountres[num] num.nonzeroBitCountRusti.count_ones()(0..n).map(\|i\| i.count_ones() as i32).collect()其中 JavaScript 的写法原理与「内置函数」思想一致i.toString(2)得到二进制字符串再统计其中1的个数仓库中的 typescript/0338-counting-bits.ts 采用了等价的手写hammingWeight先把n转成二进制字符串、拆分成字符数组再逐一统计1。4.3 复杂度时间复杂度$O(n \log n)$每次转换与统计的代价与二进制位数相关空间复杂度$O(1)$ 额外空间$O(n)$ 用于输出数组。5. 解法四基于「最高 2 的幂」的 DPBit Manipulation DP推荐这是 提示文档 引导推导的核心解法也是仓库中多数语言实现采用的标准答案。5.1 思路从二进制模式中发现规律观察连续整数的二进制表示0 →00 个 11 →11 个 12 →101 个 13 →112 个 14 →1001 个 15 →1012 个 16 →1102 个 17 →1113 个 1提示文档指出每当到达一个 2 的幂数字的位模式就会重启。例如要算7的置位数等于1对应最高位100上的那个 1加上3的置位数而3的置位数又等于1加上1的置位数。推广一下对小于4的数加的是「两个位置之前」的计数对小于8的数加的是「四个位置之前」的计数。更形式化地说任意数i可以写作i 不超过 i 的最大 2 的幂 余数因此i 的置位数 1最高位的 1 余数的置位数5.2 递推关系设dp[i]表示i中 1 的个数则dp[i] 1 dp[i - offset]其中offset是不超过i的最大 2 的幂。offset初始为1即 $2^0$每当offset * 2 i也就是i本身成为下一个 2 的幂时把offset更新为i。用「offset * 2 i」而不是「判断是否为 2 的幂」来简化检查这是提示文档给出的关键技巧。5.3 算法步骤创建大小为n 1的 DP 数组dp初始化dp[0] 0、offset 1对i从1到n若i 2 * offset则offset i计算dp[i] 1 dp[i - offset]返回dp。Python 实现class Solution: def countBits(self, n: int) - List[int]: dp [0] * (n 1) offset 1 for i in range(1, n 1): if offset * 2 i: offset i dp[i] 1 dp[i - offset] return dp该实现正是仓库中 python/0338-counting-bits.py、go/0338-counting-bits.go、kotlin/0338-counting-bits.kt 等文件的直接来源三者结构与上述代码逐行对应。5.4 复杂度时间复杂度$O(n)$空间复杂度$O(1)$ 额外空间$O(n)$ 用于输出数组。6. 解法五基于右移的最优 DPBit Manipulation DPOptimal6.1 思路这是仓库源码中 C、C 实现采用的版本c/0338-counting-bits.c、cpp/0338-counting-bits.cpp递推更简洁。核心观察来自右移运算i 1相当于去掉i的最低位i 1告诉我们i的最低位是1还是0。于是setBits(i) setBits(i 1) (i 1)也就是「去掉最低位后的数的置位数 最低位本身是否为 1」。因为i 1一定小于i每个结果只依赖已计算过的更小值天然适合 DP。6.2 算法步骤创建大小为n 1的 DP 数组dp初始化dp[0] 0对i从1到n计算dp[i] dp[i 1] (i 1)返回dp。Python 实现class Solution: def countBits(self, n: int) - List[int]: dp [0] * (n 1) for i in range(n 1): dp[i] dp[i 1] (i 1) return dp仓库中的 C 版本c/0338-counting-bits.c使用calloc分配n 1个元素并借助ret[i] ret[i 1] (i 1)完成计算同时通过returnSize返回长度符合题目对 C 接口「返回值必须 malloc 且由调用方 free」的要求C 版本cpp/0338-counting-bits.cpp注释中给出了直观例子x 1001011101 (605)与去掉最低位后的x 0100101110 (302)二者置位数只差最低位即f(x) f(x / 2) (x mod 2)。6.3 与解法四的关系两种 DP 的本质相同只是切分方式不同解法四把i拆成「最高位的 1 剩余部分」解法五把i拆成「去掉最低位的数 最低位」。两者都做到了每个状态 O(1) 转移从而整体 O(n)。6.4 复杂度时间复杂度$O(n)$空间复杂度$O(1)$ 额外空间$O(n)$ 用于输出数组。7. 仓库中的另一种思路奇偶分类 DP值得补充的是仓库中的 python/0338-counting-bits.py 在标准答案之外还附了一个基于奇偶分类的 DP 变体更容易理解class Solution2: def countBits(self, n: int) - List[int]: res [0] * (n 1) for i in range(1, n 1): if i % 2 1: res[i] res[i - 1] 1 # 奇数比前一个偶数多一个最低位 1 else: res[i] res[i // 2] # 偶数右移一位置位数不变 return res其依据是奇数i的最低位是 1置位数比i - 1偶数多 1偶数i右移一位除以 2后置位数不变最低位是 0被移掉不影响计数。这条路径同样满足 O(n) 复杂度可作为理解 DP 递推的辅助视角。8. 常见陷阱Common Pitfalls题解文章 专门总结了两个高频错误8.1 位移方向写错或运算符优先级错误在使用dp[i] dp[i 1] (i 1)时容易误用左移或忽略运算符优先级导致下标越界或结果错误# 错误用了左移访问了不存在的下标 dp[i] dp[i 1] (i 1) # 错误部分语言中加法先于移位执行 dp[i] dp[i 1 (i 1)] # 实际是 dp[i (1 (i 1))] # 正确 dp[i] dp[i 1] (i 1)8.2 循环边界差一Off-by-One题目要求统计0 到 n含两端因此结果数组必须有n 1个元素循环也必须到达n# 错误数组太小缺少 dp[n] dp [0] * n # 错误循环没有包含 n for i in range(n): # 应为 range(n 1) # 正确 dp [0] * (n 1) for i in range(n 1): # process9. 五法对比与选型建议解法核心技巧时间复杂度额外空间特点逐位暴力检查掩码1 i逐位判断$O(n \log n)$$O(1)$最直观教学价值高Brian Kernighann (n - 1)清除最低位 1$O(n \log n)$$O(1)$迭代次数 1 的个数语言内置函数bitCount/popcount等$O(n \log n)$$O(1)$代码最简洁最高 2 的幂 DPdp[i] 1 dp[i - offset]$O(n)$$O(1)$提示文档主推模式清晰右移 DPdp[i] dp[i 1] (i 1)$O(n)$$O(1)$递推最短仓库 C/C 采用选型建议面试或刷题阶段优先掌握两种 O(n) 的 DP 解法尤其是右移版本代码最短、最不易出错同时理解「最高 2 的幂」版本的推导过程——这正是 hints/counting-bits.md 引导读者自行发现的规律。内置函数方案适合工程中追求可读性的场景Brian Kernighan 算法则是单个数置位统计的经典工具仓库 rust/0338-counting-bits.rs 即演示了其在循环中的复用。本仓库为本题提供了 C、C、Java、Python、Go、Rust、Kotlin、TypeScript、Swift 等多语言实现覆盖了上述全部思路可作为跨语言对照学习的参考资源。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考