LeetCode 比特位计数题解

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()测试用例测试用例 1num2输入num 2输出[0,1,1]测试用例 2num5输入num 5输出[0,1,1,2,1,2]总结比特位计数是一个经典的位运算问题它可以通过动态规划和位运算来高效地解决。动态规划 位运算的核心思想是利用已计算的结果计算当前数字的 1 的个数。掌握位运算的使用方法对于解决类似的问题非常重要。