LeetCode 比特位计数题解
题目描述
给定一个非负整数 num，返回一个数组 answer，其中 answer[i] 表示 i 的二进制表示中 1 的个数。
示例：
输入：num = 2
输出：[0,1,1]
输入：num = 5
输出：[0,1,1,2,1,2]
解题思路
方法：动态规划 + 位运算
思路：
- 使用动态规划和位运算来解决这个问题。
- 对于每个数字 i，最低的设置位（lowbit）是 i & (-i)。
- i 中 1 的个数等于 i 去掉最低设置位后的数字中 1 的个数加 1。
- 即：
count[i] = count[i >> 1] + (i & 1)。
复杂度分析：
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。
代码实现
方法：动态规划 + 位运算
# 比特位计数（动态规划 + 位运算） def count_bits(num): result = [0] * (num + 1) for i in range(1, num + 1): result[i] = result[i >> 1] + (i & 1) return result # 测试 def test_count_bits(): num = 2 print(count_bits(num)) # 输出：[0, 1, 1] num = 5 print(count_bits(num)) # 输出：[0, 1, 1, 2, 1, 2] if __name__ == "__main__": test_count_bits()方法：Brian Kernighan 算法
# 比特位计数（Brian Kernighan 算法） def count_bits_bk(num): result = [] for i in range(num + 1): count = 0 n = i while n: n &= (n - 1) count += 1 result.append(count) return result # 测试 def test_count_bits_bk(): num = 5 print(count_bits_bk(num)) # 输出：[0, 1, 1, 2, 1, 2] if __name__ == "__main__": test_count_bits_bk()测试用例
测试用例 1：num=2
输入：num = 2
输出：[0,1,1]
测试用例 2：num=5
输入：num = 5
输出：[0,1,1,2,1,2]
总结
比特位计数是一个经典的位运算问题，它可以通过动态规划和位运算来高效地解决。
动态规划 + 位运算的核心思想是：利用已计算的结果，计算当前数字的 1 的个数。
掌握位运算的使用方法，对于解决类似的问题非常重要。
